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

王寶山

摘 要：本文借用語音識別技術讀取用戶輸入口令，對用戶口令和機器指令分別進行分詞處理并建立字典向量，字典向量都以用戶口令中的文字作為鍵所以具有相同的維度，在向量的基礎上對用戶口令和機器指令進行夾角余弦計算以實現對機器指令的第一次打分；第二次打分則是在第一次打分的基礎上進行，因為如果當用戶口令和機器指令在所包含文字上已經相似，則有必要對文字的排列順序做一個考察。本文通過提取用戶口令中文字的關系對并與機器指令相比較的方式對機器指令進行一個順序打分，最終挑選出文字與排序都與用戶口令最相似的機器指令。

關鍵詞：語音識別 字典向量 夾角余弦

中圖分類號：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.