基于编辑距离的无序词表的对齐和定位

赵志靖

摘要：语言调查采集到的数据存在相当程度的差异，需要进行二次加工。本文基于编辑距离算法实现从语言和方言词汇大数据中的词汇相似匹配及数据的对齐和定位。通过对达让语数据进行的三次实验发现，在做距离计算时，以词算而不是以词加括号内注释的整体去算的方式在保证抽取词汇召回率的基础上准确率会显著提升。实验结果表明，基于编辑距离的数据抽取方法是可行的，具有较好的检索效果。

关键词：编辑距离；相似度

中图分类号：TP391 文献标识码：A

Abstract： The data of languages collected from field research have considerable differences，they need for secondary process.This paper implements the match and extraction of vocabulary similarity from the big data of language and dialect vocabulary based on levenshtein distance algorithm.Through the three experiments made by using the data of Darang， the research finds that the way of counting words rather than words and comments in brackets as a whole increases the precision rate dramatically on the basis of ensuring extraction vocabulary recall rate when the levenshtein distances are computed. The experimental results show that it is feasible to extract data based on levenshtein distance， the aboved method has better retrieval effect.

Keywords： Levenshtein Distance；similarity

引言

中国语言研究中，经历了60余年大规模数据的采集，形成约数千种语言和方言词汇大数据。不过这些数据因调查理念、调查目的、调查方式、调查领域、调查词表等不同而存在不同程度的差异，需要进行二次加工处理，这批宝贵资源对语言工程和语言文化建设具有重要价值。本文目标提出对采集的语言数据二次加工，建设统一格式词表，便于后续的语言科学研究。也就是说语言调查采集到的数据是无序的，且数量不等，本文拟建设统一格式词表，该词表包括1 329个词汇，并且这些词汇是按照顺序排列的，然后又从数千种语言词汇大数据中，每种语言都抽取意义相同1 329个词汇，如果没有找到，则以空表示，这就涉及到数据的定位，由于这1 329个词汇是按照顺序排列的，所以还涉及到数据的对齐，最后将每种语言按顺序排好的1 329个词汇保存为独立的Excel文件，供语言分析研究使用。本文的难点在于如何从数千种语言词汇数据中尽可能准确地找到这1 329个词汇。

1 中国语言和方言数据现状

半个多世纪以来，我国开展过数次规模不等的语言和方言调查。1956年，根据国务院指示开展了汉语和民族语言普查，共普查了1 849个县市的汉语方言，并组成7个民族调查队，调查了主要民族地区的语言。这次语言普查，对于推广普通话和汉语规范化，对于少数民族文字的改革与创制，对于民族身份的认定等都起了重要作用。1999年，教育部、国家语委等11部（委）联合开展了中国语言文字使用情况调查，调查采用入户问卷的调查方式，涉及全国1 063个县（市、区），直接被调查对象47万多人。这次调查获得了我国语言文字使用的一些基本数据，为当今的语言决策提供了重要支撑。除了这2次大的语言调查之外，我国学者还持续进行了汉语方言、民族语言、海外华语的调查研究，取得了许多重要成果。

在推广普通话的同时，社会的语言资源保护意识逐渐加强，方言文化保护受到社会各界的关注。国家语委积极推进中国语言资源有声数据库建设，江苏库数据调查工作完成并通过国家验收，成为全国首个建成并开通的省级语言资源库，上海、北京、辽宁、广西等省区市有声数据库建设工作取得成效，山东、河北、福建等省有声数据库建设工作启动。“中华经典资源库”启动了首期建设工作[1]。

但是语言生活异常丰富复杂且与时而变，半个多世纪以来所进行的各种语言调查，或因调查理念、调查目的、调查方式（包括调查技术）、调查领域等限制，采集到的数据存在相当程度的差异，需要进行大规模统筹建设。用现代信息技术大规模处理中国语言数据，建成中国语言资源数据库，对我国语言生活规划和语言科学研究将产生极其重要的影响。

2 基于编辑距离的数据对齐和定位技术

2.1 编辑距离

编辑距离算法是俄罗斯的Vladimir Levenshtein在1965年最先提出来的[2]。Levenshtein提出的编辑距离算法允许使用插入、删除和替换3种编辑操作方式，用这3种编辑操作方式计算得到的编辑距离叫Levenshtein Distance。[3]

编辑距离用于衡量2个序列的相似度，即两者之间有多近似或有多大区别。在自然语言处理中被衡量的序列就是单词或字符串。2个单词之间的编辑距离越小，其相似度就越高。如果设2个字符串分别为源字符串s和目标字符串t，从字符串s到t的编辑距离是指：只使用删除、插入或替换3种操作，需要最少多少步可以将s变成t，即“将源字符串s变换为目标字符串t所需要的最少的删除、插入或替换操作的次数”[4]。举例如下。

