我目前正在为术语Web服务实现模糊搜索，并且正在寻找有关如何改进当前实现的建议。太多的代码无法共享，但是我认为做出解释可能足以引起深思熟虑的建议。我知道要阅读很多东西，但我会很感激。
首先，术语基本上只是一些名称(或术语)。对于每个单词，我们将其按空格分成多个标记，然后遍历每个字符以将其添加到trie中。在终端节点上(例如，到达草莓中的字符y时)，我们在列表中存储主术语列表的索引。因此，终端节点可以具有多个索引(因为草莓的终端节点将匹配“草莓”和“对草莓过敏”)。
至于实际的搜索，搜索查询也按空间分为标记。搜索算法针对每个 token 运行。搜索 token 的第一个字符必须是一个匹配项(因此，traw将永远不会匹配strawberry)。之后，我们遍历每个连续节点的子节点。如果有一个 child 具有匹配的字符，我们将使用搜索 token 的下一个字符继续搜索。如果 child 与给定字符不匹配，我们将使用搜索 token 的当前字符来查看 child (因此请不要前进)。这是模糊性部分，因此“stwb”将与“strawberry”匹配。
当我们到达搜索 token 的末尾时，我们将在该节点上搜索其余的trie结构，以获取所有可能的匹配项(因为主术语列表的索引仅在终端节点上)。我们称此为汇总。我们通过在BitSet上设置索引值来存储索引。然后，我们简单地从每个搜索 token 结果的结果中获取BitSets。然后，我们从“与”后的BitSet中获取前1000或5000个索引，并找到它们所对应的实际术语。我们使用Levenshtein对每个术语评分，然后按分数排序以获得最终结果。
这工作得很好并且非常快。树中有超过39万个节点，超过110万个实际术语名称。但是，目前存在问题。
例如，搜索“车猫”将返回“导管插入”，而我们不希望这样做(由于搜索查询是两个单词，因此结果至少应为两个)。这将很容易检查，但是并不需要像“导管插入术”这样的情况，因为这是两个字。理想情况下，我们希望它与“心脏导管插入术”相匹配。
根据需要对此进行更正，我们提出了一些更改。首先，我们在混合的深度/宽度搜索中遍历树。本质上，只要角色匹配，我们就会首先深入。那些不匹配的子节点将被添加到优先级队列中。优先级队列按编辑距离排序，该距离可在搜索Trie时计算(由于存在字符匹配，因此距离保持不变，否则，距离增加1)。这样，我们得到每个单词的编辑距离。
我们不再使用BitSet。相反，它是索引到Terminfo对象的映射。该对象存储查询短语和术语短语以及分数的索引。因此，如果搜索是“汽车猫”，匹配的术语是“导管插入程序”，则术语短语索引将为1，查询短语索引也将为1。对于“心脏导管插入术”，术语短语索引将为1,2，而查询短语索引也将为1,2。如您所见，之后查看术语短语索引和查询短语索引的计数非常简单，如果它们至少不等于搜索词计数，则可以将其丢弃。
之后，我们将加总单词的编辑距离，从与单词短语索引匹配的单词中删除单词，然后计算剩余的字母以获得真实的编辑距离。例如，如果您匹配“对草莓过敏”一词，而您的搜索查询是“稻草”，则草莓得分为7，那么您将使用词组索引从该词中删除草莓，然后进行计数“过敏”(减去空格)得到16分。
这为我们提供了我们期望的准确结果。但是，它太慢了。在一个单词搜索之前，我们可以获得25-40毫秒的时间，而现在它可能长达半秒。这很大程度上来自于实例化TermInfo对象，使用.add()操作，.put()操作以及必须返回大量匹配项这一事实。我们可以将每个搜索限制为仅返回1000个匹配项，但不能保证“car”的前1000个结果将与“cat”的前1000个匹配项中的任何一个匹配(请记住，有超过110万个字词)。
即使对于单个查询词(例如cat)，我们仍然需要进行大量匹配。这是因为如果我们搜索“cat”，则搜索将匹配car并汇总其下方的所有终端节点(这会很多)。但是，如果我们限制结果的数量，那么将会过于强调以查询开头而不是编辑距离的单词。因此，比起外套，更可能包含诸如导管插入术之类的词。
因此，基本上，是否有关于如何处理第二个实现所解决的问题的想法，而又没有第二个实现所引入的速度减慢的问题呢？如果可以使一些事情变得更清楚，我可以包括一些选定的代码，但是我不想张贴大量的代码。
最佳答案
哇...辛苦了
那么，为什么不实现Lucene？当您遇到诸如afaik之类的问题时，它是最新最好的技术。
但是我想分享一些想法...
模糊不像稻草*，而是某些单词的错误键入。并且每个丢失/错误的字符都会使距离加1。
通常很难同时具有部分匹配(通配符)和模糊性!
标记化通常是一个好主意。
一切还很大程度上取决于您获得的数据。在源文件中或仅在搜索查询中是否存在拼写错误？
我已经看到了使用多维范围树的一些非常不错的实现。
但是我真的认为，如果您想完成上述所有工作，则需要图形集和良好的索引算法的完美组合。
例如，您可以使用诸如芝麻之类的语义数据库，并且在导入文档时，将每个 token 和文档作为节点导入。然后，根据文档中的位置等，您可以添加加权关系。
然后，您需要某种可以进行有效的模糊匹配的结构中的标记，例如bk树。
我认为您可以索引mysql数据库中的 token 并执行按位比较功能以获取差异。有一个函数返回所有匹配的位，如果您将字符串转换为ascii并将这些位分组，则可以很快实现。
但是，如果将标记与字符串匹配，则可以构造一个假设的完全匹配抗体，并在语义数据库中查询最近的邻居。
在进行词法化时，您必须将单词分解为部分单词，以实现部分匹配。
但是，您也可以进行通配符匹配(前缀，后缀或两者都可以)，但不会造成模糊不清。
您还可以索引整个单词或标记的不同串联。
但是，可能有特殊的bk-tree实现支持此功能，但我从未见过这样的实现。
关于java - 有关如何改进当前模糊搜索实现的建议，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3989772/