改进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.