蒙古文信息检索系统的设计与实现

温子潇，包飞龙，高光来，王勇和，苏向东

(内蒙古大学 计算机学院，内蒙古 呼和浩特 010021)

0 引言

随着科学技术的不断发展，互联网上的信息也在呈指数增长。目前，很多中英文信息检索系统层出不穷，但针对蒙古文的信息检索系统还不够完善，且相对较少。

蒙古文是蒙古族使用的语言文字，主要分布在中国的内蒙古自治区和蒙古国。中国与蒙古国使用的蒙古文字具有一定的差异。“语同文不同”，即指语言相同，但文字不同。蒙古国使用的蒙古文称为“西里尔蒙古文”(也称为新蒙文[1])，中国使用的蒙古文称为“传统蒙古文”(也称为旧蒙文或老蒙文)。随着信息的日益增长，蒙古文也急需一种信息检索系统，来满足人们的信息检索层次的需求[2]。

一些科研工作者对蒙古文信息检索系统进行了很多相关研究工作。金威[3]通过对传统蒙古文语法及构词进行详细分析后，解决了如何构建蒙古文索引词的问题。同时，搭建了一个较为完善的蒙古文信息检索平台。李业荣[4]根据传统蒙古文语言特点，利用信息检索技术实现了一个相对完善的蒙古文搜索引擎原型系统。刘娜[5]在基于传统蒙古文语义的基础上，利用信息检索模型，构建了蒙古文信息检索系统。以上研究工作均是基于传统蒙古文而言的，而基于西里尔蒙古文的信息检索系统研究成果还相对较少。上述研究人员不仅为蒙古文信息检索的发展起到了积极促进作用，还为本系统的构建提供了重要参考价值。

本文基于传统蒙古文和西里尔蒙古文，构建了一个性能优良的信息检索系统。该系统可以同时对传统蒙古文和西里尔蒙古文进行关键词检索。本文结构如下: 第一部分介绍了系统的整体框架；第二部分介绍了对网络爬虫改进的MD5算法；第三部分介绍了对蒙古文编码转换、词缀切分和编码校正等预处理操作；第四部分介绍了蒙古文索引的构建方法；第五部分介绍了向量空间模型的检索原理、搜索结果排序打分的算法原理；第六部分介绍了系统具体实现以及性能评价。

1 系统框架

系统整体框架如图1所示。系统整体框架主要分为两大模块，即文档获取模块和文档检索模块。文档获取模块，通过网络爬虫获取传统蒙古文和西里尔蒙古文文档库，对每篇文档进行编码转换、词缀切分以及编码校正等预处理操作，最后对处理后的文档建立索引。文档检索模块，首先对输入的关键词进行词缀切分，然后在索引库中进行检索，最后将检索出的文档根据与输入关键词的相关性排序输出。此外，为了方便用户对西里尔蒙古文的阅读，在系统中加入了西里尔蒙古文到传统蒙古文转换以及网站更新统计等功能模块，满足用户多样化的需求。

图1 检索系统框架图

2 网络爬虫

网络爬虫[6-8]是一个自动提取网页的程序。它为搜索引擎从因特网上下载网页，是搜索引擎的重要组成。抓取流程主要分为三个部分: 产生、解析和提取。传统爬虫从一个或若干初始网页的URL开始，即种子URL。获得初始网页上的URL，在抓取网页的过程中，不断从当前页面上抽取新的URL放入待抓取队列。然后，采用广度优先或者深度优先遍历的方法，遍历整个队列，直到满足系统的一定停止条件。例如，抓取的深度达到设定的阈值爬虫则停止[9]。爬虫的工作流程较为复杂。需要根据一定的网页分析算法过滤与主题无关的链接，并对重复的URL进行去重操作。去重操作可以大大提高爬虫的效率，最后保留有用的新产生的链接并将其放入等待抓取的URL队列。

2.1 爬虫优化改进

去重操作对爬虫性能的改善有决定性作用。本文在爬虫中使用MD5[10]去重算法，使爬虫的性能得到了极大的提升。本文中爬虫的去重操作并不是指对单个URL进行重复性判断，而是对整个网页html进行去重。使用单个链接去重的方法不仅要重新解析当前网页中URL，还要对这些URL进行重复性判断，严重影响了爬虫的速度。使用MD5算法对整个网页html文件进行去重操作，观测整个网页的内容是否发生变化。若网页中的内容并没有变化，将该网页直接去掉即可。这样会省去很多不必要的操作，最大限度降低时间和空间的复杂度，提升爬取效率。

