相似度算法在地址匹配中的应用

在做地址匹配的时候，我们经常会遇到一个问题：

addr1 = 河北省石家庄市裕华区万达广场
addr2 = 河北石家庄市裕华万达广场

是同一个地址吗？

addr1 = 河北石家庄市裕华万达广场
addr3 = 河北石家庄市裕华万达公馆

是同一个地址吗？

在人的眼里，这可能不是什么问题，可是在计算机眼里，这就不好说了。

计算机能够很快的匹配两个字符串是否完全一样，但是对于差那么几个字符的，计算机是无法识别其差别有多大的，而且计算机也无法识别出来差的那几个字是关键词还是普通的辅助词。

所以相似度算法也就派上用场了。

所谓相似度算法，就是通过一定的计算逻辑，老判断两个字符串（不仅仅是字符串）之间差距有多大，然后给出一个评分，评分越高，则两个字符串越相似，如果两个字符串完全一样，则评分为1。

根据实现原理的不同，相似度算法又可以分为：

• 基于向量的近似匹配
  • cosine余弦相似度匹配
• 基于编辑距离的近似匹配
  • Levenshtein算法
• 基于字符串局部匹配的近似匹配
  • jaroWinkler
  • needlemanWunch
  • smithWaterman
• 基于集合的近似匹配
  • jaccard
  • dice
  • overlap Coefficient

1. 基于向量的余弦近似度匹配

所谓向量，就是我们数学上学习过的那个向量（数学照进现实），是一个有方向的字段。
在向量近似匹配的逻辑里，如果两个向量间的夹角越小，则两个向量越相似，这里用到的算法就是余弦相似度算法。

余弦相似度公式：

$$\text{cosine}(\vec{a}, \vec{b}) = \frac{\vec{a}·\vec{b}}{\|\vec{a}\|\|\vec{b}\|}$$

对应到字符串匹配上，结合TF-IDF算法, 统计每个地址里分词出现的频率，这些频率就组成了这个这个地址的向量值,然后套用上面的公式，就可以计算出上面的余弦相似度了。

然后，问题的关键就来到了如何有效的对每个地址字符串进行分词拆分了，这里推荐一个java里好用的工具HanLP，这是一个专门面向汉语分词的工具包，1.0版本提供了一套java的分词器，比较好用。

<dependency>
    <groupId>com.hankcs</groupId>
    <artifactId>hanlp</artifactId>
    <version>portable-1.8.6</version>
</dependency>

然后通过HanLP对字符串进行分词，分词结果：

addr1 = [河北省, 石家庄市, 裕华区, 万达, 广场]
addr2 = [河北, 石家庄市, 裕华, 万达, 广场]
addr3 = [河北, 石家庄市, 裕华, 万达, 公馆]

然后将比较的两个短语取并集，统计每个词出现的频率，就可以得到这个地址的向量值了.

• addr1 vs addr2

addr1 vs addr2 并集 = [河北省, 石家庄市, 裕华区, 万达, 广场, 河北，裕华]
// 并集中每个词出现的频率就是其坐标点位
addr1 = [1, 1, 1, 1, 1, 0, 0]
addr2 = [0, 1, 0, 1, 1, 1, 1]

余弦向量计算结果：

$$\frac{1·0+1·1+1·0+1·1+1·1+0·1+0·1}{\sqrt{1^2+1^2+1^2+1^2+1^2+0^2+0^2}·\sqrt{0^2+1^2+0^2+1^2+1^2+1^2+1^2}} = 0.6$$

• addr1 vs addr3

addr1 vs addr3 并集 = [河北省, 石家庄市, 裕华区, 万达, 广场, 河北，裕华,公馆]
// 并集中每个词出现的频率就是其坐标点位
addr1 = [1, 1, 1, 1, 1, 0, 0, 0]
addr3 = [0, 1, 0, 1, 0, 1, 1, 1]

余弦向量计算结果：

$$\frac{1·0+1·1+1·0+1·1+1·1+0·1+0·1+0·1}{\sqrt{1^2+1^2+1^2+1^2+1^2+0^2+0^2+0^2}·\sqrt{0^2+1^2+0^2+1^2+0^2+1^2+1^2+1^2}} = 0.4$$

所以，addr1 和 addr2 更相似。

2. 基于字符串编辑距离的近似度匹配

所谓编辑距离，就是一个字符串，删除一个字符，或者增加一个字符，或者替换一个字符，可以得到另外一个字符串，那么，变动几次就是这两个字符串的编辑距离。

