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

Question

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

标签： javastringsearchdocument

Answer 1

此处使用的最佳数据结构是树。因为在树中，甚至是 search-trie（它实际上写成“trie”）的运行时间肯定比列表的运行时间要小。您可以使用 TreeSet 的 java 实现，或者自己编写一个树的实现。搜索树或前缀树是搜索树，其中树的每个节点都是一个字符。一个小例子： 您可以在链接 https://i.stack.imgur.com/pmVCl.png 找到树的图像

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