改進Jaro-Winkler算法在迎賓機器人語音交互中的應用

吳凌芬，楊小淵，葉添杰，劉冰，王太宏

（1.廈門大學信息科學與技術學院，廈門　361005；2.廈門大學薩本棟微米納米科學技術研究院，廈門　361005）

改進Jaro-Winkler算法在迎賓機器人語音交互中的應用

吳凌芬1，楊小淵2，葉添杰2，劉冰2，王太宏2

（1.廈門大學信息科學與技術學院，廈門361005；2.廈門大學薩本棟微米納米科學技術研究院，廈門361005）

0　引言

隨著計算機和人工智能的快速發展，迎賓機器人受到越來越多的關注，具有廣闊的市場應用前景。語音作為人類與機器人溝通最便捷最自然的交互方式之一，提升了人機交互的友好性。語音交互是目前機器人研究的熱點之一，包含語音識別和語音合成。文獻［1］提出一個通過識別手勢提供語音合成的導游機器人，文獻［2～4］采用語音識別技術提取語音命令用于機器人控制，這些文獻研究了少量特定詞匯的語音識別和語音合成，不能滿足迎賓機器人的需求。迎賓機器人必須能與人進行和諧、自然的語音交互，需要擁有大量的詞匯才能實現其迎賓功能，因此本文設計了具有豐富內容的本地文本數據庫，結合小黃雞的在線數據庫，構成迎賓機器人語音交互的語言庫。

在語音交互過程中，通過字符串匹配獲取語言庫中的回復文本，目前主要的字符串匹配算法有Jaro算法、Jaro-Winkler算法、Levenshtein算法和Smith Waterman算法等［5］，其中Jaro-Winkler算法通常被用于短字符串的相似度計算［6］。已知Jaro-Winkler算法在計算兩個字符串的相似度時，只考慮了字符的換位次數，未考慮字符的刪除和插入的編輯操作數，因此存在不具備普遍適用性、語義不同的字符串相似度值過大等問題。為此，本文提出了一種改進Jaro-Winkler算法的方法，并以Android手機作為迎賓機器人的主控處理器，利用攝像頭采集圖像數據［7］，采用Wi-Fi和藍牙無線通信，基于語音識別和人臉檢測技術，應用改進的Jaro-Winkler算法實現了迎賓機器人語音交互系統。

1　基本的Jaro-Winkler算法

Jaro-Winkler算法是Jaro算法的變種，它是計算兩個字符串之間的相似度的一種算法，計算結果為0時相當于無相似性，計算結果為1則是完全匹配［8］。字符串s1和字符串 s2通過Jaro算法計算的相似度dj值為：

其中|s1|和|s2|分別為s1和s2的字符串長度，m為匹配的字符數，t為換位的數目。定義匹配窗口MW的計算公式為：

當字符串s1中一個字符與字符串s2中的一個字符相匹配，但是位置不一樣需要換位操作時，如果這兩個字符的距離不大于MW，則這兩個字符為匹配字符，t為發生換位操作的匹配字符數目的一半［9］。例如，設兩個字符串，s1=“小偷來這邊了”，s2=“小邊來這偷了”，此時MW為2，其中字符串s1中的 “偷”和字符串s2中的“偷”字符是匹配的，但是位置不同，且兩個字符的距離為2，不大于MW，因此“偷”為發生換位操作的匹配字符。同理，“邊”也是發生換位操作的匹配字符，因此t為1。

Jaro-Winkler算法定義了一個前綴范圍p，字符串s1和字符串s2通過Jaro-Winkler算法計算的相似度dw值為:

其中，p的范圍為（0～0.25），默認值為0.1，l是字符串s1和字符串s2的前綴部分匹配長度。

2　改進Jaro-Winkler算法

2.1改進的相似度計算公式

公式（1）不具有普遍適用性，例如，設字符串s1= “ABCDEFGHIJ”，字符串s2=“AICDEFGHBJ”，計算出的相似度dj=1，則dw=1，表示完全匹配，但顯然s1和s2并不完全匹配。因此，本文結合Levenshtein算法、換位數目t和相同字符數m定義新的相似度計算公式。Levenshtein distance指兩個字符串之間的編輯距離，即由一個字符串轉換成另一個字符串所需的最少編輯操作次數［10］，編輯操作包括插入一個字符、刪除一個字符和替換一個字符，則公式（1）改進為：

