文本匹配算法综述

文本匹配任务在自然语言处理中是非常重要的基础任务之一，有很多应用场景；如信息检索、问答系统、文本数据去重等。文本匹配算法按有无训练集可分为有监督算法和无监督算法；按算法的发展阶段可分为传统算法和深度算法。常见的算法如下：...

井底哇哇

9589人浏览 · 2021-07-09 14:48:15

井底哇哇 · 2021-07-09 14:48:15 发布

文本匹配，顾名思义，就是描述两段文本之间的关系，是否指向同一语义；比如两句话是否描述同一件事，或者两句话是否是上下文/问题与答案的关系。例：

小宝宝生病怎么办	狗宝宝生病怎么办
明天天气怎么样	明天预报有雨
先帝创业未半而中道崩殂	今天下三分，益州疲弊，此诚危急存亡之秋也

文本匹配任务在自然语言处理中是非常重要的基础任务之一，有很多应用场景；如信息检索、问答系统、智能对话、文本鉴别、智能推荐、文本数据去重等，但文本匹配或者说自然语言处理仍然存在很多难点。

如语言不规范，同一句话可以有多种表达方式；如“股市跳水、股市大跌、股市一片绿”

歧义，同一个词语或句子在不同语境可能表达不同意思；如“割韭菜”，“领盒饭”，“能穿多少穿多少”，在不同语境下语义完全不同

不规范或错误的输入；如 “ yyds”，“举个栗子”

需要知识依赖；如丰田supra绰号“牛魔王”等。

常见的文本匹配算法如下表，按传统模型和深度模型简单的分为两类：

算法	类型
Jaccord	传统模型
BM25	传统模型
VSM	传统模型
SimHash	传统模型
Levenshtein	传统模型
cdssm	深度模型
arc-ii	深度模型
match_pyramid	深度模型
mvlstm	深度模型
bimpm	深度模型
drcn	深度模型
esim	深度模型
textmatching	深度模型
bert-base	深度模型
albert-base	深度模型
albert-large	深度模型
raberta	深度模型
sbert	深度模型

接下来，让我们通过一个例子，来具体看一下各个算法的实现过程及匹配效果（其中并没有实现深度学习类算法）。

举个栗子：

序号	句1	句2	真实结果
1	内蒙古锡林郭勒盟多伦县县医院	多伦县医院	1（匹配）
2	绵阳市四零四医院	四川绵阳404医院	1（匹配）
3	邓州市人民医院	南召县人民医院	0（不匹配）

1.Jaccard杰卡德相似系数

jaccard相似度是一种非常直观的相似度计算方式，即两句子分词后词语的交集中词语数与并集中词语数之比。

$jaccard = \frac{A\bigcap B}{A\bigcup B}$

def jaccard(list1, list2):
    """
    jaccard相似系数
    :param list1:第一句话的词列表 
    :param list2: 第二句话的词列表
    :return:相似度，float值 
    """
    list1, list2 = set(list1), set(list2) #去重
    intersection = list1.intersection(list2) # 交集
    union = list1.union(list2)  # 并集
    Similarity = 1.0 * len(intersection) / len(union) #交集比并集
    return Similarity

a.分词

内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院

绵阳市四零四医院 / 四川绵阳 404 医院

邓州市人民医院 / 南召县人民医院

b.去重求交集--并集

多伦县（交集） -- 内蒙古、锡林郭勒盟、多伦县、县医院、医院（并集）

医院（交集） -- 绵阳市、四、零、医院、四川、绵阳、404（并集）

人民、医院（交集） -- 邓州市、人民、医院、南召县（并集）

c.相似度

文本对	相似度	真实标签
内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院	1/5=0.2	1
绵阳市四零四医院 / 四川绵阳 404 医院	1/7 = 0.14	1
邓州市人民医院 / 南召县人民医院	2/4 = 0.5	0

2.Levenshtein编辑距离

一个句子转换为另一个句子需要的编辑次数，编辑包括删除、替换、添加，然后使用最长句子的长度归一化得相似度。

def Levenshtein(text1, text2):
    """
    Levenshtein编辑距离
    :param text1:字符串1
    :param text2:字符串2
    :return:相似度，float值
    """
    import Levenshtein
    distance = Levenshtein.distance(text1, text2)
    Similarity = 1 - distance * 1.0 / max(len(text1), len(text2))
    return Similarity

a.分词-计字数

