标签: fuzzy-search

我只是冒险进入看似简单但非常复杂的搜索世界.对于应用程序,我需要构建一个搜索机制,以按名称搜索用户.

阅读了大量的帖子和文章,包括:

如何使用Lucene进行个人姓名(名字,姓氏)搜索？
http://dublincore.org/documents/1998/02/03/name-representation/
通过优先考虑用户关系来搜索社交网络的最佳方式是什么？
http://www.gossamer-threads.com/lists/lucene/java-user/120417
Lucene索引和查询设计问题 - 搜索人员
Lucene模糊搜索客户名称和部分地址

......以及其他一些我现在无法找到的人.在我的机器上进行至少索引和基本搜索工作我已经为用户搜索设计了以下方案:

1)具有第一,第二和第三名称字段并使用Solr对其进行索引
2)使用edismax作为多列搜索的requestParser
3)使用标准化过滤器的组合,例如:音译,拉丁语到ascii convesrion等
.4 )最后使用模糊搜索

很明显,对于这方面的新手,我不确定上述是否是最好的方法,并希望听到在这个领域比我更有想法的有经验的用户.

我需要能够通过以下方式匹配名称:

1)口音折叠:Jorn匹配Jörn,反之亦然
2)替代拼写:Karl匹配Carl,反之亦然
3)缩短陈述(我相信我使用SynonymFilterFactory):Sue匹配Susanne等
.4)Levenstein匹配:Jonn匹配John等
.5)Soundex匹配:Elin和Ellen

任何指导,批评或评论都是非常受欢迎的.如果可能的话请告诉我......或者我只是白日做梦.:)

编辑

我还必须补充一点,我也有一个全名字段,以防有些人有长名字,作为其中一个帖子的例子:Jon Paul或Del Carmen也应该匹配Jon Paul Del Carmen

由于这是一个新项目,我可以以任何我认为合适的方式修改架构和架构,因此限制非常有限.

你能建议一些轻量级模糊文本搜索库吗？

我想要做的是允许用户使用拼写错误找到搜索字词的正确数据.

我可以使用像Lucene这样的全文搜索引擎,但我认为这是一种过度杀伤力.

编辑:
为了使问题更清楚,这里是该库的主要场景:
我有一个很大的字符串列表.我希望能够在此列表中搜索(类似于MSVS的intellisense)但是应该可以通过字符串过滤此列表,该字符串不存在于其中,但足够接近列表中的某个字符串.
例:

• 红色
• 绿色
• 蓝色

当我在文本框中输入'Gren'或'Geen'时,我想在结果集中看到'Green'.

索引数据的主要语言是英语.

我认为Lucene对于这项任务非常重要.

更新:

我找到了一个符合我要求的产品.这是ShuffleText.
你知道其他选择吗？

按照这个在相关的线程评论,我想知道为什么基于Levenshtein距离方法比探测法更好.

我有一个~300.000行表; 其中包括技术术语; 使用PHP和MySQL + FULLTEXT索引查询.但是,当我搜索错误的类型术语时; 例如"超文本"; 自然没有结果.

我需要"压缩"一点点写错误并从数据库中获取最接近的记录.我怎么能做到这样的特质？我知道(实际上,今天学到的)关于Levenshtein距离,Soundex和Metaphone算法,但目前没有一个坚实的想法来实现这个来查询数据库.

最好的祝福.(抱歉我的英语不好,我正努力做到最好)

我正在尝试模糊搜索"jahngir"~0.2,这不会返回任何结果.我的索引记录了数据"JAHANGIR RAHMAN MD".如果我尝试使用确切的单词"jahangir"~0.2进行搜索,它就可以了.关于我做错了什么,有人可以帮忙吗？我花了很多时间试图弄清楚Solr Fuzzy搜索是如何工作的.任何解释Solr模糊搜索的链接都会有所帮助.下面是我用于索引的文本字段.提前致谢.

 <fieldType name="text" class="solr.TextField" positionIncrementGap="100" autoGeneratePhraseQueries="true">
  <analyzer type="index">
    <tokenizer class="solr.WhitespaceTokenizerFactory"/>
    <!-- in this example, we will only use synonyms at query time
    <filter class="solr.SynonymFilterFactory" synonyms="index_synonyms.txt" ignoreCase="true" expand="false"/>
    -->
    <!-- Case insensitive stop word removal.
      add enablePositionIncrements=true in both the index and query
      analyzers to leave a 'gap' for more accurate phrase queries.
    -->
    <filter class="solr.StopFilterFactory"
            ignoreCase="true"
            words="stopwords.txt"
            enablePositionIncrements="true"
            />
    <filter class="solr.WordDelimiterFilterFactory" generateWordParts="1" generateNumberParts="1" catenateWords="1" catenateNumbers="1" catenateAll="0" splitOnCaseChange="1"/>
    <filter class="solr.LowerCaseFilterFactory"/>
    <filter class="solr.KeywordMarkerFilterFactory" protected="protwords.txt"/>
    <filter class="solr.PorterStemFilterFactory"/>
    <filter class="solr.CommonGramsFilterFactory" words="stopwords.txt" …