这个很好理解，我们可以拿上面的三个地址举例。

addr2 可以通过增加“省”，“区”两个字得到 addr1, 所以addr1 和 addr2 的编辑距离为2 。

addr3 可以通过替换“公馆”为“广场”两个字得到 addr2, 而addr2 和addr1 的编辑距离为2， 所以addr1 和 addr3 的编辑距离为4 。

这个算法，仅关注两个字符的变化差异，受到一些辅助性词汇的干扰比较大，所以，这个算法并不适合于比较两个地址是否一样的逻辑。

3. 基于字符串局部匹配的近似度匹配

关于字符串的局部匹配的算法就很多了，我们就以上面说的那几个算法举例：

• smithWaterman ：局部序列比对：对比两个字符串中的子序列部分，通过一套打分系统，来寻找两个字符中每一个相似片段，最后返回最大的匹配得分。
• needlemanWunch：全局序列比对：通过填充替换等方式，对两个字符串进行改造，配合一套打分系统，对每一种全字符串改造成功后的方案进行打分，最后返回最大的匹配得分。
• jaroWinkler：jaro算法改进版，引入了前缀因子，相同前缀的数据，匹配得分会更高

因为地址的特殊性，jaroWinkler算法会更适用一些。

4. 基于集合的近似度匹配

将字符串拆解成分词，然后将每一组分词看出一个集合，通过集合间的交集、并集等方式，是实现字符串相似度匹配的另一种实现逻辑。

4.1 jaccard

jaccard算法，也叫杰卡德算法， 是一种比较有限样本集的相似性与差异性的算法，值越大，相似度越高。

$$\text{jaccard}(a, b) = \frac{a \cap b}{a \cup b}$$

同样以上面的地址举例：
addr1 和 addr2 交集 = [石家庄市, 万达, 广场]
addr1 和 addr2 并集 = [河北省, 石家庄市, 裕华区, 万达, 广场, 河北，裕华]

所以：

$$\text{jaccard}(addr1, addr2) = \frac{3}{7} = 0.42857$$

addr1 和 addr3 交集 = [石家庄市, 万达]
addr1 和 addr3 并集 = [河北省, 石家庄市, 裕华区, 万达, 广场, 河北，裕华,公馆]

所以：

$$\text{jaccard}(addr1, addr3) = \frac{2}{8} = 0.25$$

4.2 dice

dice算法，jaccard算法的一个改进版本，增加了相似集合的权重。

dice 的算法公式：

$$\text{dice}(a, b) = \frac{2|a \cap b |}{|a| + |b|}$$

• $|a|$ 表示集合a的元素个数。
• $|b|$ 表示集合b的元素个数。

同样以上面的地址举例：

$$\text{dice}(addr1, addr2) = \frac{2·3}{5 + 5} = 0.6$$ $$\text{dice}(addr1, addr3) = \frac{2·2}{5+5} = 0.4$$

4.3 Overlap Coefficient

Overlap Coefficient（重叠系数）是一种用于衡量两个集合相似度的算法，其核心原理是计算两个集合的交集大小与较小集合大小的比值。

Overlap Coefficient的计算公式：

$$\text{Overlap}(a, b) = \frac{a \cap b}{min(|a|, |b|)}$$

依据这个公式，上面地址的计算结果为：

$$\text{Overlap}(addr1, addr2) = \frac{3}{5} = 0.6$$ $$\text{Overlap}(addr1, addr3) = \frac{2}{5} = 0.4$$

5. 应用实践

以上，这些字符串的相似度算法的原理我们都了解了，在实际应用中，我们完全可以根据业务场景和算法特点，选择合适的算法应用，甚至可以组合的使用。

我这边是要做了一个地址比较的项目，因为地址的特点，我选择了前缀匹配的jaroWinkler算法，组合cosine余弦算法来实现，只有两个算法都成功的时候，才认为两个地址是相似的。

具体步骤如下：

1. 预处理：将两个地址对齐，统一按照省市县镇的格式补全地址，不然单给一个万达广场，根本无法匹配准确地址。
2. 地址规范化补全后，使用hanLP分词，对地址进行分词，得到一个词表。
3. 使用jaroWinkler相似度算法匹配地址
4. 使用cosine算法匹配地址
5. 两个算法的成功率都达到阈值，才认为两个地址是相似的。
6. 最后再根据地址的特点，前面的词都是辅助性定语，只有最后的词才是关键词，所以我最后又增加了一次优化：对比两个地址的尾串，如果完全相同的部分大于某个阈值，则认为两个地址是相似的。

