中文分词----imdict的分词机制剖析（1）
中文分词，很多地方需要用到，特别是搜索跟数据提取这一块。
中文分词器网上不少，但好用的其实不多，例如庖丁解牛，中科院，ik 就很不错了
中文分词最好的是中科院分词，不过其源代码是c++写的，不提供源码，而且是要收费的，否则只能试用一个月，所以需要另找出路。
http://ictclas.org/Down_OpenSrc.asp 在这里找到了一个java的开源分词
imdict-chinese-analyzer是 imdict智能词典的智能中文分词模块，作者高小平，算法基于隐马尔科夫模型(Hidden Markov Model, HMM)，是中国科学院计算技术研究所的ictclas中文分词程序的重新实现（基于Java），可以直接为lucene搜索引擎提供中文分词支持
但其最致命的缺点是不允许附加词库，于是尝试修改了，后来修改成功了，再次将相关的分词机制展示给各位了解一下
原有分词机制的分词步骤
由于原有机制，是中文英文数字等是分开分词的，这会导致一些很严重的bug，例如3G，5月，这样无法分词，只要修改一下判断逻辑，修可以修改这个bug。
下面的例子用查找"botwave博汇公司123"查找为例，来看看应该如何判断 "botwave 博汇 公司 123"跟"botave 博汇公司 123"哪个更准确
词库存放机制
上图为存放及查找方式
相关的代码
/** * wordIndexTable保证将Unicode中的所有汉字编码hash到PRIME_INDEX_LENGTH长度的数组中， * 当然会有冲突，但实际上本程序只处理GB2312字符部分，6768个字符加上一些ASCII字符， * 因此对这些字符是有效的，为了保证比较的准确性，保留原来的字符在charIndexTable中以确定查找的准确性 */ //位置 private short[] wordIndexTable; //汉字 词语的第一个字 private char[] charIndexTable; /** * 存储所有词库的真正数据结构，为了避免占用空间太多，用了两个单独的多维数组来存储词组和频率。 * 每个词放在一个char[]中，每个char对应一个汉字或其他字符，每个频率放在一个int中， * 这两个数组的前两个下表是一一对应的。因此可以利用wordItem_charArrayTable[i][j]来查词， * 用wordItem_frequencyTable[i][j]来查询对应的频率 */ // 中文 private char[][][] wordItem_charArrayTable; // 位置 private int[][] wordItem_frequencyTable; charIndexTable = new char[]{'广','博'}; wordIndexTable = new short[] {1,5}; wordItem_charArrayTable = new char[][][]{{{'州'},{'大'} },{{'汇'},{'汇','公','司'} ,{'汇','数','码'},{'士'},{'学'}} }; wordItem_frequencyTable = new int[][]{{100,20,5},{50,100,30,20,65}};既然知道词典的查询机制，那就可以对细节进行优化了
词典保存时的优化
1.新增一个词（例如 "骐星" onedear 原创词，囧一下 ），但原有词库并不存有骐开头的词语，换句话说，也就是charIndexTable这个数组里面不包含"骐"字，那我们就需要在 charIndexTable数组里面新增加一个位置，这个位置需要计算出来，这里附上相关的算法
经验：hash算法，分布越平均，查找速度越快
核心的相关hash代码
/** * 改进的32位FNV hash算法，用作本程序中的第一hash函数.第一和第二hash函数用来联合计算hash表， 使其均匀分布， * 并能避免因hash表过密而导致的长时间计算的问题 * * @param c * 待hash的Unicode字符 * @return c的哈希值 * @see Utility.hash2() */ public long hash1(char c) { final long p = 1099511628211L; long hash = 0xcbf29ce484222325L; hash = (hash ^ (c & 0x00FF)) * p; hash = (hash ^ (c >> 8)) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } /** * djb2哈希算法，用作本程序中的第二hash函数 * * djb2 hash algorithm，this algorithm (k=33) was first reported by dan * bernstein many years ago in comp.lang.c. another version of this * algorithm (now favored by bernstein) uses xor: hash(i) = hash(i - 1) * 33 * ^ str[i]; the magic of number 33 (why it works better than many other * constants, prime or not) has never been adequately explained. * * @param c * @return */ public int hash2(char c) { int hash = 5381; /* hash 33 + c */ hash = ((hash << 5) + hash) + c & 0x00FF; hash = ((hash << 5) + hash) + c >> 8; return hash; }
通过计算获得位置index = xxx
保存好charIndexTableindex = '骐'
需要在wordItem_charArrayTable 保存"图"字，这样才能组成 "骐图"整个词
这时位置可以直接扩展wordItem_charArrayTable数组，增加长度来存放"图"字
然后当前的位置为 index2；
对"骐图"进行分值设定
wordItem_frequencyTableindex2 = (float)分数
将四个数组关联起来
wordIndexTableindex = index2
整个词库就完整了，
但如果是 要增加三个词"骐图 ， 骐卡 ， 骐明，骐图火，骐图水"，那相关的"图、卡、明 ，图火，图水"应该如何保存顺序也必须讲究
先对"图、卡、明 ，图火"进行排序，例如比较char值大小，从小到大排序，对于"图，图火，图水"，少子的排前，"图火，图水"进行火与水的排序
计算结果
