我目前正在为术语 Web 服务实现模糊搜索，并且正在寻找有关如何改进当前实现的建议。分享的代码太多，但我认为一个解释可能足以引发深思熟虑的建议。我意识到要阅读的内容很多，但我会很感激任何帮助。
首先，术语基本上只是一些名称（或术语）。对于每个单词，我们按空格将其拆分为标记，然后遍历每个字符以将其添加到 trie 中。在终端节点上（例如当到达草莓中的字符 y 时），我们将主术语列表的索引存储在列表中。所以一个终端节点可以有多个索引（因为草莓的终端节点将匹配“草莓”和“草莓过敏”）。
至于实际搜索，搜索查询也被空格分解为标记。为每个令牌运行搜索算法。搜索标记的第一个字符必须是匹配的（因此 traw 永远不会匹配草莓）。之后，我们遍历每个连续节点的子节点。如果有匹配字符的子元素，我们继续使用搜索标记的下一个字符进行搜索。如果孩子与给定字符不匹配，我们使用搜索标记的当前字符查看孩子（因此不推进它）。这是模糊部分，所以 'stwb' 将匹配 'strawberry'。
当我们到达搜索标记的末尾时，我们将在该节点搜索剩余的 trie 结构以获取所有潜在匹配项（因为主术语列表的索引仅在终端节点上）。我们称之为汇总。我们通过在 BitSet 上设置它们的值来存储索引。然后，我们简单地和 BitSets 从结果中搜索每个 token 的结果。然后，我们从 anded BitSet 中获取前 1000 或 5000 个索引，并找到它们对应的实际术语。我们使用 Levenshtein 对每个术语进行评分，然后按分数排序以获得最终结果。
这工作得很好，而且速度很快。树中有超过 39 万个节点和超过 110 万个实际术语名称。但是，就目前情况而言，存在一些问题。
例如，搜索“car cat”将返回导管化，当我们不希望它返回时（由于搜索查询是两个单词，结果应该至少是两个）。这很容易检查，但它不处理像导管插入术这样的情况，因为它是两个词。理想情况下，我们希望它与心导管术等相匹配。
基于纠正这个问题的需要，我们提出了一些改变。一方面，我们在混合深度/广度搜索中遍历 trie。本质上，只要字符匹配，我们就会先深入。那些不匹配的子节点被添加到优先级队列中。优先级队列按编辑距离排序，可以在搜索trie时计算（因为如果有字符匹配，距离保持不变，如果没有，它增加1）。通过这样做，我们得到了每个单词的编辑距离。我们不再使用 BitSet。相反，它是索引到 Terminfo 对象的映射。该对象存储查询短语和术语短语的索引和分数。因此，如果搜索是“car cat”并且匹配的词是“Catheterization procedure” 术语短语索引将是 1，查询短语索引也是如此。对于“心导管术”，术语短语索引将是 1,2，查询短语索引也是如此。如您所见，之后查看术语短语索引和查询短语索引的计数非常简单，如果它们至少不等于搜索字数，则可以丢弃它们。
之后，我们将词的编辑距离相加，从词中剔除匹配词组索引的词，统计剩余的字母，得到真正的编辑距离。例如，如果您匹配术语“对草莓过敏”并且您的搜索查询是“稻草”，那么草莓的得分为 7，那么您将使用术语短语索引从术语中丢弃草莓，然后计算“过敏”（减去空格）得到 16 分。
这让我们得到了我们期望的准确结果。但是，它太慢了。以前我们可以在一个单词搜索上获得 25-40 毫秒，现在它可能长达半秒。它主要来自于实例化 TermInfo 对象、使用 .add() 操作、.put() 操作以及我们必须返回大量匹配项的事实。我们可以将每次搜索限制为仅返回 1000 个匹配项，但不能保证“car”的前 1000 个结果与“cat”的前 1000 个匹配项中的任何一个匹配（请记住，有超过 110 万个术语）。
即使对于单个查询词，例如 cat，我们仍然需要大量匹配。这是因为如果我们搜索“cat”，搜索将匹配 car 并汇总它下面的所有终端节点（这将是很多）。但是，如果我们限制结果的数量，则会过于强调以查询开头的单词而不是编辑距离。因此，像导管插入这样的词比像外套这样的词更有可能被包括在内。
那么，基本上，对于我们如何处理第二个实现解决的问题，但又没有它引入的速度减慢多少，我们有什么想法吗？如果可以使事情更清楚，我可以包含一些选定的代码，但我不想发布一堵巨大的代码墙。