众诚速配
广告
展会信息港展会大全

imdict的分词机制剖析(1)onedear
来源:互联网   发布日期:2011-09-09 17:18   浏览:10598次  值班编辑QQ:点击这里给我发消息

中文分词----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值大小,从小到大排序,对于"图,图火,图水",少子的排前,"图火,图水"进行火与水的排序

计算结果

赞助本站

人工智能实验室

相关热词: imdict 词机 制剖 onedear

AiLab云推荐
推荐内容
展开
Copyright © 2010-2020 AiLab Team. 人工智能实验室 版权所有    关于我们 | 联系我们 | 广告服务 | 公司动态 | 免责声明 | 隐私条款 | 工作机会 | 展会港