基于字典的的正向最大减字匹配算法，在《搜索引擎原理、技术与系统》提到过，可以说是最简单的中文分词算法之一。本文简要介绍实现过程，并附上实现源代码，一起学习。该算法实现主要是基于一个词典，进行分词，所以词典质量直接影响分词的结果。但是算法上也存在一些硬伤，举个例子，”参加过世界杯的选手”。无论用多丰富的词典，此算法均会分成“参加 过世 界 杯 的 选手”。
词典
词典采用GBK编码，格式为“ID SP 词语 SP 频率”（），只需要读取每一行，拿到两个空格（SP）之间的词语，然后放到一个C++ STL的set对象即可。在加载词典的同时，可以算出最大词长nMaxWordLen，这个值会在后面的分词使用到。
分词
从句子的最左边开始，逐字节遍历。每次分词时，首先截取nMaxWordLen个字节，并在词典中搜寻,如果找到了，就分词。如果找不到，就递减字节，如此往复，直到只剩下一个字节为止，这时就判断是ASCII还是汉字，如果是前者，直接分割，后者就将当前字节和下一个字节一起分割。这样直到遍历完所有字节。
代码
/* * dict_seg.cpp * 基于字典的分词 * Created on: 2012-6-16 * Author: bourneli */#include#include #include #include #include using namespace std;#define NL 0x0A // new line#define CR 0x0D // carrige return#define SP 0x20 // space#define GBK_HB_MIN 0x80 // minimum of gbk high byte#define DICT_PATH "words.gbk.dict" // 字典路径#define TEXT_PATH "sentence.txt" // 句子文本路径/** * 加载词典 * @param string sDictPath 字典路径 * @param set oDict 字典 * @param int nMaxLen 字典中的最长词的字节数 */void LoadDictionary(const string& sDictPath, set & oDict, int& nMaxLen);/** * 采用基于词典的最大正向匹配分词 * @param string sSen 需要分词的句子 * @param set 字典 * @param int 字典中的最长词的字节数 * @param vector 分词后的结果 */void SegmentSentence(const string& sSen, const set & oDict, int nMaxLen, vector & vecWords);int main(int argc ,char** argv) { set oDict; int nMax = 0; LoadDictionary(DICT_PATH, oDict, nMax); // 获取句子 ifstream oReader(TEXT_PATH); if (!oReader.is_open()) { cout << "Fail to open file : " << TEXT_PATH; } string sSen = ""; getline(oReader, sSen); oReader.close(); cout << "Original Sentence: " << sSen << endl; /** * 采用正向最大匹配规则分词 */ vector vecSeg; SegmentSentence(sSen, oDict, nMax, vecSeg); // 输出分词结果 cout << "Segment: "; for (vector ::const_iterator cItr = vecSeg.begin(); cItr != vecSeg.end(); ++cItr) { cout << *cItr << " "; } cout << endl; return 0;}void SegmentSentence(const string& sSen, const set & oDict, int nMaxWordLen, vector & vecWords){ // 遍历每一个字节（不是汉字） for (string::const_iterator cItr = sSen.begin(); cItr < sSen.end();) { int nWordLen = (cItr + nMaxWordLen) <= sSen.end() ? nMaxWordLen : (sSen.end() - cItr); while (nWordLen > 1) { string sWord(cItr, cItr + nWordLen); if (oDict.find(sWord) != oDict.end()) { // 字典中找到此对象 vecWords.push_back(sWord); break; } else { nWordLen -= 1; // 这个地方可以根据GBK编码规则优化 } } // 跟新当前索引 if (nWordLen == 1 && GBK_HB_MIN <= static_cast (*cItr)) { // 添加当前的单个汉字，gbk由两个byte组成 vecWords.push_back(string(cItr, cItr + 2)); cItr += 2; } else if (nWordLen == 1 && GBK_HB_MIN > static_cast (*cItr)) { // 添加当前的ascii码 vecWords.push_back(string(1, *cItr)); cItr += 1; } else { cItr += nWordLen; } }}void LoadDictionary(const string& sDictPath, set & oDict, int& nMaxWordLen) { // 加载字典 ifstream oReader(sDictPath.c_str()); if (!oReader.is_open()) { cout << "Fail to open file : " << DICT_PATH << endl; exit(0); } string sLine; nMaxWordLen = 0; while (getline(oReader, sLine)) { //cout << "Current Line :" << sLine << endl; // debug /** * 字典的每一行格式为： * ID SP 词语 SP 频率 * * 只有两个空格（SP）之间的词语需要添加到本字典中 */ // 达到第一个空格 int nSpOffset = 0; for (string::const_iterator cItr = sLine.begin(); cItr != sLine.end(); ++cItr, ++ nSpOffset) { if (SP == *cItr) { break; } } // 读取词语 string sWord(""); for (string::const_iterator cItr = sLine.begin() + nSpOffset + 1; cItr != sLine.end(); ++cItr) { if (SP == *cItr) { // 遇到第二个空格，断开 break; } sWord.append(1, *cItr); if (GBK_HB_MIN <= static_cast (*cItr)) { // 针对GBK编码特殊处理，避免截断词语 ++ cItr; if (cItr != sLine.end()) { sWord.append(1, *cItr); } else { cout << "line format error: '" << sLine << "'" << endl; exit(0); } } } // 将此与添加到字典中 if ("" != sWord) { if (!oDict.insert(sWord).second) { cout << "Word conflict: " << sWord << endl; exit(0); } } // 比较最长字长 if (nMaxWordLen < sWord.size()) { nMaxWordLen = sWord.size(); } } oReader.close();}