1. 字符串相似度

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

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

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

1.1 字符重合度度量

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

Jaccard距离

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

中国人
中国

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

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

jaro-Winkler距离

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

考虑字符串DIXON和DICKSONX：

上图中，深色的区域为匹配窗口。在这个区域内，总共有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根本没有什么相似度。

对编辑操作加权

一种Levenshtein的常见变型是Demerau-Levenshtein距离，这种计算方法引入了新的操作：调换相邻两个字符的位置，原本需要一个删除和一次插入的操作减少到一次。Levenshtein的实现在Lucence中也有一个优化过的版本org.apache.lucence.search.spell.LevenshteinDistance。在拼写检查中，两个元音字母的替换比两个辅音字母之间的替换更有可能发生，给予不同的权重是合理的。

1.3 n元组编辑距离

前面讨论到的方法都只涉及到单个字符，N元组编辑距离则允许使用多个字符进行比较。字符串开头的相似性往往会被特殊考虑。Lucence中N元组编辑距离的实现类为NgramDistance。

1.4 其他相似度度量方法

除了上述提到的集中计算方法外，还有很多方法用于计算字符串的相似。例如简单地使用最长字符串匹配，编辑距离的变形Damerau-Levenshtein，Q-Gram算法等。更多相似度算法可以参考这里。

1.5 Java字符串相似度计算：

字符串相似度的计算在不同语言中有非常多的实现，在Java中也有很多现成的方案。Solr和Lucence中自动了一些相似度算法实现。下面两个库也针对很多算法提供了实现：

java string similarity

apache common common-text

2. 模糊匹配在Solr关键词提示的应用

搜索关键词提示或者建议几乎是搜索引擎的标配，除了减少用户输入外，能够引导用户到适合的关键词上，提升用户体验。下面的例子中，我们在Solr中实现一个关键字自动提示的例子。
Solr中的EdgeNGramTokenFilter在建立索引的时候，会根据配置将前缀也加入到索引中。例如taming这个词项在被索引时，ta、tam、tami等也会同时被索引。下面的Field类型声明展示了这种用法：

相应的Field配置如下:

配置完后，加入两个文档：doctor和document，使用下面的查询测试一下效果：

http://localhost:8983/solr/select?q=prefixxdo&fl=test

在实际的产品应用中，前端需要配置JS的键盘事件来获取提示词，script.aculo.us是一个不错的库。更进一步，可以定制一个QueryResponseWriter返回前端需要的格式，例如返回li代码片段，自己定制的Writer需要在solrconfig中配置：

  
    tah
    dismax
     prefixx^1.0
  

此时就可以通过下面定制的Handler来处理请求：

http://localhost:8983/solr/typeahead?q=tam