中文分词中的trie检索树实现（转载）

原贴:http://hi.baidu.com/cuifenghui/blog/item/d66ff3360198db350b55a964.html

中文分词中的trie检索树实现

这几天在研究中文分词，目前已经研究试验了基于词典的常用中文分词算法，包括正向最大匹配、逆向最大匹配、整词二分法、基于tire的中文分词、逐词二分法、双字多字hash的方法，稍后的文章会提及中文分词的方法和程序。此篇文章是基于tire的中文分词中检索树的实现，希望对tire感兴趣或者想研究中文分词的朋友有所帮助，仅做交流。

firstChHash.h头文件内容：

/*
描述: 首字hash函数的实现和说明
作者: xiaocui
时间: 2008.2.27
版本: v1.0
*/

/* 首字hash方法: 在整词二分法，基于Trie树的分词方法，逐字二分法，多次
hash方法中，第一部都需要首字hash方法。首字hash方法采用2级hash策略，对
gb2312编码中的常用汉字，利用gb2312编码的区位码概念，hash函数为: 
index = (区号 - 0xA0 - 16) * 94 + (位号 - 0xA0 - 1)，index为该汉字的索引。
由于gb2312中汉字有限，对没有出现在gb2312编码中的汉字，利用其gbk编码中的
高字节、低字节概念进行类似的hash，gbk的hash作为二次hash。下面先给出关于
gb2312和gbk编码的一些背景知识。

背景知识:GB2312标准共收录6763个汉字，其中一级汉字3755个，二级汉字3008个.
GB2312中对所收汉字进行了“分区”处理，每区含有94个汉字/符号。这种表示方式
也称为区位码。具体分区为:
   
01-09区为特殊符号。
16-55区为一级汉字，按拼音排序。
56-87区为二级汉字，按部首/笔画排序。
10-15区及88-94区则未有编码。

举例来说，“啊”字是GB2312之中的第一个汉字，它的区位码就是1601。

为了区分汉字字符和ascii码，汉字的区码和位码都加上了OxA0,所以最高位都为1,
char显示为负值。通过(char + 256) % 256可以得到其对应的正值。

//////////////////////////////////////////////////////////////////////////
gbk编码介绍:
子集   编码范围      编码空间 编码字数
     ===== ============= ======== =========
     GBK/1 0xA1A1-0xA9FE     846         717
     GBK/2 0xB0A1-0xF7FE   6,768       6,763 //这一部分向后兼容gb2312编码
     GBK/3 0x8140-0xA0FE   6,080       6,080
     GBK/4 0xAA40-0xFEA0   8,160       8,160
     GBK/5 0xA840-0xA9A0     192         166
     EUDC/1 0xAAA1-0xAFFE     564     用户定义1
     EUDC/2 0xF8A1-0xFEFE     658     用户定义2
     EUDC/3 0xA140-0xA7A0     672     用户定义3

从上表可以看出，GBK共提供了23,940字的编码空间, 实际定义了 21,886汉字，可用户定义1,894汉字。双字节编码规则如下：

     第一字节 0x81-0xFE
     第二字节 0x40-0x7E, 0x80-0xFE；每行定义190汉字
*/

/* 首字hash函数1,针对gb2312拥有的99.5%的常用汉字的hash
   输入: 汉字(分高低2字节)
   输出: 该汉字的索引号
*/
#include <iostream>
using namespace std;
inline int hashGb2312(const char* ch)
{
//检验是不是gb2312编码
if ( ((ch[0] + 256) % 256 - 0xA0 < 16) || ((ch[0] + 256) % 256 - 0xA0 > 87) )//gb2312汉字编码高位从第16区到第87区
{
   return -1;
}
if ( ((ch[1] + 256) % 256 - 0xA0 < 1) || ((ch[1] + 256) % 256 - 0xA0 > 94) )//gb2312汉字编码低位从1到94
{
   return -1;
}
int sectionIndex = (ch[0] + 256) % 256 - 0xA0 - 16; //区号(基数为0),减16因为gb2312前15区没用，汉字区号从第16区开始
int locationIndex = (ch[1] + 256) % 256 - 0xA0 - 1; //位号(基数为0),减1因为gb2312位号从1开始，希望从0开始，故减1

int index = sectionIndex * 94 + locationIndex; //gb2312每区94个字符，这个保证hash的结果和区位码是一一对应的

return index;
}
/*首字hash函数2,针对gb2312编码中没有出现的汉字的hash函数
输入: 汉字(分高低2字节)
输出: 该汉字的索引号
*/
inline int hashGbk(const char* ch)
{
int highIndex = (ch[0] + 256) % 256 - 0x81;
int lowIndex;
if ( (ch[1]+256)% 256 > 0x7f )
{
   lowIndex = (ch[1] + 256) % 256 - 0x40 - 1; //第二字节不能是0x7f，所以第二字节比0x7f大的再多减1，这样防止hash空白空间的浪费
}
else
{
   lowIndex = (ch[1] + 256) % 256 - 0x40;
}
int index = highIndex * 190 + lowIndex;

return index;
}

