语言信息处理

《语言信息处理》由会员分享，可在线阅读，更多相关《语言信息处理（11页珍藏版）》请在金锄头文库上搜索。

1、1 引言出于个人对语言信息处理相关内容的兴趣，对两段文本之间如何比较 相似性也有很大的好奇，在之前的工作中也用到相关知识，于是在本次的 报告中，根据自己的能力实现了一个可以比较两段文本相似程度的小算法 算法原理简单，只是从“词”的角度进行分析，没有加入语义的分析，但 是如果在特定的领域也会有不错的效果。报告中会主要介绍算法的原理、 自己在原理上进行的处理以及成果的展示。2 算法思想本文所研究的算法是基于文本相似度匹配而实现的。首先将文本处理 成为相对应的向量，根据空间里向量的相近程度来反映出两个文本之间的 相似度。由于文本数据具有无结构的特性，需要对其进行一定的预处理， 这样才能转换成为数值计

2、算。本文所采用的思路是首先对文本进行中文分 词处理，然后对分词之后的结果进行词频统计，统计时可以同时完成对数 据的降维操作。将统计结果排列成为两个向量，最后利用向量计算的相关 公式进行相似度计算。其总体流程如图 1 所示。 结束图 1 算法流程图3 基于文本相似度匹配的文本匹配算法3.1 文本分词一整段的文本由多个词语组成，我们要进行文本之间相似度匹配的检 测。第一步是对文本进行中文分词，分成一些关键的词语组，其中要剔除 掉语意词、 助词等等对文章大意没有影响的词汇。 英文分词是相对容易的 因为每两个单词之间会有空格进行区分，这就使得分词工作变成了检测文 章中的空格，然后加以分割。但中文句子并

3、没有这样的特征，一个词汇是 由多个汉字组成，而且有可能出现一个字与前后两个字都能组成词语的情 况，需要根据语境进行判定区分， 所以中文的分词技术相对来说要难很多。 但目前中文分词技术也日渐成熟，出现了很多强大的中文分词工具，也提 供了很多不能编程语言的接口。单字分词、二分法和词典分词是目前分词 的主要方法。单字分词，顾名思义即在对中文文本进行分词时，以字为单位进行切 分。字索引很灵活，但是实现单字匹配算法却很复杂，也往往需要大量的 CPU 运算进行支撑。二分法，即将每两个字当作一个词语进行切分，然后 建立索引，使用二分法可以明显地减少每个词条后位置信息的长度。在进行了对比分析之后，词典分词的方

4、法最为适合本系统的需要。词 典分词的基本思想是先构造出一个基本词汇的词典，然后将遇到的文本同 词典比对分析进行分词，这是当前相对准确的方法，也被广泛使用。本文 使用的时 Ansj 中文分词，是一个基于 google 语义模型 +条件随机场模型 的中文分词的 java 实现，词速度达到每秒钟 200 万字左右，准确率能达 到 96%以上 ,目前实现了中文分词、 中文姓名识别、用户自定义词典等功能 , 可以应用到自然语言处理等方面 ,适用于对分词效果要求高的各种项目。 在文本中匹配单词时，正向最大匹配算法和逆向最大匹配法是词典分词法 经常用到的算法，从左侧开始依次读入数据，尝试把几个连续出现的字符

5、 与词库中存在的词条进行匹配，如果成功，就可以分出一个词条，这是正 向，而逆向是从文本的末端开始，每次都取最末端连续出现的几个字符进 行匹配，如果匹配失败，那么加入该字段最前面的一个字，继续进行匹配 错误！未找到引用源。 。当文本比较复杂，需要比较精确的分词的时候，就要用多种方式对文 本进行切分，对不同方式的切分结果进行比对，相同的切分结果得到的词 语就是真正需要的词。3.2 词频统计与数据降维上文中我们提到了要用到每个词条的出现的次数，那么就需要进行词 频统计，也就是词条频率，用来评价一个词对于一段文本的重要性。在信息领域，基于匹配的词频统计算法和基于树结构的词频统计算法 是最为经典也是最被

6、认可的词频统计方法，被广泛使用。在单关键词匹配算法中，比较著名的有 BF 算法、 KMP 算法、 BM 算法 等。（1） BF 算法BF 算法也被称为是蛮力算法，它的基本思想是：首先， A1 和 B1 比较，如果相等，再对A2和B2进行比较，一直到Bm为止；如果Al和B1不相等，则B右移一下，继续进行比较。如果存在k, 1WkWn,且Ak+1k+m=Tlm，则匹配成功，否则失败。( 2) KMP 算法KMP 算法是由高德纳( Donald Ervin Knuth )和 Vaughan Pratt 在 1977 年合作发明的。其基本思想为：如果在匹配的进程中，判断Ai和Bj是否相等，如果相等，那

7、么继续对 Ai+1 和 Bj+1 进行判断；如果两者不相 等，讨论一下两种情况，若j=1，向右移动，判断Ai+1和B1相等与否， 若 1j=m ，则右移 j-next(j) 位，检查 Ai 和 Bnext(j) 是否匹配，重复此过 程直到 j=m 或 i=n 结束。(3) BM 算法BM 算法 1977 年由 Bob Boyer 和 J Strother Moore 提出，是一个字符 串匹配算法。其基本思想是：设定一个位置 i，将主串i起由左至右的进行 判断，若发现不相等， 则下次应从主串的 i + distance(si) 位置开始继续进行 接下去的判断，即跳过 distance(si) 个

