严建军，彭 雯

（江西理工大学（南昌校区），江西 南昌 330013）

1 文本挖掘

随着计算机网络技术的不断进步，人类对未知领域的探索逐步从最开始的想象转变为通过各项技术实际解决问题，其中，文本挖掘就是人们研究未知领域的一个热门方向。所谓文本挖掘，指的就是从文本数据中获取有价值的信息和知识，是数据挖掘的一种方法。文本挖掘最重要、最基本的运用是实现文本的分类与聚类，前者是有监督的挖掘算法，后者是无监督的挖掘算法[1]。

本文所研究词典的文本是由20个字母构成的全新未知语言，为此，从目前取得的30条文本（单个文本长度为5 000～8 000）中截取相同片段（长度为15～21），找到其共同特征，从而达到研究的目的。

由于记录技术的限制，会存在部分语音的序列片段出现替换、插入和删除错误。现只考虑替换错误，且容错率在0～4之间，要求在30条文本中尽可能多地找到相同序列的片段，且容错率不大于4。需要考虑的问题包括：（1）构建文本模型，且单个长度为5 000～8 000。（2）运用相关原理找出相同序列的片段，并限制其长度为15～21。（3）定义变量，实现算法，并进行验证。（4）以不同的算法与原有算法进行对比，对原有算法进行改进，使算法更优。

首先，模型假设。为了简化模型，对以下部分做出假设：未知的20个语言字母，用a～t 的20个小写英文字母替代。取得的30条文本，由20个小写字母通过随机生成的方式构成。长度为15～21的序列片段，在编纂算法时，可规定其长度为17。

其次，符号说明。r,s为两个随机生成的字符串，D(r,s)为替换距离，&为容错值，D=D(r,s)为替换距离，τ为替换距离阈值[2]。

2 模型的建立与问题解决

（1）文本的生成。建立一个随机生成算法系统，编纂算法，生成随机数0～19，并与20个英文字母a～t相对应，可建立一段符合要求的文本。

（2）总体变量的定义。给定两个文本字符串集合，从两个字符串集合中找到一对相似的字符串，称作相似字符串对（r,s）。本文利用一对字符串容错率不大于4，得出相似字符串，即文本中的相似片段。建立替换距离D(r,s),即将字符串r转换成s所需改动的字符个数（只含替换错误）。当两个字符串相似时，给定其容错值为&，&在0～4之间。

（3）字符串的划分。

首先，鸽巢原理。若将一个字符串r划分成X个分块，存在替换距离D(r,s)为&的情况下，则满足字符串r与另一个字符串s相似，字符串s中必然包括与字符串r的分块相匹配的子串。所以，若已知字符串r,s以及容错值&，当字符串r被分为X个分块，且s中包含与X个分块中某个分块相匹配的子串，则r与s可能相似，若进一步验证替换距离D（r,s）为&，则r与s一定相似。反之，一定不相似，从而得到相似的字符片段。

其次，文本及字符串的划分。第一，均匀划分：已知一段文本或者字符串将其划为X个分块的种类有很多，本文只含字符串的替换错误，则对于字符串长度L满足|r|=|s|，且L满足字符串长度为15～21，即采用均匀划分的方法。对于字符串长度为5 000～8 000的文本或者字符串长度为|r|的字符串，可将其划分为X个分块，则每个分块的长度L为[|r|/X]或者[|r|/X]+1。例如：令X=3,|r|=16，可得分块的长度为3或4，若该字符串为abcdefghijklmnop，可分为4个分块，即{abc,def,ghi,jkl,mnop}。第二，N-gram：确定一个字符串r，和一个正整数n，即用长度为n的窗口在字符串r上滑动，从首字母到末尾得到一组长度为n的字符串，该组字符串即为字符串r的一个N-gram的集合，记为G(n,r)。例如：字符串r：abcdfghije, n=2，则字符串r的2-gram的集合为{ab,cd,fg,hi,je}。最后，对字符串的过滤（基于划分原理之上）。第一，倒排索引：根据属性的值来查找记录，在索引列表中每一项都包含一个属性值和地址，用属性值来确定记录的位置，而不是用记录来确定属性值，故称为倒排索引。倒排索引由关键字（索引项）和出现情况两部分（索引项所对应的二元组列表）组成，本文用N-gram代表关键字来记录信息。例如：对字符串r建立倒排索引，先将字符串r作N-gram处理，取出其中的关键字，将含有N-gram的字符串编号放入相应的倒排索引列表中。第二，划分过滤：对于当前正在访问的长度为|s|的字符串s，根据字符串r的索引列表，可判断索引列表中的字符串是否与s相似，若相似，则s中必包含一个字串与r的索引列表中的一个划分块相匹配。

3 验证框架

3.1 倒排索引的构造

本文所采用的倒排索引由索引项和索引项相对应的二元组列表构成，其中，索引项为N-gram，即索引列表中的每一个元素为一个二元组，其中，p表示该N-gram在字符串标识为d的起始位置，字母d标识包含该N-gram的字符串。可以采用数据结构组织倒排索引，每一个N-gram的数据类型为string，并将N-gram进行映射，具体如下：将N-gram作为一个string类型对待，采用map方式存储倒排列表，其中，key为string类型的N-gram, value为根据倒排索引列表所对应的数据结构。

3.2 字符串top-k的相似顺序型搜索的构造

在倒排索引二元组的基础上，首先，应该定位到倒排列表中和s最近的位置的二元组；其次，从该位置上遍历该倒排列表和查询字符串r相似的字符串s，s和q公共的N-gram位置相差很小，如果实现定位到倒排列表中和s位置最近的二元组，从该位置上遍历该倒排列表累计每个字符串和查询字符串公共N-gram的数量，可以以更高的概率先获得和查询字符串最相近的字符串。

4 算法实施与实例验证

（1）倒排索引构造算法。变量定义为InvertedList：倒排索引列表；maxLen为字符串集合中的最大字符串长度。

（2）双向过滤验证算法。首先，将字符串中已经匹配的部分进行对齐，在满足长度过滤约束的条件下，计算R1与S1之间的D1，当D1大于左边部分的τ则终止计算。否则，继续计算Rτ与Sτ之间的Dτ，Dτ大于右面部分的τ则终止计算。其次，求得Rmid和Smid之间的Dmid，若D1+Dτ+Dmid＞τ，则该字符串对被排除，否则，该字符串对被认定为相似字符串对。

5 结语

本文的实例分析主要是从3个方面对算法进行分析，即分析字符串长度与字符串相似个数的关系、替换距离与字符串相似个数的关系、替换距离与响应时间的关系，再进行比较，从而改进算法。算法改进时，在原倒排索引算法的基础上，插入双向过滤算法的先递减后递增算法，提高算法的运行速度。采用top-k顺序型搜索原理，并编纂算法，减少容错率，尽可能多地得到相同序列的片段。