-ca9fe781c2d244deaabd5ebe8c1c61a1.JPG)
模块一：关键词推荐
1. 创建词典
根据语料库创建词典，语料库就是一些连续的句子，这里使用一些书籍来作为语料库。构建词典的过程就是统计这些语料库中每个词组的词频。
那么如何将连续的句子切分成词组？并统计每个词的词频？
1.1cppjieba安装与使用
https://github.com/yanyiwu/cppjieba
//下载和编译
git clone --depth=10 --branch=master git://github.com/yanyiwu/cppjieba.git
cd cppjieba
mkdir build
cd build
cmake ..
make
该开源库可用词停库将句子划分为单词，具体用法：
#include "../../include/cppjieba/Jieba.hpp"
using namespace std;
const char* const DICT_PATH = "../../include/cppjieba/dict/jieba.dict.utf8";
const char* const HMM_PATH = "../../include/cppjieba/dict/hmm_model.utf8";
const char* const USER_DICT_PATH = "../../include/cppjieba/dict/user.dict.utf8";
const char* const IDF_PATH = "../../include/cppjieba/dict/idf.utf8";
const char* const STOP_WORD_PATH = "../../include/cppjieba/dict/stop_words.utf8";
void test()
{
cppjieba::Jieba jieba(DICT_PATH,
HMM_PATH,
USER_DICT_PATH,
IDF_PATH,
STOP_WORD_PATH);
vector<string> words;
vector<cppjieba::Word> jiebawords;
string s;
string result;
s = "他来到了网易杭研大厦";
cout << "[demo] Cut With HMM" << endl;
jieba.Cut(s, words, true);
for(auto it:words){
cout << it << " ";
}
}
#输出结果
#[demo] Cut With HMM
#他 来到 了 网易 杭研 大厦将句子切分之后，就可以统计语料库中所有词组的词频，建立词典
void EnDictProducer::buildDict() {
map<string,int> dict_map;
_splict_tool = new EnSplitTool();
//遍历每个文件
for(auto &file : _files){
ifstream ifs(file);
string line;
//每次读取一行
while(getline(ifs,line)){
vector<string> words;
words = _splict_tool->cut(line);
//将每个词放入map中
for(auto &word : words){
if(_stop_word.find(word) != _stop_word.end()){
continue;
}
auto iter = dict_map.find(word);
if(iter == dict_map.end()){
dict_map.insert({word,1});
}else{
++iter->second;
}
}
}
}
//将map中的单词放入vector中
for(auto &p : dict_map){
_dict.push_back({p.first,p.second});
}
}创建后，词典大概是这样：
abda 2
abdeel 1
abdi 3
abdicate 1
abdicated 1
abdiel 1
abdomen 22
abdomens 2
abdominal 47
abdon 8
abduct 3
abducted 4
abducting 2
abduction 10
abductor 4
abductors 1
abe 2
abednego 15
abel 17
abelbethmaachah 2
abelmaim 1
abelmeholah 3
abelmizraim 1
abelshittim 1
......
2. 创建索引文件
索引文件用来索引组成这些词组所在的位置，如果一次词组包含某个字，那么可以通过这个字的索引找到该词组。查询词query 没有必要与所有的候选词来比较，例如，查询词是nike，候选词是appl，这两个词没有任何字符有交集，这种情况没有必要计算编辑距离。如何利用索引来缩小候选词，以达到提高计算性能的目的：当query 是nike 的时候，我们只需要查找候选词包含n 或者i 或者k 或者e 的这些词。
n：ipone，iphone
i：ipone，iphone，nike
k：nike，kindle
e：nike，iphone，ipone，kindle
l：loop，appl
中: 中国 中间 其中
void EnDictProducer::createIndex() {
//遍历Dict
for(int i = 0; i < _dict.size(); ++i){
//每次取出一个词，遍历其字母，并将其放入对应字母的集合里
for(auto c : _dict[i].first){
auto iter = _index.find(string(1,c));
//如果是不存在的字母，插入这个字母
if(iter == _index.end()){
auto pos = _index.insert({string(1,c),set<int>()});
if(pos.second){
pos.first->second.insert(i);
}
//存在的字母，直接插入即可
}else{
iter->second.insert(i);
}
}
}
}索引文件结构 字母 词典中含有该字母的索引：
p 70 150 151 170 210 211 212 213 214 215 216 217 218 219 238 239 240 241 242 243 244 245 246 247 248 249 250 310 313 376 392 393 394 395 396 431 450 451 452 524 525 526 527 765 808 849 850 912 913 996 1039 1040 1044 1045 1046 1047 1048 1049 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1211 1259 1260 1307 1369 1441 1447 1448 1449 1450 1459 1460 1461 1462 1463 146 .....
3. 候选词推荐
3.1 最短距离
根据输入进来的内容，推荐几个候选词，而候选词可能会有很多，那么如何推荐最接近的候选词呢？
可使用动态规划解决这个问题，详情可以看[leetcode72. 编辑距离](https://leetcode.cn/problems/edit-distance/)
//计算最小编辑距离-包括处理中英文
int editDistance(const std::string & lhs, const std::string &rhs){
size_t lhs_len = length(lhs);
size_t rhs_len = length(rhs);
int editDist[lhs_len + 1][rhs_len + 1];
for(size_t idx = 0; idx <= lhs_len; ++idx){
editDist[idx][0] = idx;
}
for(size_t idx = 0; idx <= rhs_len; ++idx){
editDist[0][idx] = idx;
}
std::string sublhs, subrhs;
for(std::size_t dist_i = 1, lhs_idx = 0; dist_i <= lhs_len; ++dist_i, ++lhs_idx){
size_t nBytes = nBytesCode(lhs[lhs_idx]);
sublhs = lhs.substr(lhs_idx, nBytes);
lhs_idx += (nBytes - 1);
for(std::size_t dist_j = 1, rhs_idx = 0; dist_j <= rhs_len; ++dist_j, ++rhs_idx){
nBytes = nBytesCode(rhs[rhs_idx]);
subrhs = rhs.substr(rhs_idx, nBytes);
rhs_idx += (nBytes - 1);
if(sublhs == subrhs){
editDist[dist_i][dist_j] = editDist[dist_i - 1][dist_j - 1];
}
else{
editDist[dist_i][dist_j] =
triple_min( editDist[dist_i][dist_j - 1] + 1,
editDist[dist_i - 1][dist_j] + 1,
editDist[dist_i - 1][dist_j - 1] + 1);
}
}//for
}//for
return editDist[lhs_len][rhs_len];
}3.2 推荐
遍历输入的句子中的字或者字母，然后在索引中获取包含这些字或者字母的单词，将这些单词作为候选词，根据最短距离推荐候选词
vector<string> EnKeyRecommander::doQuery(){
vector<string> res;
//获取英文词典，并初始化获得词典库和索引库
Dictionary *dict = EnDictionary::createInstance();
dict->readDictAndIndex(conf->_configMap["en_dict_path"],conf->_configMap["en_index_path"]);
vector<pair<string,int>> dict_vec = dict->getDict();
map<string,set<int>> dict_map = dict->getIndexTable();
//获取候选词
set<int> candidate_set;
//遍历每个字母，将包含该字母的词加入候选集
for(char &c : _wordBeQuery){
set<int> s = dict_map[string(1,c)];
candidate_set.insert(s.begin(),s.end());
}
//cout << "candidate_set size = " << candidate_set.size() << endl;
//从候选词中取出对应词并加入优先队列
for(auto idx : candidate_set){
if(_prique.size() < 5){
_prique.push(CandidateResult(dict_vec[idx].first, dict_vec[idx].second,
editDistance(_wordBeQuery, dict_vec[idx].first)));
}else{
CandidateResult cr(dict_vec[idx].first, dict_vec[idx].second,
editDistance(_wordBeQuery, dict_vec[idx].first));
if(cr < _prique.top()){
_prique.pop();
_prique.push(CandidateResult(dict_vec[idx].first, dict_vec[idx].second,
editDistance(_wordBeQuery, dict_vec[idx].first)));
}
}
}
//将优先队列中的词放入结果vector中
while(!_prique.empty()){
res.push_back(_prique.top()._wordCandidate);
_prique.pop();
}
//反转vector使相关性高的词排在前面
reverse(res.begin(),res.end());//注意：C++中的优先级队列 默认是大顶堆实现的
return res;
}