解密搜索引擎技术之中文分词与实现
中文分词一直都是中文自然语言处理领域的基础研究，也是中文搜索引擎的核心模块之一。目前而言的分词系统绝大多数都是基于中文词典的匹配算法，其中，最为常见的是最大匹配算法
(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;
}