其中ld為編輯距離，pd定義為關聯系數，范圍為（0～1），m為匹配的字符數，t為換位的數目。

2.2關聯系數pd值

為了確定最適用于本文的關聯系數pd值，通過三組詞語構成類似的字符串組，計算pd取不同值時的字符串相似度值。三組字符串組如表1所示，其中1組和2組是語義相近的字符串組，1組和3組是語義不同的字符串組。

表1　用于算法對比的三組字符串

運用Jaro-Winkler算法和改進的Jaro-Winkler算法，分別計算1組和2組字符串、1組和3組字符串的相似度值，計算得出的相似度曲線如圖1所示，其中，0＜pd＜1，pd的步長為0.1。

圖1　Jaro-Winkler算法和不同pd值下改進Jaro-Winkler算法的相似度曲線

由圖1可知，同等條件下，隨著pd的增大，計算出的相似度值減小，而相同的pd值，1組和3組計算出的相似度與Jaro-Winkler算法計算的相似度差值比1組和2組大，即pd值對語義不同的字符串組的影響更大。為了提高字符串匹配的準確率，減少誤判，語義相近的字符串計算得到的相似度值越大越好，語義不同的字符串計算得到的相似度值越小越好，因此在這兩種情況下計算的相似度差值越大的pd越適用于本文。由圖1可知，當pd=0.4時，該pd值下的相似度曲線與Jaro-Winkler算法的曲線趨勢類似，1組和2組的相似度值與Jaro-Winkler算法的差值較小，1組和3組的相似度值與Jaro-Winkler算法的差值較大，因此1組和2組與1組和3組的相似度差值明顯地增加了。在這種情況下，字符串匹配能夠有效地排除語義不同的字符串，因此pd值默認為0.4。

2.3匹配字符串長度有效范圍

假設s1的字符串長度為m，s2的字符串長度為n，如果n＜m/2或者n＞2m，則默認字符串s1和字符串s2不匹配，定義s1的匹配字符串長度有效范圍為［m/ 2，2m］。因此，在字符串s1與字符串s2進行字符串匹配之前，對兩個字符串的長度進行比較，如果s2的字符串長度不在s1的匹配字符串長度有效范圍內，則s1與s2不匹配，因此該方法能夠節省s3與匹配字符串長度有效范圍外的字符串匹配的時間。

2.4改進算法數值分析

為了驗證本文提出的改進Jaro-Winkler算法，通過Java語言實現算法過程，并用MATLAB進行數值分析。對80個語義不同的字符串組和20個語義相近的字符串組，用改進的Jaro-Winkler算法和Jaro-Winkler算法計算相似度，結果如圖2所示。

圖2　改進Jaro-Winkler算法和Jaro-Winkler算法計算的相似度值對比

由圖2可知，相似度值越大，兩條相似度曲線的差異越小，相似度值越小，兩條相似度曲線的差異越大，所以改進算法能明顯減小語義不同的字符串的相似度，能夠解決Jaro-Winkler算法計算語義不同字符串的相似度值過大，容易將不匹配的字符串誤判成匹配字符串的問題，因此改進Jaro-Winkler算法的字符串匹配準確度比Jaro-Winkler高。定義改進算法的字符串匹配閾值為0.8，即在計算兩個字符串的相似度值時，如果值大于等于0.8，則兩個字符串默認是匹配的，否則不匹配。

從數據庫中隨機取出字符串長度從1～26的字符串各20個，共有520個字符串，運用Java語言，將字符串長度從2～13的12個字符串分別用Jaro-Winkler算法和改進的Jaro-Winkler算法與這520個字符串進行匹配，20次實驗的平均運行時間如圖3所示。

圖3　改進Jaro-Winkler算法與Jaro-Winkler算法運行時間對比

由圖3可知，Jaro-Winkler算法及其改進算法的運行時間都隨著字符串長度的增大而增大。由于迎賓機器人語音交互的字符串長度主要在7～10之間，并且短字符串的使用頻率大于長字符串，因此從總體上來說，改進Jaro-Winkler算法的運行時間近似于Jaro-Winkler算法，即改進算法能夠在不增加算法運行時間的條件下，提高字符串匹配的準確度。

3　改進Jaro-Winkler算法的應用

3.1總體設計方案

