NLP 点滴 ：文本相似度 （上）

导语

在自然语言处理过程中，经常会涉及到如何度量两个文本之间的相似性，我们都知道文本是一种高维的语义空间，如何对其进行抽象分解，从而能够站在数学角度去量化其相似性。而有了文本之间相似性的度量方式，我们便可以利用划分法的K-means、基于密度的DBSCAN或者是基于模型的概率方法进行文本之间的聚类分析；

另一方面，我们也可以利用文本之间的相似性对大规模语料进行去重预处理，或者找寻某一实体名称的相关名称（模糊匹配）。而衡量两个字符串的相似性有很多种方法，如最直接的利用hashcode，以及经典的主题模型或者利用词向量将文本抽象为向量表示，再通过特征向量之间的欧式距离或者皮尔森距离进行度量。本文围绕文本相似性度量的主题，从最直接的字面距离的度量到语义主题层面的度量进行整理总结，并将平时项目中用到的文本相似性代码进行了整理，如有任何纰漏还请指出，我会第一时间改正^v^。（ps.平时用的Java和scala较多，本文主要以Java为例。）

字面距离

提到如何比较两个字符串，我们从最初编程开始就知道：字符串有字符构成，只要比较比较两个字符串中每一个字符是否相等便知道两个字符串是否相等，或者更简单一点将每一个字符串通过哈希函数映射为一个哈希值，然后进行比较。但是这种方法有一个很明显的缺点，就是过于“硬”，对于相似性的度量其只有两种，0不相似，1相似，哪怕两个字符串只有一个字符不相等也是不相似，这在NLP的很多情况是无法使用的，所以下文我们就“软”的相似性的度量进行整理，而这些方法仅仅考虑了两个文本的字面距离，无法考虑到文本内在的语义内容。

common lang库

文中在部分代码应用中使用了Apache提供的common lang库，该库包含很多Java标准库中没有的但却很实用的函数。其maven引用如下：

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.4</version>
</dependency>

相同字符数

在传统的字符串比较过程中，我们考虑字符串中每个字符是否相等，并且考虑了字符出现的顺序，如果不考虑字符出现的顺序，我们可以利用两个文本之间相同的字符数量，很简单不再赘述，可以利用common lang中的getFuzzyDistance：

int dis = StringUtils.getFuzzyDistance(term, query, Locale.CHINA);

莱文斯坦距离(编辑距离)

定义

我们在学习动态规划的时候，一个很经典的算法便是计算两个字符串的编辑距离，即：

莱文斯坦距离，又称Levenshtein距离，是编辑距离（edit distance）的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如将kitten一字转成sitting：

sitten （k→s）

sittin （e→i）

sitting （→g）

那么二者的编辑距离为3。

俄罗斯科学家弗拉基米尔·莱文斯坦在1965年提出这个概念。

实现方式

我们可以利用common lang中StringUtils的函数来计算：

int dis = StringUtils.getLevenshteinDistance(s1, s2);
//实现
public static int getLevenshteinDistance(CharSequence s, CharSequence t) {
    if (s == null || t == null) {
        throw new IllegalArgumentException("Strings must not be null");
    }
    int n = s.length(); // length of s
    int m = t.length(); // length of t
    if (n == 0) {
        return m;
    } else if (m == 0) {
        return n;
    }
    if (n > m) {
        // swap the input strings to consume less memory
        final CharSequence tmp = s;
        s = t;
        t = tmp;
        n = m;
        m = t.length();
    }
    int p[] = new int[n + 1]; //'previous' cost array, horizontally
    int d[] = new int[n + 1]; // cost array, horizontally
    int _d[]; //placeholder to assist in swapping p and d
    // indexes into strings s and t
    int i; // iterates through s
    int j; // iterates through t
    char t_j; // jth character of t
    int cost; // cost
    for (i = 0; i <= n; i++) {
        p[i] = i;
    }
    for (j = 1; j <= m; j++) {
        t_j = t.charAt(j - 1);
        d[0] = j;
        for (i = 1; i <= n; i++) {
            cost = s.charAt(i - 1) == t_j ? 0 : 1;
            // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
            d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
        }
        // copy current distance counts to 'previous row' distance counts
        _d = p;
        p = d;
        d = _d;
    }
    // our last action in the above loop was to switch d and p, so p now
    // actually has the most recent cost counts
    return p[n];
}

Jaro距离

定义

Jaro Distance也是字符串相似性的一种度量方式，也是一种编辑距离，Jaro 距离越高本文相似性越高;而Jaro–Winkler distance是Jaro Distance的一个变种。据说是用来判定健康记录上两个名字是否相同，也有说是是用于人口普查。从最初其应用我们便可看出其用法和用途，其定义如下：

其中

• 
  是匹配数目（保证顺序相同）
• 
  字符串长度

*

是换位数目

• 其中t换位数目表示：两个分别来自S1和S2的字符如果相距不超过
  
  我们就认为这两个字符串是匹配的；而这些相互匹配的字符则决定了换位的数目t，简单来说就是不同顺序的匹配字符的数目的一半即为换位的数目t，举例来说，MARTHA与MARHTA的字符都是匹配的，但是这些匹配的字符中，T和H要换位才能把MARTHA变为MARHTA,那么T和H就是不同的顺序的匹配字符，t=2/2=1。 而Jaro-Winkler则给予了起始部分就相同的字符串更高的分数，他定义了一个前缀p，给予两个字符串，如果前缀部分有长度为 的部分相同，则Jaro-Winkler Distance为：
  
• 
  是两个字符串的Jaro Distance
• 
  是前缀的相同的长度，但是规定最大为4
• 
  则是调整分数的常数，规定不能超过0.25，不然可能出现dw大于1的情况，Winkler将这个常数定义为0.1