1）如果s=“computer”，t=“computer”，那么编辑距离D（s，t）=0，因为s与t完全相同，不需要变换。

2）如果s=“sport”，t=“sort”，那么编辑距离D（s，t）=1，因为将s变换为t只需一次编辑操作（删除字母“p”）。

3）如果s=“sensible”，t=“sensitive”，其编辑距离D（s，t）=3，因为将s变成t至少需要三步（第一步插入“t”，第二步把“b”替换成“i”，第三步把“l”替换成“v”）。

编辑距离D（s，t）的计算方法如下所述。假设Dij=D（s1…si，t1…tj），0≤i≤m，0≤j≤n，m和n分别表示源字符串s和目标字符串t的长度，Dij表示从s1…si到t1…tj的编辑距离，那么（m+1）×（n+1）阶矩阵Dij可通过公式（1）计算得到。

公式（1）包含删除、插入和替换三种操作。该算法是从两个字符串的左边开始比较，记录已经比较过的编辑距离，然后进一步得到下一个字符位置时的编辑距离。矩阵Dij能够通过从D00逐行逐列计算获取，最终Dmn表示D（s，t）的值，即源字符串s和目标字符串t的编辑距离。

编辑距离算法最初用于拼写检查，计算将错误的拼写形式转换成正确的拼写形式最少需要多少次操作[5]。现在，编辑距离算法不仅用于拼写检查，还在如剽窃检测、重名或近似名查询、重复内容检查、生物学上的DNA分析、计算机辅助翻译需要的相似译文文本查找、数据清洗等领域中得到了很好的应用[6-7]。

2.2 统一格式词表数据对齐和定位的实现过程

统一格式词表是指从数千种语言词汇大数据中，每种语言都抽取意义相同的词汇（本文是1 329个词汇），然后将所有语言的1329词汇按统一顺序和格式排列，供语言分析研究使用。统一格式词表数据和语言词汇数据保存在Excel中。数据的对齐和定位算法流程如图1所示。

首先，从1329词汇表F1中取词W1，然后从语言词汇大数据F2中依次取词W2，计算W1与W2之间的编辑距离。实际操作中，所谓的W1和W2可能还需要做细化处理，因为1329词汇数据和语言词汇数据保存在Excel中，数据是以类似一条记录的形式保存的，不是以单个词的形式保存的。比如，1329词汇表Excel文件中“雹子，冰雹”这条记录，在程序处理过程中，会将“雹子”和“冰雹”分别取出去做编辑距离计算，而不是以“雹子，冰雹”整体去做编辑距离计算。语言词汇数据Excel文件中的记录也是这样处理的。如此经过编辑距离计算之后，研究择取其中的最小值进入下一步的处理中。将1329词汇表中的每个词汇，采用编辑距离算法，和语言词汇表的所有数据进行相似匹配，并计算编辑距离，将距离最小的和等于最小距离的值作为匹配结果保存到matchWords数组中。如果matchWords的长度为1，则说明只有一条匹配结果，然后将该结果输出保存；如果matchWords的长度为大于1，则说明匹配到相似数据较多，需要进一步处理。

由于应用中词汇的长度相差较大时，词汇长度对最终的计算结果影响较大，因此，有必要对编辑距离值进行归一化操作。本文基于取比较词汇的最大长度做归一化。也就是说，matchLen和最小距离值minMatchLen都是归一化后的值。

本文的算法中，将最小距离minMatchLen阈值设置为0.6，因为经过对输出结果的勘察，我们发现，最小距离值超过0.6的匹配结果，其正确率基本为0。也就是说，具体只对小于0.6的结果做进一步处理，超过0.6就认为没找到，自动输出“Not found！”。超过0.6的检索结果举例如表1所示。实验举例用词汇来自达让语，见本文第四部分，下同，不再赘述。

2.3 词汇的自动抽取及后加工

如前所述，matchWords的长度为1，自动抽取并输出匹配结果；如果matchWords的长度大于1，词汇比较距离超过0.6的自动输出“Not found！”，词汇比较距离小于0.6的则需要进行后加工，即人工判断，后期筛选。即虽然抽取词汇的过程是自动的，但是筛选出尽可能正确的词汇仍需要人工判断。在此，以“洞，窟窿”、“岩石”举例做如下说明，具体如表2、表3所示。

表2和表3中加粗斜体的为筛选结果。由表可知，表2可筛选出正确的匹配词；表3筛选不出匹配词，程序自动输出“Not found！”。同时表2说明，最小距离值为0并不一定只有一个候选词，仍需进一步筛选。