迎賓機器人語音交互系統的總體設計方案如圖4所示，系統以Android手機作為主控處理器［11］，由類人的迎賓機器人、機械手臂和控制板等構成。其中控制板和舵機嵌入在迎賓機器人的手臂中，Android手機嵌入在迎賓機器人的頭部，通過Android手機的攝像頭進行人臉檢測，通過Wi-Fi通信連接訊飛語音服務器和小黃雞網站服務器，結合本地文本數據庫實現語音識別和語音合成。

系統由通信模塊、MCU（Micro Control Unit）控制單元、電源模塊和電機模塊四個部分構成。其中控制板的控制芯片采用意法半導體推出的8位單片機STM8S003F，同時提供多個外設接口，具有模塊化、可靠性強、易拓展等優點。

圖4　系統總體設計方案

圖5　軟件設計流程圖

3.2軟件設計

迎賓機器人語音交互系統的軟件設計如圖5所示，由Android手機和機械手臂控制兩大部分組成。Android手機與機械手臂控制部分藍牙連接成功后，開啟手機攝像頭采集圖像信息并進行實時人臉檢測，如果檢測到人臉，則進行語音識別，如果沒有識別到語音，系統會重新進行人臉檢測；如果語音識別成功，則會輸出相應的語音合成，并通過藍牙通信向機械手臂控制部分發送控制指令，使機器人完成指定的迎賓動作。

由于語言的豐富度和靈活性，所以本系統需要配置擁有大量的輸入文本和回復文本的語言庫，包括本地SQLite數據庫和小黃雞聊天機器人數據庫。通過Java代碼生成本地文本數據庫strings和相應的字符串長度數據庫length。數據庫表strings中存儲了id號，輸入文本和回復文本。

圖6　語音交互流程圖

本文的語音交互模塊使用“訊飛語音”提供的語音服務接口，實現語音識別和語音合成［12］。語音交互模塊的流程圖如圖6所示，當語音交互開始時，系統調用訊飛語音識別函數將麥克風輸入的語音信號識別為文本，然后運用改進的Jaro-Winkler算法與本地文本數據庫strings中的輸入文本依次進行字符串匹配。如果計算的相似度值大于等于匹配閾值（0.8），則根據id輸出相應的回復文本，否則通過HTTP通信獲取小黃雞聊天機器人的回復文本。最后將獲取的回復文本進行語音合成，通過手機揚聲器輸出語音信號。

3.3測試結果與分析

測試迎賓機器人的語音交互系統，結果如圖7所示，根據Android手機顯示的語音識別文本、回復文本和語音合成結果統計正確率。在數據庫strings中隨機選取100個輸入文本字符串與迎賓機器人進行語音交互，此時語音識別正確率為98%，字符串匹配正確率為100%，語音合成正確率為98%；用100個與隨機選取的字符串語義相似而詞語構成不同的字符串進行語音交互時，語音識別正確率為97%，字符串匹配正確率為96%，語音合成正確率97%。因此，應用改進的Jaro-Winkler算法能夠實現高正確率的迎賓機器人語音交互。

本文的數據庫是可修改、刪除和插入內容的，具有擴展性，并能與靈活多變的語音交互內容進行字符串匹配，與其他識別特定詞匯的機器人語音交互相比［1～4］，本系統能夠識別和回復更豐富的內容，并且能夠應用到各種場合，應用前景廣泛。

4　結語

本文基于編輯距離改進Jaro-Winkler算法，提高了字符串匹配的準確度，且更具有普遍適用性。應用改進的Jaro-Winkler算法和開源、可移植的Android系統設計了迎賓機器人語音交互系統，能夠實現人臉檢測、語音識別、語音合成和無線控制機械手臂等功能。迎賓機器人語音交互系統應用改進的Jaro-Winkler算法，基于語言豐富，方便修改、刪除和插入的本地文本數據庫，能夠識別和回復更多的內容。本系統提供軟件接口，能實現更多的擴展功能，如天氣查詢、來賓咨詢和引導等，硬件電路也預留了多個接口，能接入各種傳感器，具有強大的擴展能力與應用前景。

圖7　語音交互系統測試結果

［1］Alvarez-Santos V,Iglesias R,Pardo X M,et al.Gesture-Based Interaction with Voice Feedback for a Tour-Guide Robot［J］.Journal of Visual Communication and Image Representation,2014,25（2）:499～509

［2］Martínez J A,Ubeda A,Iá?ez E,et al.Multimodal System Based on Electrooculography and Voice Recognition to Control a Robot Arm ［J］.International Journal of Advanced Robotic Systems,2013,10

