实现一个简单的Trie以实现高效的Levenshtein距离计算 - Java

更新 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的steve Hanov算法的C++版本直接翻译过来的。那么我应该如何重构此算法和/或进行优化呢?下面是代码...

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 Automata工作,但我无法实现它。

因此,我正在寻找有关上述代码的重构和/或优化的建议。如果有任何混淆,请告诉我。与往常一样,我可以根据需要提供其余的源代码。


更新 1

因此,我实现了一个简单的Trie数据结构,并且我一直在尝试按照Steve Hanov的python教程来计算Levenshtein Distance。实际上,我对计算给定单词和Trie中的单词之间的最小Levenshtein距离感兴趣,因此我一直在遵循Murilo Vasconcelos版本的Steve Hanov算法。它不是很有效,但这是我的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的搜索,但是有些东西不对劲,我需要一些帮助来调试它。请就如何重构此内容和/或指出错误所在提供建议。我想重构的第一件事是“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);
        }
    }
}

我对缺乏评论表示歉意。那么我做错了什么呢?

初始职位

我一直在读一篇文章,使用Trie的快速和简单Levenshtein距离,希望找出一种有效的方法来计算两个字符串之间的Levenshtein距离。我这样做的主要目标是,给定一大组单词,能够找到输入单词和这组单词之间的最小Levenshtein距离。

在我简单的实现中,我计算每个输入单词的输入单词和单词集之间的Levenshtein距离,并返回最小值。它有效,但它效率不高...

我一直在Java中寻找Trie的实现,我遇到了两个看似不错的来源:

但是,这些实现对于我尝试执行的操作来说似乎太复杂了。当我一直在阅读它们以了解它们的工作原理以及Trie数据结构的一般工作方式时,我只是变得更加困惑。

那么,如何在Java中实现一个简单的Trie数据结构呢?我的直觉告诉我,每个TrieNode都应该存储它所代表的字符串,并引用字母表中的字母,而不一定是所有字母。我的直觉正确吗?

一旦实现,下一个任务就是计算Levenshtein距离。我通读了上面文章中的Python代码示例,但我不会说Python,一旦我点击递归搜索,我的Java实现就会耗尽堆内存。那么,我该如何使用Trie数据结构来计算Levenshtein距离呢?我有一个微不足道的实现,以这个源代码为模型,但它不使用Trie...这是低效的。

除了您的意见和建议之外,如果能看到一些代码,那将是非常好的。毕竟,这对我来说是一个学习的过程...我从未实施过Trie...所以我从这次经历中学到了很多东西。

谢谢。

p.s. 如果需要,我可以提供任何源代码。另外,我已经通读了并尝试按照Nick Johnson的博客中的建议使用BK-Tree,但它并不像我认为的那样有效......或者也许我的实现是错误的。


答案 1

据我所知,您不需要提高Levenshtein Distance的效率,您需要将字符串存储在一个结构中,该结构可以阻止您需要多次运行距离计算,即通过修剪搜索空间。

由于Levenshtein距离是一个度量,您可以使用任何利用三角形不等式的度量空间索引 - 您提到了BK树,但还有其他例如。有利点树、固定查询树、双扇区树、空间近似树。以下是他们的描述:

伯克哈德-凯勒树

节点按如下方式插入到树中:对于根节点,请从空间中选择一个任意元素;添加唯一的边缘标记子项,使得每个边缘的值是从透视到该元素的距离;递归应用,在边已存在时选择子项作为枢轴。

固定查询树

与BKT一样,除了:元素存储在叶子上;每个叶子都有多个元素;对于树的每个级别,使用相同的透视。

双扇树

每个节点包含两个透视元素及其覆盖半径(中心元素与其任何子树元素之间的最大距离);将最接近第一个透视图轴的元素和最接近第二个透视图的元素筛选为两个组,并从这些集递归生成两个子树。

空间近似树

最初,所有元素都在一个袋子里;选择任意元素作为枢轴;在枢轴范围内建立最近邻居的集合;将每个剩余的元素放入刚构建的集合中最接近它的元素的袋子中;以递归方式从此集合的每个元素形成子树。

有利位置树

从集合中选择一个枢轴;计算此枢轴与剩余集合的每个元素之间的中位数距离;将集合中的元素过滤为左和右递归子树,以便距离小于或等于中位数的元素形成左侧,较大的元素形成右侧。


答案 2

我已经在C++中实现了“使用Trie的快速和简单的Levenshtein距离”文章中描述的算法,并且它非常快。如果你想要(理解C++比Python更好),我可以在某个地方传递代码。

编辑:我把它贴在我的博客上。


推荐