Java：查找相似的字符串

Question

我有一个包含很多字符串的 java 列表（如果需要，它可以是地图）。

列表（你好，地狱，汽车，卡通，...）

我想以高效的方式为另一个给定字符串找到最相似的字符串。

我想我应该使用 Levenshtein 距离，但我不想遍历所有列表。

您认为将主列表分成一些具有共同前缀的部分是个好主意吗？

然后我会有一个以前缀为键、以列表为值的映射：

hel -> 列表(hello,hell,...)
汽车 -> 列表（汽车、卡通、...）

这样我可以快速搜索与搜索到的字符串具有相同前缀的字符串。然后我可以只对一些字符串而不是所有主列表应用 Levenshtein 距离。

这是个好主意吗？谢谢

Answer 1

您可以一次计算每个词条的soundex代码，并将soundex映射到原始单词列表。 Soundex 是一个简化代码，可以为相似发音的单词获取一个键。

Map<String, Set<String>> soundexToWords = ...
for (String word : words) {
    String sdex = soundex(word);
    Set<String> similarWords = soundexToWords.get(sdex));
    if (similarWords == null) {
        similarWords = new HashSet<>();
        soundexToWords.put(sdex, similarWords);
    }
    similarWords.add(word);
}

Set<String> similarWords(String word) {
    return soundexToWords.get(soundex(word));
}

Soundex 通常用于一种语言，比如英语，尤其是对于英语，它是相当简化的。

Answer 2

简单的解决方案

最简单的解决方案是先在您的 List 上调用 Collections.sort()。现在您的列表已按 lexicographical order 排序。接下来，对列表执行二进制搜索以查找您的前缀所属的位置。返回的索引基本上为您提供了最相似词的位置。

然后您可以通过将前缀映射到索引来构造您的地图，这样您就可以根据需要检索整体 List 的子集，或者您可以将子集本身缓存在地图中。该子集是一个列表，从整体 List 中的该索引开始，其元素具有递减的相似性。您可以将停止索引微调为一旦第一个字母递增或类似的东西。

最佳解决方案

最好的解决办法是看看trie数据结构。 trie 支持 O(m) 查询，其中 m 是您要搜索的前缀的长度。这占用 少得多 space 并且避免哈希冲突。虽然您的地图理论上支持 O(1) 查询，但如果您明确存储每个列表，构建时间为 O(n^2)。如果存储索引，构建时间是线性的，但是每个请求都是 O(n).

Answer 3

public List<String> similarWords(String word, List<String> allWords){
    List<String> similarWordList = new ArrayList<>();

    for(String currentWord : allWords){
        if(currentWord.contains(word)){
            similarWordList.add(currentWord);
        }
    }
    return similarWordList;
}

Java：查找相似的字符串

Java: Find similar strings

java

performance

similarity

levenshtein-distance

简单的解决方案

最佳解决方案