基于字典的的正向最大减字匹配算法，在《搜索引擎原理、技术与系统》提到过，可以说是最简单的中文分词算法之一。本文简要介绍实现过程，并附上实现源代码，一起学习。该算法实现主要是基于一个词典，进行分词，所以词典质量直接影响分词的结果。但是算法上也存在一些硬伤，举个例子，”参加过世界杯的选手”。无论用多丰富的词典，此算法均会分成“参加 过世 界 杯 的 选手”。
词典
词典采用GBK编码，格式为“ID SP 词语 SP 频率”（点击这里下载），只需要读取每一行，拿到两个空格（SP）之间的词语，然后放到一个C++ STL的set对象即可。在加载词典的同时，可以算出最大词长nMaxWordLen，这个值会在后面的分词使用到。
分词
从句子的最左边开始，逐字节遍历。每次分词时，首先截取nMaxWordLen个字节，并在词典中搜寻,如果找到了，就分词。如果找不到，就递减字节，如此往复，直到只剩下一个字节为止，这时就判断是ASCII还是汉字，如果是前者，直接分割，后者就将当前字节和下一个字节一起分割。这样直到遍历完所有字节。
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
/*
* dict_seg.cpp
* 基于字典的分词
* Created on: 2012-6-16
* Author: bourneli
*/
#include <string>
#include <iostream>
#include <fstream>
#include <set>
#include <vector>
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<string> oDict 字典
* @param int nMaxLen 字典中的最长词的字节数
*/
void
LoadDictionary(
const
string& sDictPath, set<string>& oDict,
int
& nMaxLen);
/**
* 采用基于词典的最大正向匹配分词
* @param string sSen 需要分词的句子
* @param set<string> 字典
* @param int 字典中的最长词的字节数
* @param vector<string> 分词后的结果
*/
void
SegmentSentence(
const
string& sSen,
const
set<string>& oDict,
int
nMaxLen, vector<string>& vecWords);
int
main(
int
argc ,
char
** argv) {
set<string> 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<string> vecSeg;
SegmentSentence(sSen, oDict, nMax, vecSeg);
// 输出分词结果
cout <<
"Segment: "
;
for
(vector<string>::const_iterator cItr = vecSeg.begin(); cItr != vecSeg.end(); ++cItr) {
cout << *cItr <<
" "
;
}
cout << endl;
return
0;
}
void
SegmentSentence(
const
string& sSen,
const
set<string>& oDict,
int
nMaxWordLen, vector<string>& 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
<unsigned
char
>(*cItr)) {
// 添加当前的单个汉字，gbk由两个byte组成
vecWords.push_back(string(cItr, cItr + 2));
cItr += 2;
}
else
if
(nWordLen == 1 && GBK_HB_MIN >
static_cast
<unsigned
char
>(*cItr)) {
// 添加当前的ascii码
vecWords.push_back(string(1, *cItr));
cItr += 1;
}
else
{
cItr += nWordLen;
}
}
}
void
LoadDictionary(
const
string& sDictPath, set<string>& 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
<unsigned
char
>(*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();
}
|
声明：如有转载本博文章，请注明出处。您的支持是我的动力！文章部分内容来自互联网，本人不负任何法律责任。
本文转自bourneli博客园博客，原文链接：
http://www.cnblogs.com/bourneli/archive/2012/06/29/2570432.html
，如需转载请自行联系原作者
