改進(jìn)Jaro-Winkler算法在迎賓機(jī)器人語音交互中的應(yīng)用

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

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

改進(jìn)Jaro-Winkler算法在迎賓機(jī)器人語音交互中的應(yīng)用

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

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

0　引言

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

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

1　基本的Jaro-Winkler算法

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

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

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

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

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

2　改進(jìn)Jaro-Winkler算法

2.1改進(jìn)的相似度計算公式

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

其中l(wèi)d為編輯距離，pd定義為關(guān)聯(lián)系數(shù)，范圍為（0～1），m為匹配的字符數(shù)，t為換位的數(shù)目。

2.2關(guān)聯(lián)系數(shù)pd值

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

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

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

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

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

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

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

2.4改進(jìn)算法數(shù)值分析

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

圖2　改進(jìn)Jaro-Winkler算法和Jaro-Winkler算法計算的相似度值對比

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

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

圖3　改進(jìn)Jaro-Winkler算法與Jaro-Winkler算法運(yùn)行時間對比

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

3　改進(jìn)Jaro-Winkler算法的應(yīng)用

3.1總體設(shè)計方案

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

系統(tǒng)由通信模塊、MCU（Micro Control Unit）控制單元、電源模塊和電機(jī)模塊四個部分構(gòu)成。其中控制板的控制芯片采用意法半導(dǎo)體推出的8位單片機(jī)STM8S003F，同時提供多個外設(shè)接口，具有模塊化、可靠性強(qiáng)、易拓展等優(yōu)點(diǎn)。

圖4　系統(tǒng)總體設(shè)計方案

圖5　軟件設(shè)計流程圖

3.2軟件設(shè)計

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

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

圖6　語音交互流程圖

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

3.3測試結(jié)果與分析

測試迎賓機(jī)器人的語音交互系統(tǒng)，結(jié)果如圖7所示，根據(jù)Android手機(jī)顯示的語音識別文本、回復(fù)文本和語音合成結(jié)果統(tǒng)計正確率。在數(shù)據(jù)庫strings中隨機(jī)選取100個輸入文本字符串與迎賓機(jī)器人進(jìn)行語音交互，此時語音識別正確率為98%，字符串匹配正確率為100%，語音合成正確率為98%；用100個與隨機(jī)選取的字符串語義相似而詞語構(gòu)成不同的字符串進(jìn)行語音交互時，語音識別正確率為97%，字符串匹配正確率為96%，語音合成正確率97%。因此，應(yīng)用改進(jìn)的Jaro-Winkler算法能夠?qū)崿F(xiàn)高正確率的迎賓機(jī)器人語音交互。

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

4　結(jié)語

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

圖7　語音交互系統(tǒng)測試結(jié)果

［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］靳祖光,陳超,唐堅.一種室內(nèi)導(dǎo)盲機(jī)器人的RFID-語音交互系統(tǒng)設(shè)計［J］.自動化儀表,2013,35（3）:73～76

［4］閔華松,劉冬,王田苗.智能機(jī)器狗的語音控制模型研究［J］.計算機(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技術(shù)應(yīng)用研究［J］.電子技術(shù)應(yīng)用,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ìn)編輯距離的字符串相似度求解算法［J］.計算機(jī)工程,2014,40（1）:222～227

［11］江燕良.基于Android智能終端的遠(yuǎn)程控制系統(tǒng)［J］.電子技術(shù)應(yīng)用,2012,38（8）:129～132

［12］付蔚,唐鵬光,李倩.智能家居語音控制系統(tǒng)的設(shè)計［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-），女，福建人，碩士研究生，研究方向為物聯(lián)網(wǎng)技術(shù)以及軟件工程

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

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

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

王太宏（1966-），男，湖北人，教授，博導(dǎo)，博士，研究方向為鋰電、傳感和物聯(lián)網(wǎng)

2015－01－27

2015－03－04

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

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

國家自然科學(xué)基金（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.