Chinaunix首页 | 论坛 | 博客
  • 博客访问: 537517
  • 博文数量: 80
  • 博客积分: 1496
  • 博客等级: 上尉
  • 技术积分: 1292
  • 用 户 组: 普通用户
  • 注册时间: 2008-09-18 11:24
个人简介

IT码农一个~

文章分类

全部博文(80)

文章存档

2020年(3)

2019年(7)

2017年(1)

2016年(2)

2015年(2)

2014年(26)

2013年(26)

2012年(2)

2011年(1)

2010年(1)

2008年(9)

我的朋友

分类: 架构设计与优化

2014-09-19 14:44:54

        中文分词一直都是中文自然语言处理领域的基础研究,也是中文搜索引擎的核心模块之一。目前而言的分词系统绝大多数都是基于中文词典的匹配算法,其中,最为常见的是最大匹配算法 (Maximum Matching,以下简称MM算法) ,而MM算法有三种:一种正向最大匹配、一种逆向最大匹配和双向匹配。本文以正向最大匹配算法为例介绍其基本思想和实现。
一、基本思想
        (1)假设词典中最长的词语字数为w(一般设置为8个字符,即4个汉字)。
        (2)判断带分词语句长度是否大于w个字,如果大于w则跳到(3),如果小于w则跳到(6)。
        (3)取待分词语句的前w个字。
        (4)在词典中查找w,如果存在,则从语句中去掉w,从语句中w后的词开始重复上面过程。
        (5)如果不存在,就去掉这w个字的最后一个字。
        (6)检查是否是单字或者空,如果是,则退出。
        (7)如果不是,则继续判断词库中是否存在这个词,如此反复循环,直到输出一个词。
        (8)继续取短语的前w个字反复循环,这样就可以将一个语句分成词语的组合了。

二、简单实现
        #include
        #include
        #include
        using namespace std;
        set g_setWordDictionary;

        int construct()
        {
            g_setWordDictionary.insert("中国");
            g_setWordDictionary.insert("中国人");
            g_setWordDictionary.insert("纽约");
            g_setWordDictionary.insert("北京");
        }

        bool match(string &word)
        {
            set::iterator itor = g_setWordDictionary.find(word);
            if (itor == g_setWordDictionary.end())
            {
                return false;
            }

            return true;
        }

        void forward_maximum_matching(string content, set &keywords)    
        {
            #define MAX_LEN 12      //词库中最长词语(utf-8一个汉字3个字节)
            #define MIN_LEN 3       //单字(原理同上)
            int len = content.length();
            int right_len = len;
            int start_pos = 0;
            bool ret = false;
            string kw_value = "";
            int kw_len = 0;
            int kw_pos = 0;
            //单字或空串
            while (right_len > MIN_LEN)
            {
                //语句大于词库中最长词语
                if (right_len >= MAX_LEN)
                {
                    kw_value = content.substr(start_pos, MAX_LEN);
                }
                //语句小于词库中最长词语
                else
                {
                    kw_value = content.substr(start_pos, right_len);
                }

                //词库匹配
                ret = match(kw_value);
                kw_len = kw_value.length();
                kw_pos = 0;
                while (!ret && kw_len > 2*MIN_LEN)
                {
                    //去掉候选词右边一个汉字
                    kw_len -= MIN_LEN;
                    kw_value = kw_value.substr(kw_pos, kw_len);
                    //继续匹配
                    ret = match(kw_value);
                }

                //匹配到词
                if (ret)
                {
                    keywords.insert(kw_value);
                    //从语句中去掉匹配到的词
                    start_pos += kw_len;
                    right_len = len - start_pos;
                }
                //未匹配到词,下移一个字
                else
                {
                    start_pos += MIN_LEN;
                    right_len = len - start_pos;
                }
            }//while (right_len > MIN_LEN)      
        }

        int main()
        {
            //构造词库
            construct();

            //切分词库
            string content = "我是中国人,我是来自中国北京的中国人,在纽约工作";
            set keywords;
            forward_maximum_matching(content, keywords);
            set::iterator itor;

            //输出分词
            for (itor=keywords.begin(); itor!=keywords.end(); ++itor)
            {
                printf("result: %s\n", (*itor).c_str());
            }

            return 0;
        }
          

阅读(1076) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~