实施简单的Trie来进行有效的Levenshtein距离计算
更新3
完成。 以下是最终通过我所有测试的代码。 再次，这是仿照Murilo Vasconcelo修改后的Steve Hanov算法。 感谢所有帮助！
/**
* 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
最后，我设法让这个工作适用于我的大多数测试用例。 我的实现实际上是Murilo的C ++版Steve Hanov算法的直接翻译。 那么我应该如何重构这个算法和/或进行优化？ 下面是代码...
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自动机工作，但我无法做到这一点。
所以我正在寻找关于上述代码重构和/或优化的建议。 请让我知道是否有任何混淆。 与往常一样，我可以根据需要提供其他源代码。
更新1
所以我实现了一个简单的Trie数据结构，并且一直试图按照Steve Hanov的python教程来计算Levenshtein距离。 实际上，我对计算给定单词和Trie中单词之间的最小 Levenshtein距离感兴趣，因此我一直遵循Murilo Vasconcelos的Steve Hanov算法的版本。 这不是很好，但这是我的特里班级：
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来实现搜索，但有些东西关闭，我需要一些帮助来调试。 请给出关于如何重构这个和/或指出错误的地方的建议。 我想重构的第一件事是“minCost”全局变量，但这是最小的事情。 无论如何，这是代码...
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距离，希望找出计算两个字符串之间Levenshtein距离的有效方法。 我的主要目标是给定一大组单词，以便能够找到输入单词和这组单词之间的最小Levenshtein距离。
在我微不足道的实现中，我计算每个输入单词的输入单词和单词集之间的Levenshtein距离，并返回最小值。 它可以工作，但效率不高
我一直在寻找Java的Trie的实现，并且我遇到了两个看似不错的来源：
但是，这些实现对于我所要做的事似乎太复杂了。 正如我一直在阅读它们以了解它们是如何工作以及Trie数据结构如何工作的，我只是变得更加困惑。
那么我将如何在Java中实现一个简单的Trie数据结构？ 我的直觉告诉我，每个TrieNode都应该存储它所表示的字符串，并且也引用字母表中的字母，而不一定是所有的字母。 我的直觉是否正确？
一旦实现，下一个任务就是计算Levenshtein距离。 我通过上面的文章中的Python代码示例进行了阅读，但我不会说Python，并且一旦我进行递归搜索，我的Java实现就会耗尽堆内存。 那么如何使用Trie数据结构计算Levenshtein距离？ 我有一个简单的实现，仿照此源代码，但它不使用Trie ...它效率低下。
除了您的意见和建议之外，还能看到一些代码真的很棒。 毕竟，这对我来说是一个学习过程......我从来没有实施过Trie ......所以我有很多东西可以借鉴这个经验。
谢谢。
ps我可以根据需要提供任何源代码。 另外，我已经阅读并尝试使用Nick Johnson博客中提出的BK-Tree，但其效率并不如我想的那么高......或者也许我的实现是错误的。
我用C ++实现了“使用Trie快速简单的Levenshtein距离”中描述的算法，它非常快速。 如果你想（比Python更好地理解C ++），我可以在某处将代码过去。
编辑：我张贴在我的博客。
根据我可以告诉你不需要提高Levenshtein距离的效率，您需要将您的字符串存储在一个结构中，以防止您需要多次运行距离计算，即通过修剪搜索空间。
由于Levenshtein距离是一个度量标准，因此您可以使用任何利用三角不等式的度量空间索引 - 您提到了BK-Trees，但还有其他例如。 有利点树，固定查询树，平分线树，空间近似树。 这里是他们的描述：
Burkhard-Keller树
将节点插入树中，如下所示：为根节点从空间中选择一个任意元素; 添加独特的边缘标记的子元素，使得每个边的值是从该元素到该元素的距离; 以递归方式应用，当边缘已经存在时选择儿童作为支点。
固定查询树
和BKT一样，除了：元素存储在叶子上; 每片叶子有多个元素; 对于树的每个级别，使用相同的枢轴。
平分线树
每个节点包含两个枢轴元素，其覆盖半径（中心元素与其任何子树元素之间的最大距离）; 将最接近第一个元素的元素和最接近第二个元素的元素筛选到两个集合中，并从这些集合中递归地构建两个子树。
空间近似树
最初所有的元素都在一个袋子里; 选择一个任意元素作为支点; 在枢轴的范围内构建最近邻居的集合; 将每个剩余的元素放入刚刚构建的集合中距离它最近的元素的包中; 递归地从该集合的每个元素形成一个子树。
有利点树
愉快地从集合中选择一个支点; 计算这个枢轴和剩余集合中每个元素之间的中值距离; 将集合中的元素过滤为左和右递归子树，以使距离小于或等于中值的元素形成左侧，右侧的大于右侧。
下面是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 /测试/组织/阿帕奇/ 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");
上一篇: Implementing a simple Trie for efficient Levenshtein Distance calculation