trieTree.h头文件内容：

#include <vector>
using namespace std;

/* 检索树节点定义 */
struct node
{
vector<char*> mKeyWordVec; //关键字向量(递增顺序,便于以后二分查找)
vector<node*> mLinkVec; //指向子检索树的指针向量
};

/* 检索树类的定义 */
class trieTree
{
public:
trieTree(node* root = NULL):mRoot(root){}
node* getTrieTreeRoot() const
{
   return mRoot;
}
trieTree& insert(const char* str); //增加新的字符串
trieTree& del(const char* str); //删除指定字符串
bool find(const char* str); //在检索树中查找指定字符串
trieTree findCh(const char* ch); //在检索树中检索单独汉字
private:
node* mRoot;
};

/* 根据区位码比较2个汉字序列的大小
   输入: 2个汉字序列
   输出: 0表示2个汉字序列相等;正数1表示前者大，负数1表示前者小
*/
int wordCmp(const char* chineseWord1, const char* chineseWord2);

/* 汉字的二分查找 */
int bSearch(const vector<char*>& vec, const char* word);

/* 特殊二分查找，如果在有序序列中没有找到指定元素，返回该元素应该被插入的位置 */
int specBSearch(const vector<char*>& vec, char* word);

/* 有序序列的插入，返回插入的位置 */
int insertToVec(vector<char*>& vec, char* word);

实现和测试文件：

// trieTree.cpp : Defines the entry point for the console application.
//
/*
描述: 自己实现的检索树
作者: xiaocui
时间: 2008.2.27
版本: v1.0
*/

#include "stdafx.h"
#include "trieTree.h"
#include "firstChHash.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;

/* 根据区位码比较2个汉字序列的大小
   输入: 2个汉字序列
   输出: 0表示2个汉字序列相等;正数1表示前者大，负数1表示前者小
*/
int wordCmp(const char* chineseWord1, const char* chineseWord2)
{
size_t len1 = strlen(chineseWord1);
size_t len2 = strlen(chineseWord2);
int firstIndex;
int secondIndex;
size_t i;
for (i = 0; i < (len1 < len2 ? len1 : len2); i += 2)
{
   char ch1[3];
   ch1[0] = chineseWord1[i];
   ch1[1] = chineseWord1[i+1];
   ch1[2] = '/0';
   char ch2[3];
   ch2[0] = chineseWord2[i];
   ch2[1] = chineseWord2[i+1];
   ch2[2] = '/0';
   firstIndex = hashGb2312(ch1);
   secondIndex = hashGb2312(ch2);

   if ( (firstIndex >= 0) && (secondIndex >= 0) && (firstIndex < secondIndex) ) //2个首字都是gb2312的常用汉字
   {
    return -1;
   }
   else if ( (firstIndex >= 0) && (secondIndex >= 0) && (firstIndex > secondIndex) )
   {
    return 1;
   }
   else if ( (firstIndex < 0) && (secondIndex >= 0) )//第1个汉字不在gb2312编码中(gbk中),第2个汉字是gb2312常用汉字
   {
    return 1;
   }
   else if ((firstIndex >= 0) && (secondIndex < 0) )//第1个汉字是gb2312常用汉字，第2个汉字不在gb2312编码中(gbk中)
   {
    return -1;
   }
   else if ( (firstIndex < 0) && (secondIndex < 0) )//2个汉字都不是gb2312常用汉字
   {
    firstIndex = hashGbk(ch1);
    secondIndex = hashGbk(ch2);
    if ( firstIndex < secondIndex )
    {
     return -1;
    }
    else if ( firstIndex > secondIndex )
    {
     return 1;
    }
   }
}
if ( i < len1 )
{
   return 1;
}
else if ( i < len2 )
{
   return -1;
}

return 0;
}

