AHu*_*ist 9 java algorithm performance fuzzy-search levenshtein-distance
我正在努力实现术语Web服务的模糊搜索,我正在寻找关于如何改进当前实现的建议.分享的代码太多了,但我认为解释可能足以提出深思熟虑的建议.我意识到这是很多东西,但我很感激任何帮助.
首先,术语基本上只是一些名称(或术语).对于每个单词,我们按空格将其拆分为标记,然后遍历每个字符以将其添加到trie.在终端节点上(例如当达到草莓中的字符y时),我们在列表中存储主术语列表的索引.因此,终端节点可以具有多个索引(因为草莓的终端节点将匹配'草莓'和'对草莓过敏').
对于实际搜索,搜索查询也按空间分解为标记.为每个令牌运行搜索算法.搜索令牌的第一个字符必须匹配(因此traw永远不会匹配草莓).之后,我们通过每个连续节点的子节点.如果有匹配的字符的子项,我们继续使用搜索令牌的下一个字符进行搜索.如果孩子与给定的角色不匹配,我们会使用搜索令牌的当前角色来查看孩子(因此不会推进它).这是模糊部分,因此'stwb'将匹配'草莓'.
当我们到达搜索令牌的末尾时,我们将搜索该节点处的其余trie结构以获得所有可能的匹配(因为到主术语列表的索引仅在终端节点上).我们称之为卷起.我们通过在BitSet上设置它们的值来存储索引.然后,我们简单地从每个搜索令牌的结果中得到BitSets.然后,我们从anded BitSet中获取前1000或5000个索引,并找到它们对应的实际项.我们使用Levenshtein对每个术语进行评分,然后按分数进行排序以获得最终结果.
这种方法效果很好而且非常快.树中有超过390k个节点,超过110万个实际术语名称.但是,现在存在问题.
例如,当我们不想要它时,搜索'car cat'将返回Catheterization(因为搜索查询是两个单词,结果应该至少为两个).这很容易检查,但它不会像导管过程那样处理,因为它是两个字.理想情况下,我们希望它与Cardiac Catheterization相匹配.
基于纠正这个问题的需要,我们想出了一些改变.首先,我们通过混合深度/广度搜索来检查trie.基本上,只要角色匹配,我们就会先进入深度.那些不匹配的子节点将添加到优先级队列中.优先级队列按编辑距离排序,可以在搜索特里时计算(因为如果有字符匹配,则距离保持不变,如果不匹配,则增加1).通过这样做,我们得到每个单词的编辑距离.我们不再使用BitSet了.相反,它是Terminfo对象的索引映射.此对象存储查询短语的索引以及术语短语和分数.因此,如果搜索是"汽车猫"并且匹配的术语是"导管过程" 术语短语索引将是1,查询短语索引也是如此.对于"心脏导管",术语短语索引将是1,2,查询短语索引也是如此.正如您所看到的,之后查看术语短语索引和查询短语索引的计数非常简单,如果它们不至少等于搜索词计数,则可以将它们丢弃.
之后,我们将单词的编辑距离相加,从与术语短语索引匹配的术语中删除单词,并计算剩余的字母以获得真正的编辑距离.例如,如果您将术语"过敏与草莓"匹配并且您的搜索查询为"稻草",您将从草莓中获得7分,那么您将使用术语短语索引从该术语中丢弃草莓,并且只计算"过敏"(减去空格)得分为16分.
这让我们得到了我们期望的准确结果.但是,它太慢了.在一个单词搜索之前我们可以获得25-40毫秒,现在它可能多达半秒.它主要来自实例化TermInfo对象,使用.add()操作,.put()操作以及我们必须返回大量匹配这一事实.我们可以将每次搜索限制为仅返回1000个匹配,但不能保证"car"的前1000个结果将匹配"cat"的前1000个匹配中的任何一个(记住,有超过1.1万个术语).
即使对于像cat一样的单个查询词,我们仍然需要大量的匹配.这是因为如果我们搜索'cat',搜索将匹配汽车并汇总其下方的所有终端节点(这将是很多).但是,如果我们限制结果的数量,则会过于强调以查询开头而不是编辑距离的单词.因此,像导尿管这样的词语比涂层更容易被包括在内.
那么,基本上,对于我们如何处理第二个实现修复的问题有什么想法,但没有引入的速度减慢那么多吗？我可以包含一些选定的代码,如果它可以使事情更清楚,但我不想发布一个巨大的代码墙.
哇...艰难的一个。
那你为什么不实现lucene呢？当涉及到像你这样的问题时，这是最好的、当前最先进的技术。
不过我想分享一些想法...
模糊性并不是像稻草*那样的东西，而是某些单词的错误输入。每个缺失/错误的字符都会使距离加 1。
通常，同时具有部分匹配（通配符）和模糊性是非常非常困难的！
标记化通常是一个好主意。
一切都在很大程度上取决于您获得的数据。源文件中是否存在拼写错误，或者仅在搜索查询中存在拼写错误？
我已经看到一些使用多维范围树的非常好的实现。
但我真的认为，如果您想完成上述所有目标，您需要图形集和良好的索引算法的完美组合。
例如，您可以使用像 sesame 这样的语义数据库，并在导入文档时将每个标记和文档导入为节点。然后根据文档中的位置等，您可以添加加权关系。
然后，您需要某种结构中的标记，您可以在其中进行有效的模糊匹配，例如 bk 树。我认为你可以在 mysql 数据库中对标记进行索引，并执行按位比较函数来获取差异。有一个函数可以返回所有匹配的位，如果您将字符串转换为 ascii 并对这些位进行分组，您可以很快地实现一些目标。
但是，如果您将标记与字符串进行匹配，您可以构造一个假设的完美匹配实体，并在语义数据库中查询最近的邻居。
在标记化时，您必须将单词分解为部分单词才能实现部分匹配。
但是，您也可以进行通配符匹配（前缀、后缀或两者），但不会出现模糊性。
您还可以对整个单词或不同的标记串联进行索引。
然而，可能有特殊的 bk-tree 实现支持这一点，但我从未见过。