一种基于打分机制的文本相似度匹配算法

王宝山

摘 要：本文借用语音识别技术读取用户输入口令，对用户口令和机器指令分别进行分词处理并建立字典向量，字典向量都以用户口令中的文字作为键所以具有相同的维度，在向量的基础上对用户口令和机器指令进行夹角余弦计算以实现对机器指令的第一次打分；第二次打分则是在第一次打分的基础上进行，因为如果当用户口令和机器指令在所包含文字上已经相似，则有必要对文字的排列顺序做一个考察。本文通过提取用户口令中文字的關系对并与机器指令相比较的方式对机器指令进行一个顺序打分，最终挑选出文字与排序都与用户口令最相似的机器指令。

关键词：语音识别 字典向量 夹角余弦

中图分类号：TP18 文献标识码：A 文章编号：1672-3791（2018）02（a）-0059-02

如今计算机一词已经不再单纯指电脑，因为不论手机、电视机、洗衣机还是手表等许多种机器都可以被植入计算机系统，实现部分计算机的功能，虽然它们依然担当着不同的角色，实际上它们都在变得越来越同一、越来越智能。然而这些机器变得越来越强大时，随之带来的一个问题是，这些机器也变得越来越难于操控，即用户在享受这些机器带来的服务之前，学习如何使用它们反而成为了一种负担。比如许多中老年人想看电视时，结果就因为不会使用电视机盒子最后就不看了。机器越来越强大的时候却反而离人们越来越远，这绝不是机器的设计者们最初的理想，机器的设计应该朝着更人性化的方向前进。

本算法就是致力于打造一款面向人机交流的算法，设想通过人机交流的方式来操控机器，用户向机器输入相关的口令，机器识别这些口令并执行对应的功能，最后返回用户所需的服务。目前语音识别的技术已经较为成熟当，用户口令通过语音识别的方式输入机器，机器可以将用户的声音语言识别为书面语言，这给用户提供了很大的方便，当然也可以通过手动方式输入口令，但不管通过哪种方式，机器真正要做的是识别用户口令意图并执行对应功能。

1 研究思路

机器识别用户口令意图，并不是让机器去“听懂”用户口令的意思、“理解”用户语言表达的思想，实际上，机器目前是做不到这一点的。人类的语言应该分两个层面看待——物理层面和信息层面。物理层面即语言本身包含着哪些文字、这些文字个数以及这些文字的排列顺序，这是语言所包含的基础的信息；信息层面即语言背后的含义，也即人类所表达的思想。同一句话在不同的环境里可以表达不同的意思，这种现象正是由于人类能很好的理解、利用语言的第二个层面，而计算机却不行。

那么如何让机器识别出用户口令意图？这就需要利用好计算机本身的优点。计算机具有很好的记忆力和逻辑关系对应能力，它可以轻松地记住很多条指令、记住每个按钮该执行什么操作。本算法设想采用匹配的方式来让机器识别用户口令，即机器接收用户口令后从自己的指令库里寻找一条最匹配的机器指令并执行相关的操作，设计者们只需要把机器指令与机器操作建立一定的对应关系即可。到时机器便能够像听懂人类的话一般受用户摆布，而用户所需的只是一个机器的库指令清单，这样机器一定很受用户的欢迎。但是用户说出的口令可能是口语化的并不标准，甚至还包括很多方言，而且机器的语音识别技术也不一定能完全还原用户本来的语言，这就造成用户口令与机器指令产生一定偏差，导致机器检索相关指令出现困难。

本文考虑采用打分机制来匹配用户口令与机器指令，分值最高的机器指令将作为检索结果供机器执行。本打分机制主要分两个过程：第一个过程是利用夹角余弦公式对用户口令向量和机器指令向量就所包含文字的匹配度打一个分值，此时可以找出在包含文字上与用户口令最接近的机器指令，但可能不止一条，因为汉语的魅力是，许多词语或短语正着反着说可以表达不同的意思，这对机器来说却是一个麻烦。所以为了对用户口令和机器指令就文字排列顺序做一个相似度匹配，本文还要指出第二个打分过程——顺序打分。

2 算法步骤

本算法是基于python语言[1]设计实现的一款算法，主要涉及数学中的向量、夹角余弦等知识，以及python语言中的列表、集合、字典等工具，具体步骤如下所述：

2.1 建立向量

向量的建立要分两个方向：（1）用户口令向量的建立；（2）机器指令的向量列表的建立，因为机器指令不止一条，所以考虑将其向量以列表的形式存储。

2.1.1 建立用户口令向量

（1）将用户口令拆分成文字的列表，记为ul，这个列表要保持文字原本的顺序，因为文字的顺序作为语言的基础物理信息之一也很重要。

（2）以ul为基础生成集合，记为us。生成集合的目的是提取用户口令中的文字并去除重复的文字，因为集合不包含重复的项。这里值得一提的是，用户口令向量和机器指令向量的建立都要用到该集合。

（3）以字典的形式建立用户口令向量：这个字典的键是us中的项（文字），包含用户口令涉及的所有文字并且没有重复；键所对应的值则是这个键（文字）在ul中的个数。把这个向量记为uh。