我有两个超过一百万个名称的列表,命名约定略有不同.这里的目标是匹配那些相似的记录,具有95%置信度的逻辑.

我知道有一些我可以利用的库,比如Python中的FuzzyWuzzy模块.

然而,就处理而言,似乎将占用太多资源,将1个列表中的每个字符串与另一个列表进行比较,在这种情况下,似乎需要100万乘以另外的百万次迭代次数.

这个问题还有其他更有效的方法吗？

更新:

所以我创建了一个bucketing函数,并应用了一个简单的规范化,即删除空格,符号并将值转换为小写等...

for n in list(dftest['YM'].unique()):
    n = str(n)
    frame = dftest['Name'][dftest['YM'] == n]
    print len(frame)
    print n
    for names in tqdm(frame):
            closest = process.extractOne(names,frame)

通过使用pythons pandas,将数据加载到按年分组的较小桶中,然后使用FuzzyWuzzy模块,process.extractOne用于获得最佳匹配.

结果仍然有点令人失望.在测试期间,上面的代码用于仅包含5千个名称的测试数据框,并且占用将近一个小时.

测试数据被拆分.

• 名称
• 出生日期的年月

我正在用他们的YM在同一桶中的桶进行比较.

问题可能是因为我使用的FuzzyWuzzy模块？感谢任何帮助.

需要一种方法让我的搜索引擎处理搜索字符串中的小拼写错误,并仍然返回正确的结果.

根据ElasticSearch文档,有三个值与文本查询中的模糊匹配相关:模糊性,max_expansions和prefix_length.

不幸的是,关于这些参数究竟是做什么的,并没有很多详细信息,以及它们的合理值.我知道模糊性应该是0到1.0之间的浮点数,而另外两个是整数.

任何人都可以为这些参数推荐合理的"起点"值吗？我确信我将不得不通过反复试验来调整,但我只是在寻找球场价值来正确处理拼写错误和拼写错误.

如何在multi_match查询中添加模糊性？因此,如果有人要搜索'basball',它仍会找到'棒球'文章.目前我的查询如下所示:

POST /newspaper/articles/_search
{
    "query": {
        "function_score": {
            "query": {
                "multi_match": {
                    "query": "baseball",
                    "type": "phrase",
                    "fields": [
                        "subject^3", 
                        "section^2.5", 
                        "article^2", 
                        "tags^1.5",
                        "notes^1"
                    ]
                }
            }
        }
    }
}

我正在考虑的一个选择是做这样的事情,只是不知道这是否是最好的选择.根据评分保持排序很重要:

   "query" : { 
      "query_string" : { 
         "query" : "subject:basball^3 section:basball^2.5 article:basball^2", 
         "fuzzy_prefix_length" : 1 
      } 
   } 

建议？

我有一个非常长的位序列,称为比特序列A,以及更短的比特序列x.在对齐它们之后,相同长度的两个比特序列是模糊匹配的,存在k或者更少的不匹配比特.我想在A中找到x的所有模糊出现.

到目前为止,我已经尝试过天真的方法.循环通过A,然后对于每个位,循环遍历x的长度,计算从A中该位置开始的不匹配位的数量,如果它不超过k,则报告该位置.该算法效率不高.如果A具有n_A位,并且x具有n_x位,则运行时间为O(n_A * n_x).

我被告知O(n_A * log(n_A))无论如何都可以做到这一点k.提供的提示是利用快速傅立叶变换.请记住,两个输入 和 ,卷积产生 哪里

类似于多项式乘法.我不清楚如何使用这个提示.任何帮助将非常感激.

I am trying to find strings which are at most two mistakes 'away' from the original pattern string (i.e. they differ by at most two letters).

However, the following code isn't working as I would expect, at least not from my understanding of fuzzy regex:

import regex
res = regex.findall("(ATAGGAGAAGATGATGTATA){e<=2}", "ATAGAGCAAGATGATGTATA", overlapped=True)
print res
>> ['ATAGAGCAAGATGATGTATA']  # the second string

As you can see, the two strings differ on three letters rather than at most two:

the first has: ATAG …