java - 如何优化搜索算法？

Question

所以基本上我的意思是我如何制作一个有用的搜索工具（比如搜索一系列字符串，可能在数组或数组列表中等）？不一定很快，但很有用。

例如，在您搜索的术语产生拼写相似但不准确的结果时，合并“自动更正”有多容易？或匹配前 3 个字符但不匹配整个单词的结果，或者可能包含该单词但不一定包含整个单词的结果？是否有这个或一个类的API，或者有一个算法可以帮助我吗？

Answer 1

简而言之，对于 SIMILAR 字符串，您可以使用“编辑距离”算法来查找相似性（实际上它会找到将一个字符串转换为另一个字符串的移动次数，但这是一种相似性），对于 AUTOCOMPLETE 工具，您可以使用“Trie”数据结构，它作为字符树工作，当它读取当前单词的字符时，它会停在一个节点上，该节点向您显示它还可以去哪里获取现有单词。要搜索包含单词（字符串）的内容，我想您可以使用 KMP 算法（或 Aho-Corasick，如果您希望在整个文本中搜索多个单词）。

https://en.wikipedia.org/wiki/Edit_distance

https://en.wikipedia.org/wiki/Trie

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm