1

我对数据结构有点陌生，我正在尝试使用编辑距离来消除名称数据库的歧义。我正在使用 trie 的以下实现：

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 )

这很好地完成了这项工作，因为它将所有名称插入到 trie 中。现在，我逐个浏览我拥有的名称列表，并使用 trie 返回与传递的名称有一定编辑距离的所有名称的列表。然后，我想从列表中返回的 trie 中删除所有名称。

有没有快速的方法来做到这一点？

谢谢！

4

1 回答 1

1

有两种方法可以做到这一点，具体取决于您是否要检查是否要删除通过任何内部节点的最后一条路径（这会使删除速度稍慢，但可能会使删除后的搜索速度稍快一些）。两种方法都可以递归执行，但是如果您想迭代地展开它（就像您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

你能让这个更快吗？是的，但这可能无关紧要。

首先，您知道节点将始终存在，因此您可以删除一些错误检查。更重要的是，如果你可以让搜索函数返回节点，而不仅仅是它们的值，那会让事情变得更快一些。如果您可以在 trie 中添加反向链接，这意味着您可以在恒定时间内擦除节点，而不是重复搜索。如果您不希望在 trie 中反向链接，则可以通过返回拉链而不是节点来获得完全相同的好处，或者更简单地说，只返回一堆节点。

但实际上，这里最坏的情况只是将工作加倍，而不是增加算法复杂性或乘以一个很大的因子，所以简单可能会获胜。

于 2013-07-31T20:20:04.660 回答