MD5即Message Digest Algorithm 5(信息—摘要算法5)，用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一(又译摘要算法、哈希算法)。MD5算法具有以下特点。

(1) 压缩性: 任意长度的数据，算出的MD5值长度都是固定的。

(2) 容易计算: 从原数据计算出MD5值很容易。

(3) 抗修改性: 对原数据进行任何改动，哪怕只修改1个字节，所得到的MD5值都有很大区别。

(4) 抗碰撞性: 已知原数据和其MD5值，想找到一个具有相同MD5值的数据(即伪造数据)是非常困难的。

通过简单的计算，我们可以知道使用该算法理论上可以使空间的利用率提高60倍。同时经过试验，我们对将近30万条的URL进行去重实验，并对不同的去重方法进行了比较，从表1中可以看出，爬虫的效率提高了很多。

表1 去重方式对比

本文使用的测试环境为Inter Core i3-21003.10Ghz的内存大小为10GB。在30万条URL中，进行了30次实验，最终得出了每种去重算法耗时的平均时间。从表1中可以看出，使用MD5去重耗时最短。使用MD5算法进行去重时，去重时间跟URL的多少是没有关系的。而其他两种去重算法随着URL数量的增大，去重时间也会随之成正比例的增长。因此，在URL很大的情况下，MD5算法仍然可以保持高效的去重效率。当数据量相对较小时，MD5算法的性能并不一定优于其他两种去重方法，该算法只在大数据量的情况下有较好的去重效率。

3 文本预处理

在实现蒙古文检索时，考虑到蒙古文的特点及数据来源(均是从各大网站上抓取下来的)，故文本的格式、编码均不统一。所以，需要对提取的文本进行预处理，将原始数据转换成统一格式，以方便后续的检索处理。

文本预处理的一般步骤主要有: 文本的获取、转码、词缀的切分以及去除停用词等操作。此外，由于蒙古文自身结构特点，有的词从字形上看是正确的，可它的内部编码却是错误的。而在多数情况下，计算机是按照字符编码识别词汇，若不纠正这些错误，将加大后续处理的难度，故在预处理阶段还需要对蒙古文进行编码校对。预处理过程不仅可以减小索引的空间，还可以提高搜索的精度。

3.1 编码转换

获取到文章后，需要对蒙古文的文档进行格式统一，以方便计算机辨认出文档的不同部分然后进行检索。这些内容的区分对信息检索来说是十分必要的，也是检索系统实现的一个重要先决条件。大部分蒙古文的网站使用的编码方式均为蒙科立编码。因此，本文将蒙科立编码的蒙古文转换为国际标准编码的蒙古文。

蒙科立编码采用变形显现字符编码，国际标准编码采用名义字符编码。在使用蒙科立编码的蒙古文中，一个相同的字符，出现在不同蒙古文词的不同位置时，它的编码不同。而在国际标准编码中，无论该字符出现在任何位置，均使用统一编码。为了使所有的数据在我们的系统中具有唯一的编码，需要对蒙古文进行编码转换。采用基于规则和词典的方法，来实现蒙科立编码的蒙文转换为国际标准编码的蒙古文，图2为转换后的文档。

图2 处理后的文档

3.2 词缀切分

蒙古文依据其本身的构词特点与书写规则，是由空格进行分词的。蒙古文词汇通常包括两部分，词干和词缀。与英文的区别在于，蒙古文词汇中没有前缀和中缀，只有后缀。蒙古文中一个词干后面可以连接多种后缀，形成大量代表不同意义的词。如果不对其进行词干的切分，将会导致索引库规模过于庞大，严重影响检索的速度。因此，对蒙古文进行词干提取是很有必要的。蒙古文在去除词缀后，不仅可以有效地提高搜索的效率，还能减少索引的存储空间。

传统蒙古文和西里尔蒙古文切词: 首先要将蒙古文按照空格分词。以词级为单位，从后缀表和词干库中匹配到当前单词的后缀和词干。再采用基于规则的方法进行词缀切分，提取词干。表2为西里尔蒙古文切分词缀后得到的词干表。

表2 切分后得到的词干表

4 索引构建

将非结构化数据中的一部分信息提取出来，重新组织，使其具有一定结构。然后，对这些有一定结构的数据进行搜索，从而达到搜索相对较快的目的。这部分从非结构化数据中提取出来的数据，重新组织后的信息，称之为索引。将输入的数据以倒排索引的数据结构进行存储，索引的建立可以极大地提升搜索速度。倒排索引主要用来存储全文搜索条件下，某一个单词在一篇文档或文档集中存储位置的映射关系及其他信息。本文倒排索引如表3所示。

