文件名称：编辑距离方法-iso-14229统一诊断服务uds.pdf
文件大小：277KB
文件格式：PDF
更新时间：2024-06-22 08:24:05
中文句子 相似度计算算法
2．3词形与词序结合的方法 这种方法认为句子相似度是由词形相似度和词序相似度两部分 共同决定的，其中词形相似度起主要作用，词序相似度起次要作用。计 算过程如下： 2．3．1词形相似度 设句子x的长度为句子中单词的个数，记为Zen(X)。SameWC(A，B) 表示句子A、B中相同单词的个数．当一个单词在A、B中出现的次数 不同时，以出现次数少的计数。则句子A、B的词形相似度计算如下： WordSim(A，B)=2x器器(3) 2．3．2词序相似度 令OnceWS(A。B)表示A、B中都出现且只出现一次的单词集合。 Pfirst(A。B)表示OnceWS(A，B)的单词在A中的位置序号构成的向量。 Psecond(A，B)表示Pfirst(A，B)中的分量按对应单词在B中的词序排列 生成的向量。RevOrd(A。B)表示Psecond(A,B)各相邻分量的逆序数。则 A、B的词序相似度由下式决定： f t一可RevOrd(A剧,BI)OnceWS(A=『卅‰e矽跗，印|>ll‘J ，曰Jl—J ⋯⋯⋯1‘⋯”’‘ Or渤t(A，曰)21’ 1⋯ ，10，lceWS(A驯：1(4) l 0 厂|OnceWS(A，别I=o 2．3．3句子相似度的计算 句子A和B的相似度计算公式如下：$im(A，曰)_A．xWordSim(A． B)+2t，xOrdSim(A。B) (5) 其中，～和k是常数，并且满足xl+k=l。显然有O≤WordSim(A， 曰)≤1．D≤OrdSim(A。B)≤l，O≤Sim(A，B)≤1。另外，由于词形相似度 起主要作用，词序相似度起次要作用，所以要求～≥k。 该方法的优点是对于句子中的一个分句或短语发牛长距离移动 后。仍然会与原句子非常相似；综合考虑了句子的结构和相同词语的 数量对相似度的影响；算法实现简单，复杂度较低。但是．该方法基于 词与词之间的词形旺配．没有考虑语义信息，也没有区分不同词性的 词语对句子的不同影响．经常会出现语义相似的句子相似度结果却较 低的不合理现象。 2．4依存树方法 语句相似度计算应该既要考虑对比句子的结构信息和词汇语义 信息．又要力图避免句法分析所带来的高难度和高复杂度，基于该思 想，穗志方于1998年首先提出了基于骨架依存树的语句相似度计算 模趔IS]，即只分析出句子的整体句法结构。其中．整体句法结构用句子 的谓语中心词及其直接支配成分来表示，分析结果可看作一棵简化了 的依存树，称为骨架依存树。骨架依存树仅限两层，第一层为根结点， 即句子的谓语中心词，第二层为叶结点，是句中谓语中心词的直接支 配成分；另外。还需要标注出谓语中心词与其直接支配成分之间存在 的依存关系和相对位置。李彬在2003年也提出了一种基于语义依存 的汉语句子相似度计算方法搠，该方法把语义与依存文法分析结合起 来，有效地刻画了句子的表达意思。在计算依存树之间的相似度时．并 没有匹配所有的搭配对．而是计算那些有效搭配对之间的相似程度， 有效降低了计算的时间复杂度。 依存树方法基于对句子的句法结构分析，理论上是一种较好的计 算模型。但是，目前对句子各成分之间的依存关系分析准确率还不高。 其中，第一种方法采取了人机交互方式．要求用户对自动执行的依存 分析结果进行确认或作必要的修改。第二种方法所采用的分析器对依 存弧的标记准确率只有86％。相似度计算基础的不牢固导致该类方法 难以取得较高的准确率，实际应用性不强。 2．5编辑距离方法 编辑距离指从一个以字符为单位的字符串转换为另一个字符串 所需要的最小编辑操作的代价数。标准的编辑操作有“插入”、“删除” 和“替换”三种。编辑距离最初面向的是不考虑语义的字符处理．在字 符串相似度计算、自动文摘、拼写检查、图象识别、音乐识别、语音识 别、数据清理等众多领域都有着广泛地应用。在汉语句子的相似度计 算方面，也取得了一些成果，如车万翔利用改进编辑距离进行中文相 似句子的检索110l，G．Leusch利用编辑距离计算句子相似度并用于机器 翻译的评价1121。 该方法的主要思想是：以普通编辑距离算法为基础．采用词语取 代单个的汉字或字符作为基本的编辑单元参与运算，加入了词语的语 义相似信息确定词语之间的替换代价．并适当降低插入．删除操作的 代价，使之更加符合中文句子相似度计算的要求。改进编辑距离方法 与单纯基于语义辞典的句子相似度计算方法相比。具有便于扩展、准 确率高等优点。但是现有的研究还存在以下问题：首先，句子中不同的 词语对整体的贡献并不一致；其次，汉语句子中经常会出现短语移位 现象，增加交换操作将符合汉语的特点：另外，现有研究一般没有考虑 归一化问题。单纯凭借编辑距离的大小对句子的相似与否做出判断有 时并不准确。 3．结论 句子相似度计算是自然语言处理领域中比较重要的研究课题．有 着非常广泛的应用，直接决定某些领域的发展。本文介绍了中文句子 相似度计算存在的特点和难点。分析了当前常用的中文句子相似度计 算方法的优点以及存在的问题。通过以上分析可以看出，对中文句子 相似度计算的研究目前还处于一个起始阶段．对于中文问句相似度计 算来说，如何利用汉语句子自身的特点。综合考虑问句的结构关系和 词的语义信息来进行句子相似度计算的研究是关键，是进一步深入研 究句子相似度算法的主要方向。 。 【参考文献】 [1】Chatterjee，Niladri．A Statistical Approach for Similarity Measurement between Sentences for EBMT[A】．In Proceedings of Symposium 011 Translation Support systems(STRANS一2001)[C】．2001． [2]姚天顺，朱靖波，张俐，杨莹．自然语言理解——种让机器懂得人类语言的研 究(第二版)[M]．北京：清华大学出版社，2002． [3]吴市德，罗航哉，薛向阳．基于多重倒排文件的快速相似性检索[J】．计算机学 报，2000，23(1 1)：1 156-1 160． [4】余iE涛，高盛祥，纪鹏程．RDAQAS中同句相似度计算方法研究[J】昆明理工大 学学报(理工版)．2004，29(2)：40—71． [5]吕学强，任飞亮，黄志丹。姚天顺．句子相似模型和最相似句子查找算法[J]．东 北大学学报(自然科学版)，2003，24(6)：531—534． [6ILl Sujian,Zhang Jian，Huang Xiong,et a1．Semantic computation in a Chinese quest!on—answering system[J]Joumal of Computer Science and Technology'2002, 17(6)：933—939． [7]崔桓，蔡东风，苗雪雷．基于网络的中文问答系统及信息抽取算法研究cJ]． 中文信息学报，2004。18 f3)：24-31． [8】穗志方，俞士汶．基于骨架依存树的语句相似度计算模型[A】．中文信息处理 国际会议(ICClr"98)[C]，北京，1998． [9]李彬，刘挺，秦兵．李生．基于语义依存的汉语句子相似度计算[J]．计算机应用 研究,2003，12f12)：15—17． [io]车万翔，刘挺，秦兵，李生．基于改进编辑距离的中文相似句子检索[J]．高技术 通讯,2004，(7)：15—19． [11]丁丰。袁保宗．基于编辑距离的结构模式方法[J]．铁道学报'200l,23(1)：112一 ll 4． [12]G．Lemh,N．Ueffing．H．Ney．A novel string—to-suing distance meBJ4ure诵tll a仰lieations to㈣hine tramlation evaluation【A1．Machine Tmnslmion Summit 1X [C]．New Orleans,t“siana,13SA，2003． 作者简介：贾宗福(196卜)，教授，礓士研究生导师。现任唔尔滨学院教学 与计算机学院、软件学院院长，黑龙江省计算机基础教育研究套常务剐理事长、 秘书长。研究方向为计算机应用技术、计算机教育。 资助项目 [责任编辑：张慧】 万方数据