实现简单的Trie来实现高效的Levenshtein距离计算 – Java
更新3
完成。 以下是最终通过我所有的testing代码。 再次，这是仿照Murilo Vasconcelo的修改后的史蒂夫·哈诺夫的algorithm。 感谢所有帮助！
/** * Computes the minimum Levenshtein Distance between the given word (represented as an array of Characters) and the * words stored in theTrie. This algorithm is modeled after Steve Hanov's blog article "Fast and Easy Levenshtein * distance using a Trie" and Murilo Vasconcelo's revised version in C++. * * http://stevehanov.ca/blog/index.php?id=114 * http://murilo.wordpress.com/2011/02/01/fast-and-easy-levenshtein-distance-using-a-trie-in-c/ * * @param ArrayList<Character> word - the characters of an input word as an array representation * @return int - the minimum Levenshtein Distance */ private int computeMinimumLevenshteinDistance(ArrayList<Character> word) { theTrie.minLevDist = Integer.MAX_VALUE; int iWordLength = word.size(); int[] currentRow = new int[iWordLength + 1]; for (int i = 0; i <= iWordLength; i++) { currentRow[i] = i; } for (int i = 0; i < iWordLength; i++) { traverseTrie(theTrie.root, word.get(i), word, currentRow); } return theTrie.minLevDist; } /** * Recursive helper function. Traverses theTrie in search of the minimum Levenshtein Distance. * * @param TrieNode node - the current TrieNode * @param char letter - the current character of the current word we're working with * @param ArrayList<Character> word - an array representation of the current word * @param int[] previousRow - a row in the Levenshtein Distance matrix */ private void traverseTrie(TrieNode node, char letter, ArrayList<Character> word, int[] previousRow) { int size = previousRow.length; int[] currentRow = new int[size]; currentRow[0] = previousRow[0] + 1; int minimumElement = currentRow[0]; int insertCost, deleteCost, replaceCost; for (int i = 1; i < size; i++) { insertCost = currentRow[i - 1] + 1; deleteCost = previousRow[i] + 1; if (word.get(i - 1) == letter) { replaceCost = previousRow[i - 1]; } else { replaceCost = previousRow[i - 1] + 1; } currentRow[i] = minimum(insertCost, deleteCost, replaceCost); if (currentRow[i] < minimumElement) { minimumElement = currentRow[i]; } } if (currentRow[size - 1] < theTrie.minLevDist && node.isWord) { theTrie.minLevDist = currentRow[size - 1]; } if (minimumElement < theTrie.minLevDist) { for (Character c : node.children.keySet()) { traverseTrie(node.children.get(c), c, word, currentRow); } } } 更新2
最后，我已经设法使这个工作适用于我的大多数testing用例。 我的实现实际上是从Murilo的C ++版 Steve Hanovalgorithm的直接翻译。 那么我应该如何重构这个algorithm和/或进行优化呢？ 以下是代码…
public int search(String word) { theTrie.minLevDist = Integer.MAX_VALUE; int size = word.length(); int[] currentRow = new int[size + 1]; for (int i = 0; i <= size; i++) { currentRow[i] = i; } for (int i = 0; i < size; i++) { char c = word.charAt(i); if (theTrie.root.children.containsKey(c)) { searchRec(theTrie.root.children.get(c), c, word, currentRow); } } return theTrie.minLevDist; } private void searchRec(TrieNode node, char letter, String word, int[] previousRow) { int size = previousRow.length; int[] currentRow = new int[size]; currentRow[0] = previousRow[0] + 1; int insertCost, deleteCost, replaceCost; for (int i = 1; i < size; i++) { insertCost = currentRow[i - 1] + 1; deleteCost = previousRow[i] + 1; if (word.charAt(i - 1) == letter) { replaceCost = previousRow[i - 1]; } else { replaceCost = previousRow[i - 1] + 1; } currentRow[i] = minimum(insertCost, deleteCost, replaceCost); } if (currentRow[size - 1] < theTrie.minLevDist && node.isWord) { theTrie.minLevDist = currentRow[size - 1]; } if (minElement(currentRow) < theTrie.minLevDist) { for (Character c : node.children.keySet()) { searchRec(node.children.get(c), c, word, currentRow); } } }
谢谢大家对这个问题的贡献。 我试图让Levenshtein自动机工作，但我不能做到这一点。
所以我正在寻找关于上述代码重构和/或优化的build议。 请让我知道是否有任何混淆。 和往常一样，我可以根据需要提供其余的源代码。
更新1
所以我实现了一个简单的Trie数据结构，我一直在试图按照Steve Hanov的python教程来计算Levenshtein距离。 实际上，我对计算给定单词和Trie单词之间的最小 Levenshtein距离感兴趣，因此我一直遵循Murilo Vasconcelos的Steve Hanovalgorithm 。 这不是很好，但这是我的Trie类：
public class Trie { public TrieNode root; public int minLevDist; public Trie() { this.root = new TrieNode(' '); } public void insert(String word) { int length = word.length(); TrieNode current = this.root; if (length == 0) { current.isWord = true; } for (int index = 0; index < length; index++) { char letter = word.charAt(index); TrieNode child = current.getChild(letter); if (child != null) { current = child; } else { current.children.put(letter, new TrieNode(letter)); current = current.getChild(letter); } if (index == length - 1) { current.isWord = true; } } } }
…和TrieNode类：
public class TrieNode { public final int ALPHABET = 26; public char letter; public boolean isWord; public Map<Character, TrieNode> children; public TrieNode(char letter) { this.isWord = false; this.letter = letter; children = new HashMap<Character, TrieNode>(ALPHABET); } public TrieNode getChild(char letter) { if (children != null) { if (children.containsKey(letter)) { return children.get(letter); } } return null; } }
现在，我尝试着像Murilo Vasconcelos那样实现search，但是有些东西是closures的，我需要一些帮助来debugging它。 请给出关于如何重构和/或指出错误的地方的build议。 我想重构的第一件事是“minCost”全局variables，但这是最小的事情。 无论如何，这是代码…
public void search(String word) { int size = word.length(); int[] currentRow = new int[size + 1]; for (int i = 0; i <= size; i++) { currentRow[i] = i; } for (int i = 0; i < size; i++) { char c = word.charAt(i); if (theTrie.root.children.containsKey(c)) { searchRec(theTrie.root.children.get(c), c, word, currentRow); } } } private void searchRec(TrieNode node, char letter, String word, int[] previousRow) { int size = previousRow.length; int[] currentRow = new int[size]; currentRow[0] = previousRow[0] + 1; int replace, insertCost, deleteCost; for (int i = 1; i < size; i++) { char c = word.charAt(i - 1); insertCost = currentRow[i - 1] + 1; deleteCost = previousRow[i] + 1; replace = (c == letter) ? previousRow[i - 1] : (previousRow[i - 1] + 1); currentRow[i] = minimum(insertCost, deleteCost, replace); } if (currentRow[size - 1] < minCost && !node.isWord) { minCost = currentRow[size - 1]; } Integer minElement = minElement(currentRow); if (minElement < minCost) { for (Map.Entry<Character, TrieNode> entry : node.children.entrySet()) { searchRec(node, entry.getKey(), word, currentRow); } } }
我对缺乏评论表示歉意。 那么我做错了什么？
初始POST
我一直在用Trie阅读一篇文章“ 快速简单的Levenshtein距离” ，希望find一种有效的方法来计算两个string之间的Levenshtein距离 。 我的主要目的是给出一大组单词，以便能够findinput单词和这组单词之间的最小Levenshtein距离。
在我微不足道的实现中，我计算每个input词的input词和词集之间的Levenshtein距离，并返回最小值。 它可以工作，但效率不高
我一直在寻找Java的Trie的实现，并且我遇到了两个看似不错的来源：
- Koders.com版本
- code.google.com版本
但是，这些实现看起来太复杂，我试图做的。 正如我一直在阅读他们了解他们如何工作以及Trie数据结构如何工作，我只是变得更加困惑。
那么我将如何在Java中实现一个简单的Trie数据结构呢？ 我的直觉告诉我，每个TrieNode都应该存储它所代表的string，并且也引用字母表中的字母，而不一定是所有的字母。 我的直觉是否正确？
一旦实现，下一个任务就是计算Levenshtein距离。 我通过上面的文章中的Python代码示例进行了阅读，但我不会说Python，并且一旦我进行recursionsearch，我的Java实现将耗尽堆内存。 那么如何使用Trie数据结构计算Levenshtein距离呢？ 我有一个简单的实现，仿照这个源代码 ，但它不使用Trie …这是低效的。
除了您的意见和build议之外，还能看到一些代码真的很棒。 毕竟，这对我来说是一个学习过程…我从来没有实施过Trie …所以我有很多东西要从这个经验中学习。
谢谢。
ps我可以提供任何源代码，如果需要的话。 此外，我已经阅读并尝试使用尼克·约翰逊博客中提出的BK-Tree，但是效率不如我想的那么高……或者也许我的实现是错误的。
我已经实现了在C ++中使用Trie快速简单的Levenshtein距离描述的algorithm，它非常快。 如果你想（理解C ++比Python更好），我可以把代码放在某个地方。
编辑：我张贴在我的博客 。
从我可以告诉你不需要提高Levenshtein距离的效率来说，你需要把你的string存储在一个结构中，这样你就不用多次执行距离计算，比如修剪search空间。
由于Levenshtein距离是度量标准，因此可以使用任何利用三angular不等式的度量空间索引 – 您提到了BK-Trees，但还有其他的例如。 有利点树，固定查询树，平分线树，空间近似树。 这里是他们的描述：
Burkhard-Keller树
将节点插入到树中，如下所示：为根节点从空间中select一个任意元素; 添加独特的边缘标记的孩子，使每个边的值是从枢轴到该元素的距离; recursion地应用，当边缘已经存在时select儿童作为枢轴。
固定查询树
和BKT一样，除了：元素存储在叶子上; 每片叶子有多个元素; 对于树的每个级别，使用相同的枢轴。
平分线树
每个节点包含两个枢轴元素，其覆盖半径（中心元素与其任何子树元素之间的最大距离）; 将两个最接近第一个元素的元素和最接近第二个元素的元素过滤到两个集合中，并从这些集合中recursion地构build两个子树。
空间近似树
最初所有的元素都在一个袋子里; select一个任意元素作为支点; 在枢轴的范围内build立最近邻居的集合; 把剩下的每一个元素都放入刚build好的集合中最近的元素的包中; recursion地从这个集合的每个元素形成一个子树。
有利点树
从集合中select一个枢轴; 计算这个枢轴和剩余集合的每个元素之间的中值距离; 将集合中的元素过滤为左recursion子树和右recursion子树，以使距离小于或等于中间值的元素形成左侧，右侧大于右侧。
下面是Java中的Levenshtein自动机的一个例子。这可能也是有帮助的：
http://svn.apache.org/repos/asf/lucene/dev/trunk/lucene/src/java/org/apache/lucene/util/automaton/ http://svn.apache.org/repos/asf/的lucene的/ dev /中继/ lucene的/ SRC /testing/组织/阿帕奇/ lucene的/ util的/自动机/
它看起来像实验Lucene代码是基于dk.brics.automaton包。
用法似乎如下所示：
LevenshteinAutomata builder = new LevenshteinAutomata(s); Automaton automata = builder.toAutomaton(n); boolean result1 = BasicOperations.run(automata, "foo"); boolean result2 = BasicOperations.run(automata, "bar");
在很多方面，Steve Hanov的algorithm（在第一篇文章中提到， 使用Trie快速简单的Levenshtein距离 ），Murilo和你（OP）algorithm的端口，以及很可能涉及到的每个相关algorithmTrie或类似的结构，就像一个Levenshtein自动机（在这里已经提到好几次）的function一样：
Given: dict is a dictionary represented as a DFA (ex. trie or dawg) dictState is a state in dict dictStartState is the start state in dict dictAcceptState is a dictState arrived at after following the transitions defined by a word in dict editDistance is an edit distance laWord is a word la is a Levenshtein Automaton defined for laWord and editDistance laState is a state in la laStartState is the start state in la laAcceptState is a laState arrived at after following the transitions defined by a word that is within editDistance of laWord charSequence is a sequence of chars traversalDataStack is a stack of (dictState, laState, charSequence) tuples Define dictState as dictStartState Define laState as laStartState Push (dictState, laState, "") on to traversalDataStack While traversalDataStack is not empty Define currentTraversalDataTuple as the the product of a pop of traversalDataStack Define currentDictState as the dictState in currentTraversalDataTuple Define currentLAState as the laState in currentTraversalDataTuple Define currentCharSequence as the charSequence in currentTraversalDataTuple For each char in alphabet Check if currentDictState has outgoing transition labeled by char Check if currentLAState has outgoing transition labeled by char If both currentDictState and currentLAState have outgoing transitions labeled by char Define newDictState as the state arrived at after following the outgoing transition of dictState labeled by char Define newLAState as the state arrived at after following the outgoing transition of laState labeled by char Define newCharSequence as concatenation of currentCharSequence and char Push (newDictState, newLAState, newCharSequence) on to currentTraversalDataTuple If newDictState is a dictAcceptState, and if newLAState is a laAcceptState Add newCharSequence to resultSet endIf endIf endFor endWhile
Steve Hanov的algorithm及其上述衍生物显然使用Levenshtein距离计算matrix来代替正式的Levenshtein自动机。 相当快，但是一个正式的Levenshtein自动机可以有其参数状态 （描述自动机的具体状态的抽象状态） 生成并用于遍历，绕过任何与编辑距离有关的运行时计算。 所以，它应该比上述algorithm运行得更快。
如果您（或任何其他人）对正式的Levenshtein自动机解决scheme感兴趣，请查看LevenshteinAutomaton 。 它实现了前述的基于参数状态的algorithm，以及纯粹的基于混沌状态遍历的algorithm（上面概述）和基于dynamic规划的algorithm（用于编辑距离和邻居确定）。 它是由你真正保持:)。
我的直觉告诉我，每个TrieNode都应该存储它所代表的string，并且也引用字母表中的字母，而不一定是所有的字母。 我的直觉是否正确？
不，一个trie不代表一个String，它代表一组string（及其所有前缀）。 trie节点将input字符映射到另一个trie节点。 所以它应该像一个字符数组和一个相应的TrieNode引用数组。 （也许不是那个确切的表示，取决于你的特定使用效率。）
正如我所看到的，你想循环所有的树枝。 使用recursion函数并不困难。 我在我的k最近邻algorithm中也使用了一个trie，使用相同types的函数。 我不知道Java，但是这里有一些伪代码：
function walk (testitem trie) make an empty array results function compare (testitem children distance) if testitem = None place the distance and children into results else compare(testitem from second position, the sub-children of the first child in children, if the first item of testitem is equal to that of the node of the first child of children add one to the distance (! non-destructive) else just the distance) when there are any children left compare (testitem, the children without the first item, distance) compare(testitem, children of root-node in trie, distance set to 0) return the results
希望能帮助到你。
函数walk需要一个testitem（例如一个可索引string或一个字符数组）和一个trie。 一个特里可以是一个有两个插槽的对象。 一个指定该树的节点，另一个指定该节点的子节点。 孩子们也尝试。 在Python中，它会是这样的：
class Trie(object): def __init__(self, node=None, children=[]): self.node = node self.children = children
或者在Lisp中…
(defstruct trie (node nil) (children nil))
现在一个特里看起来像这样：
(trie #node None #children ((trie #node f #children ((trie #node o #children ((trie #node o #children None))) (trie #node u #children ((trie #node n #children None)))))))
现在内部函数（你也可以单独写）取得testitem，树的根节点的子节点（节点值为None或其他），初始距离设为0。
然后，我们只是recursion遍历树的两个分支，从左到右，然后开始。
我会留在这里以防万一任何人正在寻找这个问题的又一个处理：
http://code.google.com/p/oracleofwoodyallen/wiki/ApproximateStringMatching
我正在看你的最新更新3，algorithm似乎不适合我。
让我们看看你有以下的testing用例：
Trie dict = new Trie(); dict.insert("arb"); dict.insert("area"); ArrayList<Character> word = new ArrayList<Character>(); word.add('a'); word.add('r'); word.add('c');
在这种情况下， "arc"和字典之间的最小编辑距离应该是"arc"和"arb"之间的编辑距离1，但是您的algorithm将返回2。
我经历了下面的代码块：
if (word.get(i - 1) == letter) { replaceCost = previousRow[i - 1]; } else { replaceCost = previousRow[i - 1] + 1; }
至less在第一个循环中，字母是单词中的一个字符，相反，您应该比较单词中的节点，所以会有一行与单词中的第一个字符重复，是吗？ 每个DPmatrix具有第一行作为副本。 我执行完全相同的代码，你把解决scheme。
好吧， 这是我很久以前做的。 我把字典存储为一个trie，它只是一个限于树形的有限状态机。 你可以通过不做这个限制来加强它。 例如，常见的后缀可以简单地是一个共享的子树。 你甚至可以有循环，捕捉像“国家”，“国家”，“国有化”，“国有化”，…
保持trie尽可能简单。 不要在其中填充string。
请记住，您不要这样做来查找两个给定string之间的距离。 您可以使用它来查找字典中与给定string最接近的string。 所花费的时间取决于你可以忍受多lesslevenshtein距离。 对于零距离，简单地说是O（n），其中n是字长。 对于任意距离，它是O（N），其中N是字典中单词的数量。
纠正我，如果我错了，但我相信你的update3有一个额外的循环是不必要的，使程序慢得多：
for (int i = 0; i < iWordLength; i++) { traverseTrie(theTrie.root, word.get(i), word, currentRow); }
你只能调用traverseTrie一次，因为在traverseTrie中你已经循环了整个单词。 代码应该如下所示：
traverseTrie(theTrie.root, ' ', word, currentRow);
