あなたが質問をした直後に昨夜これを始めましたが、今までそれを磨くことができませんでした. これが私の解決策でした。これは基本的に修正されたトライであり、今日まで知りませんでした!
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 万 7000 語をすべて見つけるのに、平均して 10 分の 6 秒 (私の i5-2500 では) かかります。
この実装とトライの大きな違い (これにより、一般的に DAWG からさらに遠ざかります) は次のとおりです。単語は、ソートされた文字に関連してトライに格納されます。したがって、'dog' という単語は 'god' と同じパス (dgo) に格納されます。2 番目のビットはfind_max_wordアルゴリズムです。このアルゴリズムは、継続的に先頭を切り落として検索を再実行することにより、考えられるすべての文字の組み合わせが確実にアクセスされるようにします。
ああ、そして笑いのために：
>>> sorted(tree.find_max_word('RAEPKWAEN'), key=len)[-5:]
['wakener', 'rewaken', 'reawake', 'reawaken', 'awakener']