Эффективная охота за словами в зашифрованных буквах
Я думаю, вы могли бы классифицировать это как проблему стиля Эрудит, но это началось из-за друга, упомянувшего британское телевизионное шоу-викторину Countdown. Различные раунды в шоу вовлекают участников, представляющих зашифрованный набор букв, и они должны придумать самое длинное слово, которое они могут. Тот, кого мой друг упомянул, был "RAEPKWAEN".
В довольно короткие сроки я решил что-то в Python для решения этой проблемы, используя PyEnchant для обработки поиска по словарю, однако я заметил, что он действительно не может все так хорошо масштабировать.
Вот что у меня сейчас:
#!/usr/bin/python
from itertools import permutations
import enchant
from sys import argv
def find_longest(origin):
s = enchant.Dict("en_US")
for i in range(len(origin),0,-1):
print "Checking against words of length %d" % i
pool = permutations(origin,i)
for comb in pool:
word = ''.join(comb)
if s.check(word):
return word
return ""
if (__name__)== '__main__':
result = find_longest(argv[1])
print result
Это хорошо для 9-буквенного примера, который они используют в шоу, 9 факториала = 362 880 и 8 факториала = 40 320. В этом масштабе, даже если бы пришлось проверять все возможные перестановки и длины слов, это не так много.
Однако, как только вы наберете 14 символов, это будет 87 178 291200 возможных комбинаций, что означает, что вы полагаетесь на удачу, что слово из 14 символов будет быстро найдено.
В приведенном выше примере слова моей машине требуется около 12 с половиной секунд, чтобы найти "пробуждение". Используя зашифрованные слова из 14 символов, мы могли бы разговаривать в масштабе 23 дней, чтобы проверить все возможные варианты перестановок из 14 символов.
Есть ли более эффективный способ справиться с этим?
10 ответов
Реализация идеи Jeroen Coupé из его ответа с количеством букв:
from collections import defaultdict, Counter
def find_longest(origin, known_words):
return iter_longest(origin, known_words).next()
def iter_longest(origin, known_words, min_length=1):
origin_map = Counter(origin)
for i in xrange(len(origin) + 1, min_length - 1, -1):
for word in known_words[i]:
if check_same_letters(origin_map, word):
yield word
def check_same_letters(origin_map, word):
new_map = Counter(word)
return all(new_map[let] <= origin_map[let] for let in word)
def load_words_from(file_path):
known_words = defaultdict(list)
with open(file_path) as f:
for line in f:
word = line.strip()
known_words[len(word)].append(word)
return known_words
if __name__ == '__main__':
known_words = load_words_from('words_list.txt')
origin = 'raepkwaen'
big_origin = 'raepkwaenaqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnmqwertyuiopasdfghjklzxcvbnm'
print find_longest(big_origin, known_words)
print list(iter_longest(origin, known_words, 5))
Вывод (для моих маленьких 58000 слов dict):
counterrevolutionaries
['reawaken', 'awaken', 'enwrap', 'weaken', 'weaker', 'apnea', 'arena', 'awake',
'aware', 'newer', 'paean', 'parka', 'pekan', 'prank', 'prawn', 'preen', 'renew',
'waken', 'wreak']
Заметки:
Это простая реализация без оптимизации.
words_list.txt- может быть/usr/share/dict/wordsв линуксе
ОБНОВИТЬ
В случае, если нам нужно найти слово только один раз, и у нас есть словарь со словами, отсортированными по длине, например, по этому сценарию:
with open('words_list.txt') as f:
words = f.readlines()
with open('words_by_len.txt', 'w') as f:
for word in sorted(words, key=lambda w: len(w), reverse=True):
f.write(word)
Мы можем найти самое длинное слово, не загружая полный текст в память:
from collections import Counter
import sys
def check_same_letters(origin_map, word):
new_map = Counter(word)
return all(new_map[let] <= origin_map[let] for let in word)
def iter_longest_from_file(origin, file_path, min_length=1):
origin_map = Counter(origin)
origin_len = len(origin)
with open(file_path) as f:
for line in f:
word = line.strip()
if len(word) > origin_len:
continue
if len(word) < min_length:
return
if check_same_letters(origin_map, word):
yield word
def find_longest_from_file(origin, file_path):
return iter_longest_from_file(origin, file_path).next()
if __name__ == '__main__':
origin = sys.argv[1] if len(sys.argv) > 1 else 'abcdefghijklmnopqrstuvwxyz'
print find_longest_from_file(origin, 'words_by_len.txt')
Вы хотите избежать перестановки. Вы можете посчитать, сколько раз символ появляется в обеих строках (исходная строка и одна из словаря). Исключите все слова из словаря, где частота символов не одинакова.
Таким образом, чтобы проверить одно слово из словаря, вам нужно посчитать символы максимум в МАКС. (26, n) раз.
Другой подход, аналогичный ответу @market, заключается в предварительном вычислении "битовой маски" для каждого слова в словаре. Бит 0 устанавливается, если слово содержит по крайней мере один A, бит 1 устанавливается, если он содержит по крайней мере один B, и так далее до бит 25 для Z.
Если вы хотите найти все слова в словаре, которые могут состоять из комбинации букв, вы начинаете с формирования битовой маски для набора букв. Затем вы можете отфильтровать все слова, которые используют другие буквы, проверив, wordBitmask & ~lettersBitMask это ноль. Если это ноль, слово использует только буквы, доступные в коллекции, и поэтому может быть допустимым. Если это ненулевое значение, оно использует букву, недоступную в коллекции, и поэтому не допускается.
Преимущество этого подхода в том, что побитовые операции выполняются быстро. Подавляющее большинство слов в словаре будет использовать по крайней мере одну из 17 или более букв, которых нет в данном наборе, и вы можете быстро отменить их все. Тем не менее, для меньшего количества слов, которые проходят через фильтр, есть еще одна проверка, которую вам еще предстоит выполнить. Вам все еще нужно убедиться, что слова не используют буквы чаще, чем они появляются в коллекции. Например, слово "слабее" должно быть запрещено, потому что оно имеет три "е", тогда как в наборе букв RAEPKWAEN только два. Один только побитовый подход не отфильтрует это слово, так как каждая буква в слове появляется в коллекции.
- Предварительно проанализируйте словарь как отсортированный (слово), пары слов. (например, Гилнсту, лингвист)
- Сортировать файл словаря.
Затем, когда вы ищете заданный набор букв:
- Двоичный поиск по словарю для ваших букв, сортируя буквы в первую очередь.
Вам нужно будет сделать это отдельно для каждой длины слова.
РЕДАКТИРОВАТЬ: следует сказать, что вы ищете все уникальные комбинации отсортированных букв целевой длины слова (range(len(letters), 0, -1))
Я начал это прошлой ночью вскоре после того, как вы задали вопрос, но до сих пор не удосужился его отшлифовать. Это было мое решение, которое по сути является модифицированной, и о которой я не знал до сегодняшнего дня!
class Node(object):
__slots__ = ('words', 'letter', 'child', 'sib')
def __init__(self, letter, sib=None):
self.words = []
self.letter = letter
self.child = None
self.sib = sib
def get_child(self, letter, create=False):
child = self.child
if not child or child.letter > letter:
if create:
self.child = Node(letter, child)
return self.child
return None
return child.get_sibling(letter, create)
def get_sibling(self, letter, create=False):
node = self
while node:
if node.letter == letter:
return node
sib = node.sib
if not sib or sib.letter > letter:
if create:
node.sib = Node(letter, sib)
node = node.sib
return node
return None
node = sib
return None
def __repr__(self):
return '<Node({}){}{}: {}>'.format(chr(self.letter), 'C' if self.child else '', 'S' if self.sib else '', self.words)
def add_word(root, word):
word = word.lower().strip()
letters = [ord(c) for c in sorted(word)]
node = root
for letter in letters:
node = node.get_child(letter, True)
node.words.append(word)
def find_max_word(root, word):
word = word.lower().strip()
letters = [ord(c) for c in sorted(word)]
words = []
def grab_words(root, letters):
last = None
for idx, letter in enumerate(letters):
if letter == last: # prevents duplication
continue
node = root.get_child(letter)
if node:
words.extend(node.words)
grab_words(node, letters[idx+1:])
last = letter
grab_words(root, letters)
return words
root = Node(0)
with open('/path/to/dict/file', 'rt') as f:
for word in f:
add_word(root, word)
Тестирование:
>>> def nonrepeating_words():
... return find_max_word(root, 'abcdefghijklmnopqrstuvwxyz')
...
>>> sorted(nonrepeating_words(), key=len)[-10:]
['ambidextrously', 'troublemakings', 'dermatoglyphic', 'hydromagnetics', 'hydropneumatic', 'pyruvaldoxines', 'hyperabductions', 'uncopyrightable', 'dermatoglyphics', 'endolymphaticus']
>>> len(nonrepeating_words())
67590
Я думаю, что я предпочитаю дерматоглифику неконкурентоспособной для самого длинного слова, сам. С точки зрения производительности, используя словарь слов ~500k ( отсюда),
>>> import timeit
>>> timeit.timeit(nonrepeating_words, number=100)
62.8912091255188
>>>
Так, в среднем, 6/10 секунды (на моем i5-2500), чтобы найти все шестьдесят семь тысяч слов, которые не содержат повторяющихся букв.
Большие отличия между этой реализацией и деревом (что делает его еще более далеко от DAWG в целом) заключается в том, что слова сохраняются в дереве по отношению к их отсортированным буквам. Таким образом, слово "собака" хранится по тому же пути, что и "бог": dgo. Второй бит find_max_word Алгоритм, который обеспечивает посещение каждой возможной комбинации букв, постоянно отрывая голову и перезапуская поиск.
Ох, и просто для хихиканья
>>> sorted(tree.find_max_word('RAEPKWAEN'), key=len)[-5:]
['wakener', 'rewaken', 'reawake', 'reawaken', 'awakener']
Это похоже на проблему анаграммы, над которой я работал раньше. Я решил это, используя простые числа для представления каждой буквы. Произведение букв для каждого слова производит число. Чтобы определить, достаточен ли данный набор входных символов для выполнения работы, просто разделите произведение входного символа на произведение на число, которое вы хотите проверить. Если остатка нет, тогда достаточно ввести символы. Я реализовал это ниже. Выход:
$ python longest.py rasdaddea aosddna raepkwaen
rasdaddea --> sadder
aosddna --> soda
raepkwaen --> reawaken
Вы можете найти более подробную информацию и подробное объяснение случая анаграмм по адресу: http://mostlyhighperformance.blogspot.com/2012/01/generating-anagrams-efficient-and-easy.html
Этот алгоритм требует небольшого количества времени для настройки словаря, а затем отдельные проверки так же просты, как одно деление для каждого слова в словаре. Могут быть более быстрые методы, которые полагаются на закрытие частей словаря, если в нем отсутствует буква, но они могут в конечном итоге работать хуже, если у вас есть большое количество вводимых букв, поэтому он фактически не может закрыть какую-либо часть словаря.
import sys
def nextprime(x):
while True:
x += 1
for pot_fac in range(2,x):
if x % pot_fac == 0:
break
else:
return x
def prime_generator():
'''Returns a generator that produces the next largest prime as
compared to the one returned from this function the last time
it was called. The first time it is called it will return 2.'''
lastprime = 1
while True:
lastprime = nextprime(lastprime)
yield lastprime
# Assign prime numbers to each lower case letter
gen = prime_generator()
primes = dict( [ (chr(x),gen.next()) for x in range(ord('a'),ord('z')+1) ] )
product = lambda x: reduce( lambda m,n: m*n, x, 1 )
make_key = lambda x: product( [ primes[y] for y in x ] )
try:
words = open('words').readlines()
words = [ ''.join( [ c for c in x.lower() \
if ord('a') <= ord(c) <= ord('z') ] ) \
for x in words ]
for x in words:
try:
make_key(x)
except:
print x
raise
except IOError:
words = [ 'reawaken','awaken','enwrap','weaken','weaker', ]
words = dict( ( (make_key(x),x,) for x in words ) )
inputs = sys.argv[1:] if sys.argv[1:] else [ 'raepkwaen', ]
for input in inputs:
input_key = make_key(input)
results = [ words[x] for x in words if input_key % x == 0 ]
result = reversed(sorted(results, key=len)).next()
print input,'--> ',result
DAWG (направленный ациклический словесный граф) Марк Вутка был достаточно любезен, чтобы предоставить здесь некоторый паскаль-код.
При поиске слов длиной более 10 букв вы можете попытаться перебрать слова (я думаю, что не так много слов с 10 буквами), которые длиннее 10 букв, и проверьте, что в вашем наборе есть требуемые буквы.
Проблема в том, что вы должны сначала найти все эти слова (= слово) >= 10 слов.
Итак, что бы я сделал: при чтении словаря разделите слова на 2 категории: шорты и длинные. Вы можете обрабатывать шорты, повторяя каждую возможную перестановку. Чем вы можете обрабатывать длинные, повторяя и проверяя их, они возможны.
Конечно, существует много возможных оптимизаций для обоих путей.
- Создайте три (дерево префиксов) из вашего словаря. Вы можете кэшировать это.
- Пройдите по этому пути и удалите целые ветви, которые не соответствуют вашей сумке писем.
На данный момент ваша три представляет собой представление всех слов в вашем словаре, которые могут быть созданы из вашего пакета букв.
- Просто возьмите более длинный (ые):-)
Редактировать: вы также можете использовать DAGW (направленный график ациклических слов), у которого будет меньше вершин. Хотя я не читал ее, в этой статье в Википедии есть ссылка о самой быстрой в мире программе скрэббл.
Если у вас есть текстовый файл с отсортированными словами. Просто этот код делает математику:
UsrWrd = input() #here you Enter scrambled letters
with open('words.db','r') as f:
for Line in f:
for Word in Line.split():
if len(Word) == len(UsrWrd) and set(Word) == set(UsrWrd):
print(Word)
break
else:continue `