2.1.2 建立机器指令向量列表

（1）考虑到机器指令不止一条，所以首先需要建立一个空列表，记为ml，这个列表用来存储所有机器指令。

（2）依次读取ml中的机器指令并拆分成以文字为基础的一维列表，然后将其存储到一个空的二位列表中，记为mll。

（3）依次读取mll中的每一条机器指令列表，以2.1.1中us里的文字为键、以该文字在所读取列表中的个数为值（若没该字，其值为0）建立机器指令向量并保存到一个列表中。最后生成的是一个向量列表，记为mvl。

2.2 夹角余弦打分

因为用户口令向量和机器指令向量是以相同的键建立的字典，所以它们具有相同的维度。夹角余弦的公式是[2]：

其中，mvl[i]为mvl中第i条向量。之所以建立字典形式的向量，就是为了方便求两向量的点积。因为字典的一个键就代表向量的一个维度，如果两字典向量具有相同的键，那么它们就具有相同的维度，这样一来很容易对它们的值计算点积。向量的模即向量的长度，其计算方法不再赘述。

利用夹角余弦公式可以给每一条机器指令打分，但是我们必须要让指令与所得的分值对应起来才行，所以我们依然选择采用字典的形式保存计算结果。这个字典的键取机器指令向量在mvl中的索引、其值则是该向量获得的分数，将这个字典记为r1。因为mvl、mll、ml这3個列表是一一对应的，所以r1保存的索引对3个列表来说是通用的。

获取了向量分值之后，就要提取得分最高的机器指令，这个过程可以简单描述为，在r1中找分值最高的索引，然后根据索引在mll中找出对应的机器指令。如果分值最高的机器指令只有一条（至少有一条，假使全部向量都得0分，那么所有指令都是得分最高的，尽管此时可以特别返回一条请用户重新输入的提示）则结束，否则就要进行第二个过程打分——顺序打分。注意到分值最高机器指令是从mll中提取的，所以这些指令依然是以指令列表的形式存在，这是因为顺序打分算法依然是在指令列表的基础上实现的。又因为分值最高指令列表不止一条，所以考虑以二位列表存储这些一维列表，记为tll。

2.3 顺序打分算法

顺序打分算法的思路是这样的：对于用户口令生成的文字列表ul，它保留了原始口令中文字的顺序，这种顺序关系将作为我们给机器指令打分的依据。

具体地说，用户口令列表中任意两个字之间都具有一个先后顺序关系，我们称之为一个关系对，如果用户口令的字数为n，则这种关系对的个数为。依次取tll中的机器指令列表，通过两层循环给该机器指令打分：第一层循环依次取用户口令列表中第一个字到倒数第二个字，第二层循环则依次取第一层循环中所取字之后的字，这样两层循环分别取两个字，并且在用户口令列表中第一个字排在第二个字前面，如果在机器指令列表中第一个字也是排在第二个字的前面，则给机器指令加1分。判断这两个字在机器指令列表中的顺序关系是根据这两个字的索引，如果第一个字的索引小于第二个字，则说明第一个字排在第二个字的前面。如果两个字中的某个字在机器指令列表中不存在，或者第一个字的索引大于第二个字，则机器指令不加分。两层循环遍历完成后，这条机器指令会获得一个分数，我们依然以索引——分数的形式保存在字典里，记为r2。这样就实现了对机器指令的顺序打分，最后根据分值把得分最高的机器指令检索出来即可。

3 具体实施

下面假设一台电视机包含如下指令：调高音量、调高亮度、切换到10频道、频道切换、清理内存、打开内存清理工具；用户输入口令为：清理内存。则本算法的整个执行过程描述如下：ul=[清，理，内，存]；us=set（[清，理，内，存]）；ml=[调高音量，调高亮度，切换到10频道，频道切换，清理内存，打开内存清理工具]；mll=[[调，高，音，量]，[调，高，亮，度]，[切，换，到，10，频，道]，[频，道，切，换]，[清，理，内，存]，[打，开，内，存，清，理，工，具]]；uh={清：1，理：1，内：1，存：1}；mvl=[{调：0，高：0，音：0，量：0}，{调：，高：0，亮：0，度：0}，{切：0，换：0，到：0，10：0，频：0，道：0}，{频：0，道：0，切：0，换：0}，{清：1，理：1，内：1，存：1}，{打：0，开：0，内：1，存：1，清：1，理：1，工：0，具：0}]。通过夹角余弦公式为每一条指令打分，打分的结果保存在r1中：r1={0：0，1：0，2：0，3：0，4：1.0，5：1.0}；第一步打分过程中分数最高的是清理内存和打开内存清理工具，分数都是1.0分，所以接下来还要进行第二步打分：tll=[[清，理，内，存]，[打，开，内，存，清，理，工，具]]；r2={0：6，1：2}，结果显示机器指令中清理内存分数最高，因此这条指令将被执行。

参考文献

[1] 埃里克·马瑟斯，著.Python编程从入门到实践[M].袁国忠，译.北京：人民邮电出版社，2016.

[2] 刘玉莲，傅沛仁，林玎.数学分析讲义[M].北京：高等教育出版社，2008.