【c语言搜题软件】C语言实现搜索引擎技术之中文分词

【www.bbyears.com--C语言】

目前而言的分词系统绝大多数都是基于中文词典的匹配算法，其中，最为常见的是最大匹配算法 (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: %sn", (*itor).c_str());
    }

    return 0;
}

本文来源：http://www.bbyears.com/asp/60559.html