举个简单的例子：

计算

的距离

我们利用

可以得到一个匹配窗口距离为3，图中黄色部分便是匹配窗口，其中1表示一个匹配，我们发现两个X并没有匹配，因为其超出了匹配窗口的距离3。我们可以得到：

其Jaro score为：

而计算Jaro–Winkler score，我们使用标准权重

，其结果如下：

实现方式

同样我们可以利用common lang中的getJaroWinklerDistance函数来实现，注意这里实现的是Jaro–Winkler distance

double dis = StringUtils.getJaroWinklerDistance(reviewName.toLowerCase(), newsName.toLowerCase());

//实现
public static double getJaroWinklerDistance(final CharSequence first, final CharSequence second) {
    final double DEFAULT_SCALING_FACTOR = 0.1; //标准权重
    if (first == null || second == null) {
        throw new IllegalArgumentException("Strings must not be null");
    }
    final double jaro = score(first,second); // 计算Jaro score
    final int cl = commonPrefixLength(first, second); // 计算公共前缀长度
    final double matchScore = Math.round((jaro + (DEFAULT_SCALING_FACTOR * cl * (1.0 - jaro))) *100.0)/100.0;   // 计算 Jaro-Winkler score

    return  matchScore;
}

应用

在Wetest舆情监控中，我们在找寻游戏名简称和全称的对应关系时便使用到了Jaro-Winkler score进行衡量，其中我们将Jaro分数大于0.6的认为是相似文本，之后在总的相似文本中提取最相似的作为匹配项，实现效果还不错：

其中冒号左边是待匹配项，右边是匹配项<游戏名 词频，Jaro-Winkler score>，Jaro-Winkler score较高的一般都是正确的匹配项。

SimHash

定义

SimHash是一种局部敏感hash，它也是Google公司进行海量网页去重使用的主要算法。

传统的Hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上仅相当于伪随机数产生算法。传统的hash算法产生的两个签名，如果原始内容在一定概率下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别很大。所以传统的Hash是无法在签名的维度上来衡量原内容的相似度，而SimHash本身属于一种局部敏感哈希算法，它产生的hash签名在一定程度上可以表征原内容的相似度。

我们主要解决的是文本相似度计算，要比较的是两个文章是否相似，当然我们降维生成了hash签名也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hash却不行。

我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。

通过simhash计算结果为：

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过传统hash计算为：

0001000001100110100111011011110

1010010001111111110010110011101

通过上面的例子我们可以很清晰的发现simhash的局部敏感性，相似文本只有部分01变化，而hash值很明显，即使变化很小一部分，也会相差很大。

基本流程

注：具体的事例摘自Lanceyan10的博客《海量数据相似度计算之simhash和海明距离》

1. 分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
2. hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
3. 加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
4. 合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
5. 降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。

整个过程的流程图为：

相似性度量

有了simhash值，我们需要来度量两个文本间的相似性，就像上面的例子一样，我们可以比较两个simhash间0和1不同的数量。这便是汉明距离（Hamming distance）

在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。 汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。 例如： 1011101与1001001之间的汉明距离是2

一般在利用simhash进行文本相似度比较时，我们认为汉明距离小于3的文本是相似的。

存储索引

存储：

1. 将一个64位的simhash签名拆分成4个16位的二进制码。（图上红色的16位）
2. 分别拿着4个16位二进制码查找当前对应位置上是否有元素。（放大后的16位）

对应位置没有元素，直接追加到链表上；对应位置有则直接追加到链表尾端。（图上的 S1 — SN）

查找：

1. 将需要比较的simhash签名拆分成4个16位的二进制码。
2. 分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。
3. 如果有元素，则把链表拿出来顺序查找比较，直到simhash小于一定大小的值，整个过程完成。
4. 在去重时，因为汉明距离小于3则为重复文本，那么如果存在simhash相似的文本，对于四段simhash则至少有一段simhash是相同的，所以在去重时对于待判断文本D，如果D中每一段的simhash都没有相同的，那么D为无重复文本。

原理：

借鉴hashmap算法找出可以hash的key值，因为我们使用的simhash是局部敏感哈希，这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本，至少有16位的simhash是一样的。具体选择16位、8位、4位，大家根据自己的数据测试选择，虽然比较的位数越小越精准，但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。

实现

在实际NLP的使用中，我利用Murmur3作为字符串的64位哈希值，用Java和spark分别实现了一个simhash的版本

我将源码放在了github上，如下链接：

github: xlturing/simhashJava

其中利用了结巴作为文本的分词工具，Murmur3用来产生64位的hashcode。另外根据上述存储方式，进行了simhash分段存储，提高搜索速度，从而进行高效查重。

应用

simhash从最一开始用的最多的场景便是大规模文本的去重，对于爬虫从网上爬取的大规模语料数据，我们需要进行预处理，删除重复的文档才能进行后续的文本处理和挖掘，那么利用simhash是一种不错的选择，其计算复杂度和效果都有一个很好的折中。

但是在实际应用过程中，也发现一些badcase，完全无关的文本正好对应成了相同的simhash，精确度并不是很高，而且simhash更适用于较长的文本，但是在大规模语料进行去重时，simhash的计算速度优势还是很不错的。

语义相似性

在NLP中有时候我们度量两个短文本或者说更直接的两个词语的相似性时，直接通过字面距离是无法实现的，如：中国-北京，意大利-罗马，这两个短语之间的相似距离应该是类似的，因为都是首都与国家的关系；再比如（男人、男孩），（女人、女孩）应该是相同的关系，但是我们看其字面距离都是0。

想要做到语义层面的度量，我们需要用到机器学习建模，而自然语言的问题转化为机器学习的首要问题便是找到一种方法把自然语言的符号数学化。

接《NLP 点滴 ：文本相似度 （中）》