java - 在大量字符串中搜索最接近的匹配项的最有效方法是什么？

Question

我有一个大文件(400K 行英文句子)，需要能够搜索并将每个句子与“输入”字符串(也是英文句子)进行比较。我不担心这个应用程序会占用内存；我正在寻找最快的方法来做到这一点。目前，我将它存储为一大串字符串，程序遍历所有字符串，一次一个，并比较每个字符串的汉密尔顿距离——“匹配”的是距离最短的字符串。有比这更快的东西吗？

Answer 1

此处使用的最佳数据结构是树。因为在树中，甚至是搜索树(它真的写得像“trie”)，运行时间肯定比列表小。您可以使用 TreeSet 的 java 实现，或者自己编写一个树的实现。搜索树或前缀树是搜索树，其中树的每个节点都是一个字符。一个小例子: you can find the image of the tree at the link /image/pmVCl.png

在这种情况下，如果你想找到/匹配“app”这个词，你只需要在整个树数据结构中进行 3 次迭代。这是我所知道的最有效的方法。