模糊匹配及Solr关键词自动提示应用

发布时间:2017-09-07 13:47:51
模糊匹配及Solr关键词自动提示应用 1. 字符串相似度

字符串相似度用于衡量2个字符串之间的相似度,这里的相似度一般指形式上的相似,而非语义上的相似。字符串相似度算法是模糊字符串匹配(搜索)的核心内容之一,在搜索引擎中的拼写检查、关键词智能补全中也发挥重要重要。在更高层次的实体链接(识别)或实体消歧应用中,也是重要的研究内容。
字符串的模糊匹配也叫模糊匹配,有点类似于正则表达式匹配,但是存在一些不同。字符串匹配(正则表达式)通常关注精确匹配,正则表达式描述的是精确的、没有二义性的字符串匹配,而模糊匹配更多关注的是相似度,近似、模糊、不精确。

模糊匹配需要回答类似下面的问题:

需要匹配多少字符? 在字符一样的情况下如何对字符顺序进行建模? 只在一个字符串中出现的字符如何处理? 是否某些字符比另一些字符更重要?例如开头的字符串更重要。 如何在单个字符与多个字符组合中进行选择和建模?

模糊匹配中的不同方法关注上述问题的不同方面。有些关注字符的重合度,有些则在字符顺序上更加关注,有些在字符组合(N元组)方面上进行建模。

1.1 字符重合度度量

字符重合度的2中度量方法:Jaccard距离,Jaro-Winkler距离。

Jaccard距离

又称相似系数,包含相同字符越多,两个字符串也越相似。具体计算时,使用相同字符串个数占总字符串个数(出现在两个字符串中)的百分比。
假设我们有以下两个词语:

中国人 中国

总共出现了3个字符(中,国,人),而共有的2个字符(中,国),因此Jaccard距离为2/3。下图是一个更直观的解释:

image_1apvj3hh31ota17rt1t2nedgb6o9.png-10.6kB

在Jaccard系数的计算中,我们根据的是字符是否出现进行统计,字符之间一律平等对待,没有考虑相应的权重。但是事实上,每个字符对相似度的贡献是不一样的,例如开头的字符串可能贡献会大一些,出现次数多对相似度贡献也有所影响。当jaccard计算中, 考虑每个字符的不同权重时,相似度成为Tanimoto coefficient(谷本系数)。也就是说,Jaccard系数是Tanimoto系数的特例。TF-IDF值可以作为权重的一种形式。

jaro-Winkler距离

Jaccard系数没有考虑字符顺序对相似度的影响。因此在极端的情况下,两个顺序相反的字符串相似度为1。Jaro-Winkler在这一问题上做了一些改进。Lucence内置了一个实现org.apache.lucence.search.spell.JaroWinklerDistance。这种方法根据字符串长度将匹配限制在一个窗口中,并且考虑了相同字符是否出现在两个字符串的同一位置。

考虑字符串DIXON和DICKSONX:

image_1apvl4hgl12i4kd5m7f1rclcnbm.png-3.6kB

上图中,深色的区域为匹配窗口。在这个区域内,总共有4个1,即4个匹配。字符串DIXON的长度为5,另一个长度为8.根据公式可以计算得到Jaro-Winkler系数为0.841。具体的公式及计算过程参考维基百科词条。

使用字符重合度来度量字符串相似度最大的问题是没有很好地考虑字符顺序,虽然Jaro-Winkler尝试做了一些改进。下面要介绍的编辑距离更正式地考虑了顺序这一因素。考虑顺序不可避免地使得计算性能下降,我们也会讨论一些提高计算性能的方法。

1.2 编辑距离

编辑距离,将一个字符串变成另一个字符串需要的操作次数。操作一般包括插入、删除、替换。因此编辑距离就是变换所需要的插入、删除、替换的最小次数。例如将tamming test转变为taming text需要删除m和替换x,编辑距离为2。插入、删除、替换操作的权重都一样的情况下,这种距离被称为Levenshtein距离。

归一化编辑距离

上述在考虑编辑距离的时候,我们没有考虑字符串长度。一个长度为10的字符串经过两次编辑后相同,跟一个长度为2的字符串经过两次编辑后相同,本质上是非常不同的。例如linktofarm与linktofrdd经过两次编辑后都成为linktofarm,而ab和cd经过两次编辑后也可以成为ab,因此编辑距离一样,说这两组字符串的相似度一样是很难说得通的。因此很有必要根据编辑后的长度进行归一化。

为了归一化到0-1,将两个字符串中长度较长的,减去编辑距离后再除以这个较长的长度。例如tamming test和taming text,较长的距离为12,减去编辑距离2,再除以12,得到归一化的值为0.833。再看一下刚才的两对字符串,归一化后的值分别为(10 - 2)/10=0.8和(2-2)/2=0。这是比较符合逻辑的,ab和cd根本没有什么相似度。

对编辑操作加权

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:天门SEO http://tianmen.raoyu.net