［3］靳祖光,陳超,唐堅.一種室內導盲機器人的RFID-語音交互系統設計［J］.自動化儀表,2013,35（3）:73～76

［4］閔華松,劉冬,王田苗.智能機器狗的語音控制模型研究［J］.計算機工程,2012,38（01）:188～191

［5］Abandah G A,Jamour F T.A Word Matching Algorithm in Handwritten Arabic Recognition Using Multiple-Sequence Weighted Edit Distances［J］.International Journal of Computer Science Issues（IJCSI）,2014,11（3）

［6］Suzuki K M F,Porto Filho C H,Cozin L F,et al.Deterministic Record Linkage versus Similarity Functions:A Study in Health Databases from Brazil［C］.MedInfo.2013:562～566

［7］龔瑞琴,畢利.基于Web Service的Android技術應用研究［J］.電子技術應用,2014,40（1）:134～136

［8］Dumitrescu S R,Branescu-Raspop I,Popescu D.Format Mediation for Matching Patient Records in a Three-Layer Information Architecture［C］.Electrical and Electronics Engineering（ISEEE）,2013 4th International Symposium on.IEEE,2013:1～5

［9］Hancox P,Polatidis N.An Evaluation of Keyword,String Similarity and Very Shallow Syntactic Matching for a University Admissions Processing Infobot［J］.Computer Science and Information Systems/ComSIS,2013,10（4）:1703～1726

［10］姜華,韓安琪,王美佳,等.基于改進編輯距離的字符串相似度求解算法［J］.計算機工程,2014,40（1）:222～227

［11］江燕良.基于Android智能終端的遠程控制系統［J］.電子技術應用,2012,38（8）:129～132

［12］付蔚,唐鵬光,李倩.智能家居語音控制系統的設計［J］.自動化儀表,2013,35（1）:46～50

Jaro-Winkler Distance；Reception Robot；Speech Interaction；Strings Matching

Application of Improved Jaro-Winkler Distance in Speech Interaction of Reception Robot

WU Ling-fen1，YANG Xiao-yuan2，YE Tian-jie2，LIU Bing2，WANG Tai-hong2
（1.School of Information Science and Engineering,Xiamen University,Xiamen 361005；
2.School of Pen-Tung Sah Institute of Micro-Nano Science and Technology,Xiamen University,Xiamen 361005）

1007-1423（2015）08-0008-06

10.3969/j.issn.1007-1423.2015.08.002

吳凌芬（1990-），女，福建人，碩士研究生，研究方向為物聯網技術以及軟件工程

楊小淵（1990-），女，福建人，碩士研究生，研究方向為機器人底層運動控制

葉添杰（1990-），男，福建人，碩士研究生，研究方向為機器人技術

劉冰（1991-），女，山西人，碩士研究生，研究方向為嵌入式硬件開發以及軟件工程

王太宏（1966-），男，湖北人，教授，博導，博士，研究方向為鋰電、傳感和物聯網

2015－01－27

2015－03－04

針對Jaro-Winkler算法在計算兩個字符串的相似度時只考慮字符的換位數目，未考慮字符插入和刪除編輯操作的問題，提出一種基于Levenshtein算法改進Jaro-Winkler算法的方法。通過改進相似度的計算公式和調整關聯系數pd，實現Jaro-Winkler算法的改進，提高字符串匹配的準確度。基于內容豐富的本地文本數據庫，將改進Jaro-Winkler算法應用于迎賓機器人語音交互中的字符串匹配，其正確率大于96%。測試結果表明，迎賓機器人能夠語音交互更多的內容和快速地應答提問，并實現特定的迎賓動作。

Jaro-Winkler算法；迎賓機器人；語音交互；字符串匹配

國家自然科學基金（No.61376073）

When measuring the similarity of two strings,Jaro-Winkler distance only considers the number of transpositions,without considering the insertions and deletions.Aiming at this problem,proposes an improved Jaro-Winkler distance method based on the Levenshtein distance. Modifies the formula of similarity and adjusting the correlation coefficient of pd to improve Jaro-Winkler distance,and the accuracy of the strings matching is increased.Based on the local database with a large number of text strings,applies the improved Jaro-Winkler distance to achieve the strings matching in speech interaction of reception robot,and its accuracy is higher than 96%.Test results show that reception robot can realize more words and quickly reply to questions by speech interaction with specific welcome actions.