How to Strike a Match

一、概念

来自于Simon White发表的一篇文章：How to Strike a Match 这个算法主要为了满足以下三个需求：

（1）字符串之间只是在某几个字符处出现不同，那么相似度应该比较高。 （2）字符串的区别只是相同的词组以不同的顺序排列，那么相似度应该比较高。 （3）语言无关性，算法应该满足多种语言的的相似度计算。

论文中对比了几种相似度算法， Soundex Algorithm会因为字符串开头的字符不同而导致字符串形成的编码不一致而导致相似度降低，如：‘FRANCE’ 和 ‘REPUBLIC OF FRANCE’； Edit Distance则对字符串长度敏感，随字符串长度差距增大而相似度降低，如：‘FRANCE’ 和 ‘QUEBEC’ 的相似度要比 ‘FRANCE’ 和 'REPUBLIC OF FRANCE’的相似度高； Longest Common Substring提取公共子字符串，则会造成拥有相同子字符串的字符串相似度一致，如：‘FRENCH REPUBLIC’ 与 'REPUBLIC OF FRANCE’的相似度 和’REPUBLIC OF CUBA’的相似度一致。

二、思想

论文里算法的思想相当简单，对于转化为大写的两个字符串，根据字符串的顺序，以2-gram的形式取出字符对，如：

FRANCE: {FR, RA, AN, NC, CE} FRENCH: {FR, RE, EN, NC, CH}

之后，取两个集合的交集，记录交集字符对的数量，最后再将两倍的交集字符对总数量除以两个集合字符对的总数量，如： 具体到例子中的字符串，代入可得：

最终得到的结果便是字符串之间的相似度。

三、例子

论文中还贴出了一些例子，简单摘录如下： （1）与‘Healed’的相似度 （2）图书名称相似度

注：本文中图片均来自于论文截图