java - 加速递归函数

Question

我正在开发这个拼写检查器，我用来向用户建议更正的方法之一是在单词中插入多个字符。这允许将诸如 exmpl 之类的单词更正为 example这是实际的代码:

public static Set<String> multiInsert(String word, int startIndex) {
    Set<String> result = new HashSet<>();

    //List of characters to insert
    String correction = "azertyuiopqsdfghjklmwxcvbnùûüéèçàêë";

    for (int i = startIndex; i <= word.length(); i++) {
        for (int j = i + 1; j <= word.length(); j++) {
            for (int k = 0; k < correction.length(); k++) {
                String newWord = word.substring(0, j) + correction.charAt(k) + word.substring(j);

                result.addAll(multiInsert(newWord, startIndex + 2));

                if(dico.contains(newWord)) result.add(newWord);
            }
        }
    }

    return result;
}

这个功能的问题是它需要很多时间来处理，特别是当单词很长或者我有太多单词需要纠正时。有没有更好的方法来实现这个功能或者优化它？

Answer 1

导致速度变慢的原因是您正在测试字典中没有的字符串。可能的拼写错误比字典中的单词还要多。你需要以字典为指导。

这是一般的拼写纠正问题。我有programmed it several times .

简而言之，该方法是将字典存储为 trie，并对 trie 进行有界深度优先遍历。在每一步中，您都会跟踪 trie 中的单词与原始单词之间的距离。每当该距离超过界限时，您就会修剪搜索。

所以你可以循环进行，每次都增加界限。首先，您将边界设置为 0，因此它只会找到完全匹配的结果。这相当于普通的trie搜索。如果没有产生匹配，则以 1 为界限再次进行行走。这将找到与原始单词距离为 1 的所有字典单词。如果没有产生任何结果，请将界限增加到 2，依此类推。(构成距离增量的是您选择的任何转换，例如插入、删除、替换或更一般的重写。)

性能受真实距离乘以字典大小的限制。除此之外，它在真实距离上是指数级的。由于每次步行的花费是前一次步行的一个因子，因此时间以最后一次步行为主，因此先前的步行不会增加太多时间。

将字典组织为字典树有一个优点，因为字典树只是有限状态机的一种特殊形式。您可以向其中添加子机来处理常见的前缀和后缀，而无需大规模扩展字典。考虑这些词:民族、民族、民族主义、民族主义、民族主义、民族主义……这样的话也许不常见，但也不是不可能。后缀 trie 可以轻松处理它们。类似的前缀，如 pre-、post-、un-、de-、in- 等。