表3 倒排索引

5 检索模型与重排序

信息的检索与排序是信息检索系统的核心部件。检索部分是从用户那里得到需求信息，利用向量空间模型的检索原理在索引文件中进行查询，检索的效率依赖于构建索引的结构。排序部分是将检索出的结果生成一个按分值排序的文档列表。目的是尽量给用户返回和用户提问最相关的文档集合。

5.1 向量空间模型

将建立完成后的索引，利用向量空间模型[11]，将查询关键词和文档都表示成为向量。文档和查询关键词之间的相似度通过向量夹角的余弦值表示。在检索时,查询关键词为Q，文档集合D=(D1,D2,...,Dn)，则检索的过程可以描述为计算Q与Dj的相关程度。

在向量空间检索模型中,把文档和用户查询均用一组相互独立的词条组成,设在文本集中,共使用了n个词条t1,t2,...,tn。文本集中某一文档dj可表示为:dj=(wj1,wj2,...,wjn),其中wi1,wi2,...,win分别为词t1,t2,...,tn在文档dj中的权值。权值越大,表示该词在文档中的份量越大,即该词越能反映dj的内容: 如果权值越小，说明该词的份量越小,越不能反映dj的内容。权值的取值范围是[0,1]。同样地,用户的查询可表示为q=(w1,w2,...,wn),其中w1,w2,...,wn分别为给出的t1,t2,...,tn的权值。把几个词看作为n维坐标系中的坐标,权植对应其坐标值。这样,文档和用户查询均可看成是由这坐标轴组成空间中的一个点,或称为一个矢量。计算相似度有多种方法,一般常用式(1)计算。

(1)

Wi代表权重，即这个词在文本检索中的重要程度。一般地，通过式(2)计算权值。

Wij=TFi,j×IDFi

(2)

TF是指Term Frequency表示词i在文档Dj中出现的次数，即词频；IDF是指Inverse Document Frequency。IDF定义如式(3)所示。

(3)

公式中，N表示文档集合中所有的文档的数目，ni表示整个文档集合中出现过词i的文档的总数，称为逆文档频率。

模型的优点: 利用向量空间模型进行检索，可以通过调节权值的大小来反映关键词与文档的相关程度。检索时要计算文档间的相似度，使得属相相似的文档会聚集在一起，提高检索的效率。

5.2 搜索排序算法

我们需要将搜索出的文章根据其与查询的相关性进行打分排序。目的是将与用户提问最相关的检索结果排在最前面返回给用户，更好地满足用户的需求。本系统使用的是一种改进的TF-IDF的排序算法，排序如式(4)所示。

Score(q,d)=cord(q,d)×queryNorm(q)×