6. 这些算法的代码demo

以下是这些算法的代码demo，大家可以参考一下：

• pom.xml

<dependency>
  <groupId>com.github.mpkorstanje</groupId>
  <artifactId>simmetrics-core</artifactId>
  <version>4.1.1</version>
</dependency>

<dependency>
  <groupId>com.hankcs</groupId>
  <artifactId>hanlp</artifactId>
  <version>portable-1.8.6</version>
</dependency>

hanLP: 前面已经介绍过了，是一个很好用的中文分词工具类。

simmetrics： 一个开源的字符串相似度算法库，集成了很多常用的算法，可以拿来直接使用。

• code

public static void main(String[] args) {
        String addr1 = "河北省石家庄市裕华区万达广场";
        String addr2 = "河北石家庄市裕华万达广场";
        String addr3 = "河北石家庄市裕华万达公馆";


        List<String> addr1List = hanlpSeg(addr1);
        List<String> addr2List = hanlpSeg(addr2);
        List<String> addr3List = hanlpSeg(addr3);

        //
        System.out.println("---cosine：  a·b / (||a|| * ||b||)---");
        CosineSimilarity<String> cosineClient = new CosineSimilarity<String>();
        float score = cosineClient.compare(HashMultiset.create(addr1List),
                HashMultiset.create(addr2List));
        System.out.println(score);
        score = cosineClient.compare(HashMultiset.create(addr1List),
                HashMultiset.create(addr3List));
        System.out.println(score);


        System.out.println("---jaccard：∣a ∩ b∣ / ∣a ∪ b∣--- ");
        Jaccard jaccard = new Jaccard<String>();
        System.out.println(jaccard.compare(new HashSet<>(addr1List),new HashSet<>(addr2List)));
        System.out.println(jaccard.compare(new HashSet<>(addr1List),new HashSet<>(addr3List)));

        System.out.println("---dice：2倍交集大小除以两集合大小之和 类似Jaccard但对共有词更敏感 --- ");
        Dice<String> dice = new Dice<String>();
        System.out.println(dice.compare(new HashSet<>(addr1List),new HashSet<>(addr2List)));
        System.out.println(dice.compare(new HashSet<>(addr1List),new HashSet<>(addr3List)));

        System.out.println("---overlapCoefficient：交集大小除以较短集合的大小--- ");
        OverlapCoefficient<String> overlapCoefficient = new OverlapCoefficient<String>();
        System.out.println(overlapCoefficient.compare(new HashSet<>(addr1List),new HashSet<>(addr2List)));
        System.out.println(overlapCoefficient.compare(new HashSet<>(addr1List),new HashSet<>(addr3List)));
        

        System.out.println("---smithWaterman：局部序列对齐 动态规划+得分矩阵--- ");
        StringMetric smithWaterman = StringMetrics.smithWaterman();
        System.out.println(smithWaterman.compare(addr1,addr2));
        System.out.println(smithWaterman.compare(addr1,addr3));

        System.out.println("---needlemanWunch：全局序列对齐，动态规划+固定空位罚分--- ");
        StringMetric needlemanWunch = StringMetrics.needlemanWunch();
        System.out.println(needlemanWunch.compare(addr1,addr2));
        System.out.println(needlemanWunch.compare(addr1,addr3));

        System.out.println("---jaroWinkler：关注前缀匹配--- ");
        StringMetric jaroWinkler = StringMetrics.jaroWinkler();
        System.out.println(jaroWinkler.compare(addr1,addr2));
        System.out.println(jaroWinkler.compare(addr1,addr3));

        System.out.println("---levenshtein：编辑距离--- ");
        Levenshtein levenshtein = new Levenshtein();
        System.out.println(levenshtein.compare(addr1,addr2)+":距离="+levenshtein.distance(addr1,addr2));
        System.out.println(levenshtein.compare(addr1,addr3)+":距离="+levenshtein.distance(addr1,addr3));
    }

    private static List<String> hanlpSeg(String str) {
        Segment segment = HanLP.newSegment().enablePlaceRecognize(true);
        // 可以通过这种方式，自己指定分词
//      CustomDictionary.add("万达广场","ns 1000");
      
      List<String> list = segment.seg(str).stream().map(term -> term.word).toList();
        System.out.println(list);
        return list;

    }

参考

hanLp 1.x文档

simmetrics github