8、字符而无需进行比较。(4) 本文使用的算法 基于匹配的词频统计方法，是在对待处理文本进行多次了扫描的基础上进行的，需要付出大量的时间和空间代价，尤其在文本数据量较大时， 则更难以实现。针对这个难点，提出了基于树结构的算法来对词条进行统 计。其基本思想是：首先根据已有的关键词集合构建一棵查找树，然后利 用这个查找树对文档进行扫描，从而进行关键词的统计。利用树形结构的 好处是，在统计时，对文本进行一次扫描就可以完成一个词与查找树的比 较，进而可统计出所有的词条信息。利用树形结构大大减少了不必要的匹 配过程，提高了统计效率。本系统在借助 HashMap 的基础上进行词条的频率统计， 这种方式相对 更

9、加简单明了，易于理解和使用。其基本思想是：利用 HashMap ，把关键 字设置成词条，其 value 等于该词条出现的次数。对已经分词完毕的文本 逐个词条地进行分析，先进行判断，如果该词条不存在于 HashMap ，那么 就将该词条加入其中，并将其 value 设置为 1；如果词条已经存在于 HashMap，就将该词条的value加1，进行一个算法复杂度为 0 (n)的操 作之后，就可以将整个文本的词频统计出来。具体算法如算法 1 所示。算法1 词频统计算法 输入：文本分词结果的listHashMap hm二new HashMapO； /初始化一个 HashMap while（list中仍有

10、未处理词条）if （词条有效）thenif （本词条不存在于hm） then 相应 value=1；else if（本词条存在于hm）then 相应 value+1；elsecontinue；rerurn;利用 HashMap 进行词频统计虽然很有效， 但是也有弊端， 那就是它最 终的结果是无序的， 而且当对两个文本进行利用 HashMap 的方法进行词频 统计之后， 很难保证两个文本同一词条在 HashMap 的位置是一样的。 如果 同一词条所对应的词频不能出现在最终两个向量的同一个维度，那么接下 去的计算必然是无效的。 所以在第二个文本进行填充 HashMap 之后就要进 行一定的操作处理

11、，最终使得两个向量相同的词条的词频出现在相同的维 度。因此，设计了算法对此进行实现，其基本思想是：设置两个数组和两 个迭代器，两个数组用来最终存储两个向量的值，分别进行迭代操作判断 出现顺序完成统计。首先，用第一个迭代器对第一个 HashMap 进行遍历，将对应关键字的 键值从数组第一个位置起往后存储。与此同时，遍历每一个关键字之后， 对这个关键字在第二个 HashMap 中是否存在进行判断：如果存在，这说明 两个文本中都存在这个词条；如果不存在，这说明这个词条只在第一个文 本中出现。判断可知该算法的时间复杂度为 O（n） 。接下来要对利用第二个 迭代器遍历第二个 HashMap ，这时候只需

12、要对词条只出现在第二个文本的 情况进行统计。对应的条件就是判断该关键字的键值在第一个 HashMap 中 是否为空，是的话那就说明这个词条的频率需要统计。由此一来，既可以将所有出现在两个文本中的词条进行统计并在最终的向量数组中存储，又可以使得两个向量保证以相同的词条顺序存储，那 么接下来的计算就是准确的。具体算法如算法 2 所示。算法2向量生成算法输入：存储词频统计结果的HashMap , hml和hm2。输出：存储向量的 vectorl , vector。Integer vectorl; Integer vector2;初始化两个数组Iterator iteratorl = hm1.keyS

13、et().iterator();初始化两个 iteratorIterator iterator2 = hm2.keySet().iterator();while(iterator1.hasNext() 不为空) vector1i=hm1.get(iterator.next();if(该关键字不存在于hm2)then buff2i = 0;elsebuff2i = hm2.get(iterator.next();while(iterator1.hasNext() 不为空) if(该关键字不存在于hm1)then buff2i= hm2.get(iterator.next();buff1i=0;e

14、lsebreak;return;如果数据的维度过大,无疑会大大增加程序的运行时间,所以词频统 计中数据降维是一个重要因素,想要提高效率必须要进行合适的降维操作。 当文本中的词条的数量很多,又有很多的标点符号时,都会增加向量的维 度,提高了计算的复杂程度。为了提高计算的效率,需要进行适当的降低 向量维度的操作,去除一些无关紧要的词语、标点等,减少向量的维度。 这样既可以有效的提高效率,又可以提高算法的精度。本系统在处理这个问题时,是在进行 HashMap 填充之前,利用分词结 果剔除一些标点、空格、一般常用语等对于相似度匹配来说的干扰项。这 样可以进行简单地去除那些对文本相似度产生精确度影响的词

15、条,也就是 说，在把词条加入 HashMap 时，会先进行简单地判断该词条是否为对相似 度判断无效的词条，只有有用词条会被添加到 HashMap 中，否则就直接跳 过，继续判断下一词条。3.3 相似度计算VSM 模型( VSM ： Vector Space Model )即向量空间模型，由索顿等人 于 20 世纪 70 年代提出，并成功地应用于著名的 SMART 文本检索系统 错误！ 未找到引用源。向量空间模型的基本思想是：用特征向量来表示原来的 文本，这样抽象的文本相似度计算问题就转化成了可见的为空间向量之间 的运算，由此大大降低了问题的复杂性，而其可行性也大为提升。它首先 按照分词技术得到的分词结果， 把原来的文本映射为一个 n 维的空间向量， 文本的相似度就可以通过计算两段文本对应的向量的余弦值来确定，利用 了空间里向量的相近程度解决了文本之间的的相似性问题，简单易懂。对 于计算机来说，模糊的文本数据在经过向量空间模型的处理之后，转换成 了可被计算机识别处理的数据，在得出两个向量之间的相似性程度之后， 两个文本之间的相似性问题也随之得到解决。每一篇文本，都是由许许多多的词条组成，文本和其中的词条之间存 在一定的关系，我们需要对这个关系进行一个研究。我们可以把一段文本 看成一个向量 D(value ,value , ,value )，其中