1

私はデータ構造が初めてで、編集距離を使用して名前のデータベースを明確にする試みを実装しています。私はトライの次の実装を使用しています:

http://stevehanov.ca/blog/index.php?id=114

これは基本的に次のとおりです。

class TrieNode:

    def __init__(self):
       self.word = None
       self.children = {}

       global NodeCount
       NodeCount += 1

    def insert( self, word ):
       node = self
       for letter in word:
            if letter not in node.children: 
                node.children[letter] = TrieNode()

            node = node.children[letter]

       node.word = word

# read dictionary file into a trie
trie = TrieNode()
for name in names:
    WordCount += 1
    trie.insert( name )

これは、すべての名前をトライに挿入するので、うまく機能します。ここで、持っている名前のリストを 1 つずつ調べ、トライを使用して、渡された名前から特定の編集距離にあるすべての名前のリストを返します。次に、リストに返されたトライからすべての名前を削除したいと思います。

それを行うための速い方法はありますか？

ありがとう！

4

1 に答える 1

1

内部ノードを通る最後のパスを削除するかどうかを確認するかどうかに応じて、これを行うには 2 つの方法があります (これにより、削除が少し遅くなりますが、削除後の検索が少し速くなる可能性があります)。どちらの方法も再帰的に行うのは簡単ですが、（あなたのように）繰り返し展開したい場合はinsert、チェックしないほうが簡単なので、そうします。

def delete(self, word):
    node = self
    for letter in word[:-1]:
        if letter not in node.children:
            return False
        node = node.children[letter]
    if word[-1] in node.children:
        del node.children[letter]
        return True
    return False

これを速くすることはできますか？はい、しかしそれは問題ではないかもしれません。

まず、ノードが常に存在することがわかっているので、エラー チェックの一部を削除できます。さらに重要なことは、検索関数がノードの値だけでなくノードを返すようにできれば、処理が少し速くなるということです。トライにバックリンクを追加できれば、検索を繰り返す代わりに一定時間でノードを消去できるということです。トライのバックリンクを望まない場合は、ノードの代わりにジッパーを返すか、より単純にノードのスタックを返すことで、まったく同じ利点を得ることができます。

しかし、実際には、ここでの最悪のケースは、作業を 2 倍にすることであり、アルゴリズムの複雑さを増したり、大きな係数を掛けたりすることではないため、単純な方がおそらく勝ちます。

于 2013-07-31T20:20:04.660 に答える