<<  球霸无耻,武汉无理,足协无能,总局无赖! | 首页 | 鱼刺卡喉记  >>

  • 中文信息处理之一 - 机械分词

    日期：2008-10-23 | 分类：Playing With Technology

    版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
    http://keilt.blogbus.com/logs/30555478.html

    最近忙,很忙,所有事情都凑到一起了,于是每天早上9点起床,晚上昏天黑地的做到一两点才睡觉.脑袋里面有很多好的idea也没时间去实现.

    突然对中文信息处理感兴趣了,因为英文默认每个词都是用空格分开的,这给英文信息处理带来了很大的方便,中文则不是这样,要处理中文信息,首先要把一个字符串按照有意义的词分开.这就涉及到一个分词算法的问题了.最简单的分词方法就是基于词典的正向最大匹配机械分词.

    如果现在有一个理想中文字典,最大字长是4(4个中文字符,下同),一条中文信息:温.家宝会见新加坡总理.

    首先建立一个循环,设置两个整形变量标志位,begin和end,初始状态下,begin=0,位于字符串头,也就是温字前,end=str.GetLenth(),位于字符串尾(字符串长度小于4的时候)或者end=8,第四字处(字符串长度大于等于4).

    设置一个临时字符串temp,拷贝输入字符串从begin到end的一段,也就是"温.家宝会",在字典中搜索temp

    显然,这四个字是不会在字典中搜索到的,于是判断搜索函数返回值后,end-=2,向前移动一个字,begin不变.返回循环开始处.

    这次执行循环的时候,由于end前移一个字,所以temp="温.家宝",这个词在字典中就可以搜索到了,于是判断搜索函数返回值后,把词分离出来,之后移动标志位,begin=end,begin向后移动到end的位置,end+=8,end向后移动4个字(begin之后的字长大于4时候),或者是end=str.GetLenth(),end位于字符串尾(begin之后字长小于4的时候),重复循环

    最后,当begin位置在最后一个字或者最后一个字之后的时候,也就是str.GetLenth()-begin<=2的时候,整个分词结束,也就是整个循环的出口.对于上述例子,因为"总理"是个词,所以完成分离"总理"之后,begin位于字符串末尾.

    C实现:

    int begin=0,end;//标志位初值
    if (input.GetLength()>20) end=20;
    else end=input.GetLength();
    while(1){
        temp=input;//copy一段输入文本
        temp.Delete(end,temp.GetLength()-end);
        temp.Delete(0,begin);
        if (input.GetLength()-begin<=2){//循环出口,当begin移动到最后一个字或之后时
            Display()//显示函数,按需自定义
            break;
        }
        if (DictSearch(temp)){//词典中找到匹配时
            DisplayFunc();//显示函数,按需自定义
            begin=end;//移动标志位
            if (begin+20<input.GetLength()) end=begin+20;
            else end=input.GetLength();
            continue;
        }
        else{//词典中未找到匹配
            end-=2;//移动标志位
            continue;           
        }
    }

     

    可能出现的问题:
    1.歧义
    歧义可能由两方面产生,1.算法本身,由于扫描方式是从左到右,所以有可能出现一个词的左半边被划分到前一个词的情况,例如"做爱做的事",其中一步会查找"做爱做",结果找不到,于是丢掉后一个"做",剩"做爱",这个词找到了,于是整句话被划分为"做爱 做 的 事"(晕). 2.词典,词典是不可能做到理想的,所以肯定有遗漏,造成错误的结果,特别是对于刚流行起来的新词,例如"正龙画虎",词典就无法做到正确识别.解决方法:1.检查歧义,可以通过对比正逆向最大匹配的划分结果,如果有不同,不同处就可能产生了歧义 2.消除歧义,可以根据检查语法规则或者不同词组合在中文中出现的频率来消除歧义.这就涉及到中文语言学问题了,明显不是我力所能及的.

    2.单字节的问题
    因为中文字符比较特殊,占用两个char的位置,所以整个处理过程都是以2为单位移动标志位的,对于输入文本中出现的任意单字节字符(半角标点,英文字母),都会造成最终处理结果混乱.解决办法就是,输入文本后,利用一个filter把所有半角字符替换成全角,然后处理,或者是在处理中设置判断条件,对于单字节字符,设置单独规则.

    3.混杂英文
    首先,把所有英文都按单独词处理肯定是不好的,因为对某些中英混合词汇必然产生歧义,例如"c语言",解决方法就是在字典中补充加入中英混合词汇,然后对于字典中找不到的英文,都划分成单独词处理.因为主要处理中文信息,碰到英文的概率不大,所以这样处理出现歧义的概率是很小的.

    4.字典检索效率
    这类机械分词方法要做到准确率高,需要一个信息量很大的词典,也就是说搜索函数需要在巨大的文本中检索相应的词.而整个算法的速度,很大程度上取决于这个搜索函数的搜索效率,逐一查找的方法肯定是不可行的,可以用构建红黑树或者建立hash值索引等方法加快检索,这里不再详述.

     

    P.S. 我开发了一个用于简体中文分词的Java组件，点击这里进入。


    随机文章：


    收藏到：Del.icio.us




    Tags：信息处理 分词 算法 C
    Mr. Kei 发表于22:56:58 | 编辑 | 继续话题 | 转发 | 分享　0
    引用地址：