/* 汉字的二分查找 */
int bSearch(const vector<char*>& vec, const char* word)
{
int low = 0;
int high = int(vec.size() - 1); //如果空向量，直接返回-1，-1表示找不到该汉字
while ( low <= high )
{
   int mid = (low + high) / 2;
   if ( wordCmp(vec[mid], word) == 0 )
   {
    return mid;
   }
   else if ( wordCmp(vec[mid], word) < 0 )
   {
    low = mid + 1;
   }
   else if ( wordCmp(vec[mid], word) > 0 )
   {
    high = mid - 1;
   }
}

return -1;
}

/* 特殊二分查找，如果在有序序列中没有找到指定元素，返回该元素应该被插入的位置 */
int specBSearch(const vector<char*>& vec, char* word)
{
int low = 0;
int high = int(vec.size() - 1); //如果空向量，insertPoint返回0，表示插入在首位置
int insertPoint = 0; //如果已在序列中，插入点-1，无需插入；初始化为0，防止要插入的汉字比序列里的汉字都小
while ( low <= high )
{
   int mid = (low + high) / 2;
   if ( wordCmp(vec[mid], word) == 0 )
   {
    return -1;
   }
   else if ( wordCmp(vec[mid], word) < 0 )
   {
    low = mid + 1;
    insertPoint = low;
   }
   else
   {
    high = mid - 1;
   }
}

return insertPoint;
}

/* 有序序列的插入，返回插入的位置 */
int insertToVec(vector<char*>& vec, char* word)
{
int insertPoint = specBSearch(vec, word); //得到插入点
if ( insertPoint == -1 )
{
   return -1;
}
vec.insert(vec.begin() + insertPoint, word);

return insertPoint;
}

/* 增添新字符串 */
trieTree& trieTree::insert(const char* str)
{
char* ch = new char[3]; //此处用动态存储，是为了长久保留汉字
ch[0] = str[0];
ch[1] = str[1];
ch[2] = '/0'; //取得汉字字符串的第一个汉字
if ( mRoot == NULL ) //检索树为空
{
   mRoot = new node;
   mRoot->mKeyWordVec.push_back(ch);
   mRoot->mLinkVec.push_back(NULL);
   const char* s = str + 2; //除第一个汉字外的子串
   if ( *s != '/0' ) //子串不为空(表明还有子节点)
   {
    node* n = new node;
    trieTree child(n); //子检索树
    mRoot->mLinkVec[0] = n; //连接到子节点
    child.insert(s); //在子检索树递归插入
   }
   else
   {
    node* n = new node;
    n->mKeyWordVec.push_back("##"); //存储"##"表示一个词的结束
    n->mLinkVec.push_back(NULL);
    mRoot->mLinkVec[0] = n;
   }
}
else if ( mRoot != NULL )
{
   int index = bSearch(mRoot->mKeyWordVec, ch); //在根节点查找第一个汉字
   if ( index != -1 ) //第一个汉字已经存在
   {
    const char* s = str + 2;
    if ( *s != '/0' )
    {
     node* n = mRoot->mLinkVec[index];
     trieTree child(n);
     child.insert(s);
    }
    else
    {
     node* n = new node;
     n->mKeyWordVec.push_back("##"); //存储"##"表示一个词的结束
     n->mLinkVec.push_back(NULL);
     mRoot->mLinkVec[index] = n;
    }
   }
   else
   {
    int insertPoint = insertToVec(mRoot->mKeyWordVec, ch);
    mRoot->mLinkVec.insert(mRoot->mLinkVec.begin() + insertPoint, NULL);
    const char* s = str + 2;
    if ( *s != '/0' )
    {
     node* n = new node;
     trieTree child(n); //子检索树
     mRoot->mLinkVec[insertPoint] = n; //连接到子节点
     child.insert(s);
    }
    else
    {
     node* n = new node;
     n->mKeyWordVec.push_back("##"); //存储"##"表示一个词的结束
     n->mLinkVec.push_back(NULL);
     mRoot->mLinkVec[insertPoint] = n;
    }
   }
}

return *this;
}