内蒙古锡林郭勒盟多伦县县医院（14） / 多伦县医院（5）

绵阳市四零四医院（8） / 四川绵阳 4 0 4 医院（9）

邓州市人民医院（7） / 南召县人民医院（7）

b.计算编辑距离

内蒙古锡林郭勒盟多伦县县医院 ------->删除内、蒙、古、锡、林、郭、勒、盟、县

绵阳市四零四医院 ------->加四、川

------->删除市

------->替换四（4）、零（0）、四（4）

邓州市人民医院 ------->替换邓（南）、州（召）、市（县）

文本对	距离	真实标签
内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院	0.357	1
绵阳市四零四医院 / 四川绵阳 404 医院	0.333	1
邓州市人民医院 / 南召县人民医院	0.571	0

3 simhash相似度

先计算两句子的simhash二进制编码，然后使用海明距离计算，最后使用两句的最大simhash值归一化得相似度。

def simhash_(text1, text2):
    """
    simhash相似度
    :param s1: 字符串1
    :param s2: 字符串2
    :return: 相似度，float值
    """
    from simhash import Simhash
    text1_simhash = Simhash(text1, f=64)  #计算simhash向量
    text2_simhash = Simhash(text2, f=64)  #计算simhash向量
    distance = text1_simhash.distance(text2_simhash)  #汉明距离
    Similarity = 1 - distance / max(len(bin(text1_simhash.value)), len(bin(text2_simhash.value))) #相似度
    return Similarity

a.分词

内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院

绵阳市四零四医院 / 四川绵阳 404 医院

邓州市人民医院 / 南召县人民医院

b.计算词权重(此处用tfidf计算，其他方法也可以)

内蒙古5	锡林郭勒盟5	多伦县2	县医院5	多伦县7	医院1
绵阳市3	四6	零3	四6	医院1	四川5	绵阳5	4045	医院1
邓州市7	人民4	医院1	南召县7	人民4	医院1

c.hash函数映射词向量；先将词映射到二进制编码，然后用b步骤中的权重值替换1，b步骤中权重值的负数替换0

词	二进制编码	加权重
内蒙古	1111000	-5 5 5 5 5 -5 -5 -5
锡林郭勒盟	1100000	-5 5 5 -5 -5 -5 -5 -5
多伦县	1111011	-2 2 2 2 2 -2 2 2
县医院	10110010	5 -5 5 5 -5 -5 5 -5
多伦县	1111011	-7 7 7 7 7 -7 7 7
医院	10010001	1 -1 -1 1 -1 -1 -1 1
绵阳市	10111111	3 -3 3 3 3 3 3 3
四	11100100	6 6 6 -6 -6 6 -6 -6
零	1011110	-3 3 -3 3 3 3 3 -3
四	11100100	6 6 6 -6 -6 6 -6 -6
医院	10010001	1 -1 -1 1 -1 -1 -1 1
四川	1100001	-5 5 5 -5 -5 -5 -5 5
绵阳	111010	-5 -5 5 5 5 -5 5 -5
404	1010	-5 -5 -5 -5 5 -5 5 -5
医院	10010001	1 -1 -1 1 -1 -1 -1 1
邓州市	10101011	7 -7 7 -7 7 -7 7 7
人民	10001011	4 -4 -4 -4 4 -4 4 4
医院	10010001	1 -1 -1 1 -1 -1 -1 1
南召县	11101010	7 7 7 -7 7 -7 7 -7
人民	10001011	4 -4 -4 -4 4 -4 4 4
医院	10010001	1 -1 -1 1 -1 -1 -1 1

d.合并（将一段文本内的词向量进行累加）

文本	合并向量	simhash值
内蒙古锡林郭勒盟多伦县县医院	-7 7 17 7 -3 -17 -3 -13	-1 1 1 1 -1 -1 -1 -1
多伦县医院	-6 6 6 8 6 -8 6 8	-1 1 1 1 1 -1 1 1
绵阳市四零四医院	13 11 11 -5 -7 17 -7 -11	1 1 1 -1 -1 -1 -1 -1
四川绵阳 404 医院	-14 -6 4 -4 4 -16 4 -4	-1 -1 1 -1 1 -1 1 -1
邓州市人民医院	12 -12 2 -10 10 -12 10 12	1 -1 1 -1 1 -1 1 1
南召县人民医院	12 2 2 -10 10 -12 10 -2	1 1 1 -1 1 -1 1 -1