∑(tf(tind)×idf(t)2t.getBoost()×norm(t,d)

(4)

(1)cord(q,d)为协调因子。表示文档(d)中Term(t)出现的百分比，也就是计算查询条件(q)中不同Term(t)，以及在文档中出现的数量之和，两者的数量之比。通常在文档中出现查询Term种类越多，分值越高。

(2)queryNorm(q)，为调节因子。不影响索引排序情况，只在检索时使用。主要是用来让排序结果在不同的查询条件之间可以比较。这个条件是在搜索时计算。数值是根据每一个查询项权重的平方和计算得到。计算如式(5)所示。

queryNorm(q)=

(5)

(3)tf(tind)，为文档频率，表示查询词中，每个Term在对应的结果文档(d)中出现的次数。查询词出现的次数越多，表示出现频率越高，文档的检索得分就越高。为了避免获得更大的相关性函数，实际中，使用次数的平方根作为文档频率tf的值，避免数值过度放大。

(4)idf(t)2，为逆文档频率。用于检索匹配文档数量的反向函数。按照信息理论，文档出现的次数越少，每一篇文档的信息量就会越大。所以匹配的文档数越少，得分就越高。而索引库中文档总数越多，找到一篇目标文档难度越大，相应的信息量也会越大。

(5)norm(t,d)，为长度因子。由每个索引词汇在域中的总体长度决定的，这个参数在索引建立时确定。数值根据文档中实际具有的索引项个数确定。检索词长度在文档总长度中占的比例越大，长度因子的数值也越大。

根据文档与查询的相关程度的大小，综合考虑关键词在文档中出现的词频等各项指标。对检索出的每一篇文档进行打分，分值越高说明该篇文档与查询词的相关程度越高。返回结果时，随着分数的高低依次排列输出给用户。

6 系统实现

在系统实现阶段，本系统可以同时对传统蒙古文和西里尔蒙古文进行检索。并在系统中加入了西里尔蒙古文转换传统蒙古文和网站更新统计模块，方便用户使用，最后对系统的性能进行了评测。

6.1 检索模块

在预处理后的文档上，采用Lucene[12-14]工具对蒙古文文档构建索引并实现检索，索引的内容包括新闻的标题，正文。检索的实现分为三个步骤: 第一，用户输入要检索的关键词；第二，使用向量空间检索模型，在建立的倒排文档中进行关键词检索；第三，将结果打分排序后反馈给用户。系统在文档库中的检索结果分别如下图所示。图3为使用西里尔蒙古文检索得到的结果，图4为使用传统蒙古文检索得到的结果，系统采用竖排的方式显示传统蒙古文，检索的关键字会在文中标红。

图3 西里尔蒙古文检索结果

图4 传统蒙古文检索结果

6.1.1 检索测试

本文将三个关键词，放在不同索引规模中进行检索测试。从表4中可以看出，对于同一个关键词，索引的规模对于系统检索速度影响不大，并不是索引规模越大检索时间越长，检索的时间主要是受命中数影响。从检索时间上可以看出系统在实际应用中，基本可以满足用户快速检索的需求。

表4 检索测试

续表

6.2 西里尔蒙古文到传统蒙古文转换模块

为了方便我国用户的使用、加快对西里尔蒙古文的阅读速度，对于系统中检索出的西里尔蒙古文，利用SOPA调用了西里尔蒙古文到传统蒙古文转换的Web Service接口，在系统中加入西里尔蒙古文转换为传统蒙古文的功能模块。对于西里尔蒙古文转换为传统蒙古文，采用基于词典和规则的方法与基于统计模型的方法[15-16]相结合的方法，使得转换更高效。图5为转换后的结果。

图5 西里尔蒙文转换为传统蒙文

6.3 网站更新统计模块

系统中加入了对蒙古文网站的更新统计和管理模块。用户不仅可以自己增减想要查看的蒙古文的网站，还可以查看蒙古文网站每天、每月、每年的更新量。系统会将统计的数据以图表的形式显示，给用户一个相对直观的感觉。该模块充分考虑到用户对网站侧重度的不同，可以自主增、删、改所要关注的网站，同时，系统还提供了不同网站的更新统计图，满足用户对系统的个性化需求，如图6所示。

图6 网站更新统计

6.4 系统性能评价

本文利用爬虫从网上抓取了30多万个新闻网页作为测试文档集，设计了10个查询作为查询集，通过人工比较的方法本文获得这些查询的相关文档数。参评指标主要采用MAP和P@N两个指标，其含义如下:

(1) MAP(Mean Average Precision)

单个主题的平均准确率是每篇相关文档检索出结果后的准确率的平均值,是反映系统在全部相关文档上性能的单值指标。系统检索出来的相关文档越靠前则分数就越高，反之则分数越低。

(2) P@N(Precision @ N)

是系统对于该主题返回的前N个结果的准确率。考虑到用户在查看搜索引擎结果时，往往希望在第一页或者第二页就找到自己所需的信息。因此，取N为10、15、20来对系统进行性能评价，常常能比较有效地反映系统在真实应用环境下所表现的性能。

从表5中可以看出，MAP与检索出的文档位置有关，误检的文档越靠前MAP值越小，随着N值的增大误检的错误率也增大，但是系统平均的MAP值基本保持在80%左右。

表5 不同N值下检索结果的MAP和P@N

7 结论与展望

本文基于蒙古文的语言特点构建了一个可以同时检索传统蒙古文和西里尔蒙古文的信息检索系统。在文档获取阶段，对网络爬虫进行了改进，使用MD5算法对网页文件进行去重，提升了爬虫的爬取速度。在文本预处理阶段，对蒙古文进行编码转换、词缀切分以及编码校正等操作，将原始的数据转换成统一的格式，方便后续建立索引和检索处理。在检索阶段，使用向量空间检索模型对倒排索引文档进行检索。系统可以对传统蒙古文和西里尔蒙古文两种不同形式的蒙古文进行检索，并对检索到的文档集合进行打分排序，返回给用户最相关的查询结果。在系统的实现阶段，考虑到我国大部分人使用的是传统蒙古文。系统中加入了西里尔蒙古文到传统蒙古文转换的模块，以方便用户阅读。同时，在系统中加入了网站更新统计的模块，用户不仅可以获得每个网站每天、每月以及每年的更新统计量，还可以根据需要增、删、改想要关注的网站，满足用户个性化的需求。最后对系统的性能进行了评测，从结果来看，系统已经达到了可应用的水平。