Я начал это прошлой ночью вскоре после того, как вы задали вопрос, но до сих пор не полировал его до полировки.Это было мое решение, которое по сути представляет собой модифицированный три, о котором я не знал до сегодняшнего дня!
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
Я думаю, что я предпочитаю дерматоглифику неконкурентоспособной дольшеслово, яС точки зрения производительности, используя словарь ~ 500 000 слов (из здесь ),
>>> 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']