e海明距离判断相似度

简单的说，海明距离可以理解为，两个二进制串之间相同位置不同的个数。举个例子，[1，1，1，0，0，0]和[1，1，1，1，1，1]的海明距离就是3。

文本对	海明距离	真实标签
内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院	3	1
绵阳市四零四医院 / 四川绵阳 404 医院	4	1
邓州市人民医院 / 南召县人民医院	2	0

4 Bm25相似度

一句话概况其主要思想：对Query（待查询语句）进行语素解析，生成语素qi；然后，对于每个搜索结果D，计算每个语素qi与D的相关性得分，最后，将qi相对于D的相关性得分进行加权求和，从而得到Query与D的相关性得分。

其中，Q表示Query，qi表示Q解析之后的一个语素（对中文而言，我们可以把对Query的分词作为语素分析，每个词看成语素qi。）；d表示一个搜索结果文档；Wi表示语素qi的权重，为词语的逆文档频率；R(qi，d)表示语素qi与文档d的相关性得分。

其中，N是待匹配总文本数

n(qt)是出现当前词的文本数

其中 f(qi, D)为单词在当前候选文档中的词频

k1、b为调节因子，通常设为k1=2，b=0.75

|D|为当前候选文本数（与目标文本匹配的总条数）

avgdl为语料库中所有文档的平均长度。

#Bm25
import math
import jieba
class BM25(object):
    def __init__(self, docs):#docs是一个包含所有文本的列表，每个元素是一个文本
        self.D = len(docs)  #总文本数
        self.avgdl = sum([len(doc)+0.0 for doc in docs]) / self.D   #平均文本长度
        self.docs = docs #文本库列表
        self.f = []  # 列表的每一个元素是一个dict，dict存储着一个文档中每个词的出现次数
        self.df = {} # 存储每个词及出现了该词的文档数量
        self.idf = {} # 存储每个词的idf值
        self.k1 = 1.5
        self.b = 0.75
        self.init()

    def init(self):
        for doc in self.docs:  #对每个文本
            tmp = {}   #定义一个字典存储词出现频次
            for word in doc:
                tmp[word] = tmp.get(word, 0) + 1  # 存储每个文档中每个词的出现次数
            self.f.append(tmp)
            for k in tmp.keys():
                self.df[k] = self.df.get(k, 0) + 1
        for k, v in self.df.items():
            self.idf[k] = math.log(self.D-v+0.5)-math.log(v+0.5) #计算idf

    def sim(self, doc, index):
        score = 0
        for word in doc:
            if word not in self.f[index]:
                continue
            d = len(self.docs[index])
            score += (self.idf[word]*self.f[index][word]*(self.k1+1)
                      / (self.f[index][word]+self.k1*(1-self.b+self.b*d
                                                      / self.avgdl)))
        return score

    def simall(self, doc):
        scores = []
        for index in range(self.D):
            score = self.sim(doc, index)
            scores.append(score)
        return scores

if __name__ == '__main__':
    sents1 = ["多伦县医院",  #数据库
                "四川绵阳404医院",
               "南召县人民医院"]
    sents2 = ["内蒙古锡林郭勒盟多伦县县医院","绵阳市四零四医院","邓州市人民医院"]#待匹配文本
    doc = []
    for sent in sents1:
        words = list(jieba.cut(sent))
        doc.append(words)
    print(doc)
    s = BM25(doc)
    print(s.f)
    print(s.idf)
    for k in sents2:
        print(s.simall(jieba.lcut(k))) #打印相似度匹配结果

	内蒙古锡林郭勒盟多伦县县医院	绵阳市四零四医院	邓州市人民医院
多伦县医院	-1.68	-1.69	-1.94
四川绵阳 404 医院	-2.28	-1.69	-1.94
南召县人民医院	-2.28	-1.69	-1.43

5. VSM算法

VSM算法的思路主要分为两步：

(1) 用向量表示句子,用向量表示句子的方法很多，简单的有onehot，词频法，基于语义的有word2vec/fastText/glove/bert/elmo等，本例中使用基于简单的词频的向量化方式。

(2)计算两向量的余弦距离（曼哈顿距离、欧几里得距离、明式距离、切比雪夫距离）得相似度。

