对索引网页信息的预处理包括网页分析和倒排文件索引两个部分，中文自动分次是网页分析的前提。文档由被称作特征项的索引词组成，网页分析是将一个文档表示 为特征项的过程。在提取特征项时，中文又面临了与英文处理不同的问题。中文信息和英文信息有一个明显的差别：英语单词之间用空格分隔；而在中文文本中，词 与词之间没有天然的分隔符，中文词汇大多是由两个或两个以上的汉字组成的，并且语句是连续书写的。这就要求在对中文文本进行自动分析前，先将整句切割成小 的词汇单元，即中文分词（或中文切词)。
用具体例子来说明，就是如何把“我的笔记本”这样连续书写的语句切分为“我”，“的”和“笔记本”三个词汇单元。 在检索和文档分类系统中，自动切词系统的速度影响整个系统的效率。中文信息的检索主要有两种：基于字的检索和基于词的检索。基于单字的检索系统建立单字索 引。在检索时得到每个单字的索引，而后加以适当的逻辑运算，得到检索结果。而基于词汇的检索系统对词汇建立索引，检索词汇时一次命中。
1、算法介绍
自动分词的基本方法有：基于字符串匹配的分词方法和基于统计的分词方法。
基于字符串匹配的分词方法
这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方长度优先匹配的情况，可以分为最大或最长匹配，和最小或最短匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：
1) 正向最大匹配；
2) 逆向最大匹配；
3) 最少切分（使每一句中切分出来的词数最小）
还可将上述各种方法相互组合，例如，可以将正向最大匹配方法和你想最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245（这可能是因为汉语的中心语靠后的特点）。对于机械分词方法，可以建立一个一般的模型，形式地表示为ASM(d,a,m)，即Automatic Segmentation Model，其中，
d：匹配方向，+表示正向，-表示逆向；
a：每次匹配失败后增加或减少字串长度（
m：最大或最小匹配标志，+为最大匹配，-为最小匹配。
例如，ASM(+, -, +)就是正向减字最大匹配法（Maximum Match based approach, MM），ASM(-, -, +)就是逆向减字最大匹配法(简记为RMM方法)，等等。对于现代汉语来说，只有m=+是实用的方法。
2、基于统计的分词方法
从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。计算汉字X和Y的互现信息公式为：
其中P(X, Y)是汉字X、Y的相邻共现概率，P(X)、P(Y)分别是X、Y在语聊中出现的概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。 词汇切分算法最重要的指标是准确，在兼顾准确性的情况下也要考虑时间复杂性。下面具体介绍正向减字最大匹配法。
2、正向减字最大匹配法
正向减字最大匹配法切分的过程是从自然语言的中文语句中提取出设定的长短字串，与词典比较，如果在辞典中，就算一个有意义的词串，并用分隔符分隔输出，否则缩短字串，在词典中重新查找（辞典是预先定义好的）。
算法要求为：
输入：中文词典，待切分的文本d，d中有若干被标点符号分割的句子s1，设定的最大词长MaxLen。
输出：每个句子sl被切为若干长度不超过MaxLen的字符串，并用分隔符分开，记为s2，所有s2的连接构成d切分之后的文本。
算法思想:事先将网页预处理成每行是一个句子的纯文本格式。从d中逐句提取，对于每个句子s1从左向右以MaxLen为界选出候选字串w，如果w在词典中，处理下一个长为MaxLen的候选字段：否则，将w最邮编一个字去掉，继续与辞典比较：s1切分完之后，构成词的字符串或者此时w已经为单字，用分隔符隔开输出给s2。从s1中减去w，继续处理后续的字串。s1处理结束。
设文本含有句子的书目为m，句子的平均长度为k，辞典的条目为n。实际中m和k远远小于n，整个算法复杂度中起决定作用的步骤在于n相关的语句。因此算法的时间复杂度为O(mklogn)。
No comments:
Post a Comment