/* 删除指定字符串 */
trieTree& trieTree::del(const char* str)
{
if ( mRoot == NULL )
{
   return *this;
}
if ( find(str) == false ) //指定字符串在检索树中不存在
{
   return *this;
}

//下面统计每个汉字的分支
size_t len = strlen(str);
vector<int> countVec(len/2); //记录分支数，0表示只有一条分支，1表示有多条分支
node* p = mRoot;
node* q;
char ch[3];
for (size_t i = 0; i < len; i += 2)
{
   ch[0] = str[i];
   ch[1] = str[i+1];
   ch[2] = '/0';
   int index = bSearch(p->mKeyWordVec, ch);
   q = p->mLinkVec[index];
   if ( q->mKeyWordVec.size() > 1 )
   {
    countVec[i/2] = 1;
   }
   else
   {
    countVec[i/2] = 0;
   }
   p = q;
}
//寻找最后一个1的位置(这个1说明前面的字组成的前缀对其他词还有用，不能删，从最后那个1的位置(那个字)可以删除
int pos = -1;
for (int i = int(countVec.size() -1); i >= 0; --i)
{
   if ( countVec[i] == 1 )
   {
    pos = i;
    break;
   }
}
//删掉单分支(单分支对其他词无影响)
p = mRoot;
const char* s = str;
for (int i = 0; i <= pos; ++i)
{
   ch[0] = *s;
   ch[1] = *(s+1);
   ch[2] = '/0';
   s = s + 2; //向后移动一个汉字
   int index = bSearch(p->mKeyWordVec, ch);
   p = p->mLinkVec[index];
}

if ( *s == '/0' ) //当前有多路分支的字是最后一个字，最后一个字有多路分支，只删除该词的结尾符即可
{
   int index = bSearch(p->mKeyWordVec, "##");
   p->mKeyWordVec.erase(p->mKeyWordVec.begin() + index);
   p->mLinkVec.erase(p->mLinkVec.begin() + index);
   return *this;
}
while ( *s != '/0' )
{
   ch[0] = *s;
   ch[1] = *(s+1);
   ch[2] = '/0';
   int index = bSearch(p->mKeyWordVec, ch);
   node* q = p->mLinkVec[index];
   p->mKeyWordVec.erase(p->mKeyWordVec.begin() + index);
   p->mLinkVec.erase(p->mLinkVec.begin() + index);
   p = q;
   s = s + 2;
}
if ( *s == '/0' )
{
   delete p; //删除结束符节点
   return *this;
}

return *this;
}

/* 在检索树中查找指定字符串 */
bool trieTree::find(const char* str)
{
char ch[3];
ch[0] = str[0];
ch[1] = str[1];
ch[2] = '/0'; //取得汉字字符串的第一个汉字
int index = bSearch(mRoot->mKeyWordVec, ch);
if ( index == -1 )
{
   return false; //第一个汉字没有查找到，直接返回
}
else
{
   const char* s = str + 2; //取得除第一个汉字外的剩余字符串
   if ( *s != '/0' )
   {
    if ( mRoot->mLinkVec[index] == NULL ) //字符串没有结束，检索树中前缀已经结束，该词不存在
    {
     return false;
    }
    trieTree child(mRoot->mLinkVec[index]); //得到子检索树
    return child.find(s); //在子检索树递归查找子字符串
   }
   else
   {
    node* n = mRoot->mLinkVec[index];
    if ( bSearch(n->mKeyWordVec, "##") != -1 )
    {
     return true;
    }
    else
    {
     return false;
    }
   }
}

return true; //all path return
}

/* 在检索树中检索单独汉字，如果存在返回子检索树 */
trieTree trieTree::findCh(const char* ch)
{
int index = bSearch(mRoot->mKeyWordVec, ch);
if ( index == -1 )
{
   trieTree rst; //空检索树,mRoot == NULL
   return rst;
}
trieTree rst(mRoot->mLinkVec[index]);
return rst;
}

int main()
{
//test
trieTree obj;
obj.insert("啊啊");
obj.insert("阿波罗");
obj.insert("篮球");
obj.insert("篮板");
cout << obj.find("啊") << endl;
cout << obj.find("篮球") << endl;
cout << obj.find("篮筐") << endl;
obj.del("篮球");
cout << obj.find("篮球") << endl;

return 0;
}