#tfidf_余弦
def sim_vecidf(self, s1, s2):
    """词向量通过idf加权平均后计算余弦距离"""
    v1, v2 = [], []
    # 1. 词向量idf加权平均
    for s in jieba.cut(s1):
        idf_v = idf.get(s, 1)
        if s in voc:
            v1.append(1.0 * idf_v * voc[s])
    v1 = np.array(v1).mean(axis=0)
    for s in jieba.lcut(s2):
        idf_v = idf.get(s, 1)
        if s in voc:
            v2.append(1.0 * idf_v * voc[s])
    v2 = np.array(v2).mean(axis=0)
    # 2. 计算cosine
    sim = self.cosine(v1, v2)
    return sim

a.句子向量化

a1.取句子对的唯一词元组

set(内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院) = (内蒙古锡林郭勒盟多伦县县医院医院)

set(绵阳市四零四医院 / 四川绵阳 404 医院) = (绵阳市四零医院四川绵阳 404 )

set(邓州市人民医院 / 南召县人民医院) = (邓州市人民医院南召县)

a2.根据每个句子在元组中的词频建立向量表示

句子	向量
内蒙古锡林郭勒盟多伦县县医院	1 1 1 1 0
多伦县医院	0 0 1 0 1
绵阳市四零四医院	1 2 1 1 0 0 0
四川绵阳 404 医院	0 0 0 1 1 1 1
邓州市人民医院	1 1 1 0
南召县人民医院	0 1 1 1

b.计算余弦距离

$Cos(x1,x2) =\frac{x1\cdot x2}{|x1||x2|}$

句子	距离
内蒙古锡林郭勒盟多伦县县医院 / 多伦县医院	0.3535
绵阳市四零四医院 / 四川绵阳 404 医院	0.1889
邓州市人民医院 / 南召县人民医院	0.6666

6.BERT模型+余弦相似度

BERT是谷歌在2018年推出的深度语言表示模型，是关于语言理解的深度双向transformers的预训练模型，开启了预训练模型的新篇章。它可以学习文本的语义信息，通过向量形式的输出可以用于下游任务。也就说，它自己已经在大规模预料上训练好的参数，我们在用的时候只需要在这个基础上训练更新参数。bert模型可以解决多种自然语言处理问题，如单文本分类、语句对分类、序列标注等。在解决文本匹配任务时，有两种思路，第一种直接把文本匹配任务作为语句对分类任务，模型输入语句对，输出是否匹配的标签；第二种利用bert模型预训练文本对的上下文嵌入向量，再通过余弦相似度等相似度计算方法验证文本对是否匹配，在此基础上还有很多基于bert模型的变种，篇幅有限不做一一讲述。BERT模型详情请转：(2条消息) 图解Transformer（完整版）_龙心尘-CSDN博客_transformer，在此不做赘述。接下来简单介绍一下bert预训练文本嵌入+余弦相似度的算法框架。

a.首先使用大量公域文本数据对BERT模型进行预训练（或直接用谷歌预训练好的模型）

b.将文本直接输入模型

c.对模型输出的语义向量C，或中间隐层向量，计算余弦相似度，得到匹配结果。

一种基于深度学习BERT算法的短文本相似匹配的方法与流程

基于深度学习的匹配算法种类繁多，如基于CNN网络、RNN网络、LSTM网络等及各种变种层出不穷，在此不一一列举实现。

传统的文本匹配方法主要关注文本间字与字，词与词的匹配关系，无法准确识别不同表达方式下不同文本的同一指向关系，即语义关系。因此在这一背景下，要对多源异构的海量地址数据进行匹配，传统的文本匹配方法已不再适用，深度学习方法大行其道。但深度学习方法也有自身的局限性，比如对海量文本和算力的高要求等，都使得深度学习方法的普适性大打折扣，因此没有最好的文本匹配算法，只有当前条件下最适合的文本匹配算法。

参考文献：

传统文本匹配算法详解（附代码） - 知乎 (zhihu.com)

文本匹配利器：从孪生网络到Sentence-BERT综述 (360doc.com)

(2条消息) SimHash算法原理_qq_33905939的博客-CSDN博客

一种基于深度学习BERT算法的短文本相似匹配的方法 - 百度文库 (baidu.com)

深度学习文本匹配简述 - ZhangHT97 - 博客园 (cnblogs.com)

文本匹配模型TextMatching - 简书 (jianshu.com)

(2条消息) BERT模型的结构，特点和实践_dream6104的专栏-CSDN博客_bert模型结构