推荐阅读：

面试BAT 却被小小字符串秒杀？这13道题帮你一举击败字符串算法题
字节跳动秋招面经：后端开发工程师，已拿意向书
前言

平时的编码中，我们经常需要判断两个文本的相似性，不管是用来做文本纠错或者去重等等，那么我们应该以什么维度来判断相似性呢？这些算法又怎么实现呢？这篇文章对常见的计算方式做一个记录。

Jaccard 相似度

首先是 Jaccard 相似度系数，下面是它在维基百科上的一个定义及计算公式。

The Jaccard index, also known as Intersection over Union and the Jaccard similarity coefficient (originally given the French name coefficient de communauté by Paul Jaccard), is a statistic used for gauging the similarity and diversity of sample sets. The Jaccard coefficient measures similarity between finite sample sets, and is defined as the size of the intersection divided by the size of the union of the sample sets:

其实总结就是一句话：集合的交集与集合的并集的比例.

java 代码实现如下：

 public static float jaccard(String a, String b) { if (a == null && b == null) { return 1f; } // 都为空相似度为 1 if (a == null || b == null) { return 0f; } Set aChar = a.chars().boxed().collect(Collectors.toSet()); Set bChar = b.chars().boxed().collect(Collectors.toSet()); // 交集数量 int intersection = SetUtils.intersection(aChar, bChar).size(); if (intersection == 0) return 0; // 并集数量 int union = SetUtils.union(aChar, bChar).size(); return ((float) intersection) / (float)union; }

与 Jaccard 类似，Dice 系数也是一种计算简单集合之间相似度的一种计算方式。与 Jaccard 不同的是，计算方式略有不同。下面是它的定义。

The Sørensen–Dice coefficient (see below for other names) is a statistic used to gauge the similarity of two samples. It was independently developed by the botanists Thorvald Sørensen[1] and Lee Raymond Dice,[2] who published in 1948 and 1945 respectively.

需要注意的是，他是：集合交集的 2 倍除以两个集合相加。并不是并集.

java 代码实现如下：

 public static float SorensenDice(String a, String b) { if (a == null && b == null) { return 1f; } if (a == null || b == null) { return 0F; } Set aChars = a.chars().boxed().collect(Collectors.toSet()); Set bChars = b.chars().boxed().collect(Collectors.toSet()); // 求交集数量 int intersect = SetUtils.intersection(aChars, bChars).size(); if (intersect == 0) { return 0F; } // 全集，两个集合直接加起来 int aSize = aChars.size(); int bSize = bChars.size(); return (2 * (float) intersect) / ((float) (aSize + bSize)); }

莱文斯坦距离，又称 Levenshtein 距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

简单的说，就是用编辑距离表示字符串相似度, 编辑距离越小，字符串越相似。

java 实现代码如下：

 public static float Levenshtein(String a, String b) { if (a == null && b == null) { return 1f; } if (a == null || b == null) { return 0F; } int editDistance = editDis(a, b); return 1 - ((float) editDistance / Math.max(a.length(), b.length())); } private static int editDis(String a, String b) { int aLen = a.length(); int bLen = b.length(); if (aLen == 0) return aLen; if (bLen == 0) return bLen; int[][] v = new int[aLen + 1][bLen + 1]; for (int i = 0; i