本文用输入对话框的动态列表菜单来显示候选词汇，如果候选词汇数目比较大会影响美观，所以本文选用下拉列表框，其高度固定，宽度根据内容自动扩展，点击列表框右边的倒立小三角可显示带滚动条的下拉列表，内容可多可少。如果有多个候选词，就会按匹配到的先后顺序进行排列并显示给用户。程序运行过程中，列表选择输入对话框是自动弹出的，用户只需在正确词上面单击鼠标右键，然后点下“OK”按钮即可；如果候选词列表中没有找到正确的匹配词，则点下“Cancel”按钮，程序自动输出“Not found！”。这就完成了词汇筛选的过程。图2和图3是词汇筛选界面功能实例图。

图2是程序在检索“洞，窟窿”时，由于有多个匹配结果，所以程序运行过程中跳出对话框进行筛选；图3显示，“窟窿（衣服上的窟窿）”应该是正确的匹配结果，而不是其他项。鼠标选择正确项之后按“OK”按钮，由此正确的匹配结果就得到了保存。

3 实验设计与数据分析

3.1 实验语料

本文所用实验语料是田野调查采集的达让语数据，共有数据记录2660条，其片段截取如图4所示。

3.2 实验过程

本文第三部分的程序实现说明都是基于该实验语料。

为了使得距离值能够切实反映词汇之间的差异，程序在处理过程中会忽略语言数据中括号内的内容。也就是说，在做距离计算时，以词算而不是以词加括号内注释的整体去算。这一点通过实验结果可以得到印证。

利用提供的达让语数据，研究展开了三次实验。

第一次实验：做距离计算时，语言数据是以词加括号内注释的整体去算的，且后期未做筛选加工处理。未召回的词数目为174，检索成功的词数目为664。

第二次实验：做距离计算时，语言数据中括号内注释部分被删除了，且后期未做筛选加工处理。未召回的词数目为39，检索成功的词数目为990。

第三次实验：做距离计算时，语言数据中括号内注释部分被删除了，且后期做了筛选加工处理。未召回的词数目为152，检索成功的词数目为1092。

实验结果用准确率P（Precision）、召回率R（Recall）来表示。3次实验结果如表4所示。

3.3 实验数据分析

从实验一结果来看，语言数据如果是以词加括号内注释的整体去算，会增加词汇的长度，从而无形中加大了编辑距离的值，使得召回率和准确率降低，且均将低于其他2个实验，尤其是准确率大大降低；从实验二结果来看，由于将语言数据中括号内注释部分删除了，召回率和准确率都提高了，尤其是准确率有了明显提升；实验三在实验二的基础上做了后期筛选加工处理，由于加入了筛选操作，召回率略微下降，但比实验一的召回率仍然偏高，最重要的却是，实验三的准确率有了改观与增益。这符合数据处理的正常思维。从实验结果的整体上来看，统一格式词表的数据提取用编辑距离算法可以得到研发，但抽取需要将语言数据中括号内注释部分删除，使得要比较的词汇的长度差小一些，且抽取结果也需要后期筛选处理。

4 结束语

编辑距离是计算和量化分析词汇相似度的一种重要依据。根据编辑距离可实现从数千种语言词汇大数据中检索/抽取词汇。但是同时也看到，本文只研究了抽取过程的自动化，由于后加工阶段需要进行筛选加工处理，会增加时间复杂度，在计算时间上，编辑距离算法还需进一步优化，或者将编辑距离算法和其他算法结合起来推进实施优化处理。

参考文献：

[1]李宇明.论中国语言资源有声数据库的建设[J].中国语文，2010，（4）：356-363.

[2]LEVENSHTEIN V I. Binary codes capable of correcting deletions， insertions and reversals[J].Doklady Akademii Nauk SSSR，1965，163（4）：845-848.

[3]MANNING C D，RAGHAVAN P，SCHUTZE H. Introduction to information retrieval[M].Cambridge： Cambridge University Press，2008：58-60.

[4]马立东.编辑距离算法及其在英语易混词自动抽取中的应用[J].智能计算机与应用，2013，3（1）：47-51.

[5]Allison L. Dynamic Programming Algorithm（DPA） for Edit-Distance[EB/OL].[2015-07-10].http：//www.allisons.org/ll/AlgDS/Dynamic/Edit/.

[6]米成刚，杨雅婷，周喜，等.基于字符串相似度的维吾尔语中汉语借词识别[J].中文信息学报，2013，27（5）：173-178，190.

[7]玛依热·依布拉音，米吉提·阿不里米提，艾斯卡尔·艾木都拉.基于最小编辑距离的维语词语检错与纠错研究[J].中文信息学报，2008，22（3）：110-114.