lucene分词算法概论以及中文分词的猜想
2008/04/06 14:37 | by edwardproAdmin ]
luncene分词的大概过程是这样的:
1 截断单词
2 过滤干扰信息
3 写入结果
截断，对于英文来书很简单就是用空格和标点符号以及一些特殊用词，这些在系统里已经定义好，当然你也可以适时地改变一下。
过滤，在它的标准算法中会对如下的符号进行过滤：'s 'S . 这样几种。
写入，这个顾名思义啦
下面谈谈我对中文分词的猜想，之前也用过je分词这样所谓成功作品，但无论性能还是效果都无法达到我的要求，而且它又不公开源码，令人非常失望，所以目前我使用的依然是luncene中的标准分词，也就是单字分词，但单字分词的问题也很明显消耗了极大的存储空间，目前在非压缩状态下，索引是原始文档的1.2～1.3倍之多，这是随着数据积累挺令我担心的问题。所以不得不思考中文的算法过程，我设想的算法应该是这样：
1 截断，利用分词库和常用介词表进行，其中分词库采用首字单词长度逆向排序法匹配，过程：
首先将词库按首字放入hash，然后将同首字的按照长度逆序排列
然后分词的时候先按单字分开，然后依据分词表，匹配 n次 （n是首字列表里的元素个数）并且允许重复匹配，比如中国 中国人 需要重复匹配。
之后同样去除标点符号等干扰因素。
那么我们现在来是想一下它的算法复杂度：
应该是： len（str）×n（str【i】）
试验更高级的算法在多词匹配时利用递归，将后一个字的算法也同时写入，或将减少其算法复杂度。
下周刊有时间的时候尝试写一个分词来看看，是否合理。
关于group by
2008/03/22 10:30 | by edwardproAdmin ]
周五因为在搜索引擎中要使用group by操作，原有的 count发似乎会出现很大的效率问题，所以也简单考虑了下groupby的实现，在sql里我猜想（我对这个算法完全没有概念），首先利用矩阵算法将所有的row排序好，然后以此顺序取出，然后再加入聚合函数count或者sum，也就是说在sql中实际上他是先把按groupby字段索引排序然后再进行数据聚合，最后再拉出需要的数据（这个猜想是基于group by字段需要索引得到的，不知道是否正确）
而在lucene中也是类似的状况，现在我们考虑lucene 大家知道在lucene中得到的结果集是hits，hits实际上和sql中的结果集recordset是一个概念的，即使你得到了一个数百万的结果集，数据也并没有立即从中拉出（这应该就是为什么表需要有主键的原因）。但lucene中有个问题，我无法得到一个多结果集，也就是说我无法得到一个按groupby排序的某个中间结果，我得到的只是输出，因此在group中我只能选择先将所有数据全部读出这条路，那么读出来的数据怎样groupby？我实现的是基于hash表的 数组遍历。是这样的过程：
hash<字段名，groupby结果集>
groupby结果集<字段值，聚合值>
用这样的hash嵌套实现，算法中我只使用了一次hash循环，但比较大的伤害是，数据集似乎被从头到尾取了一次，会产生很多io，并且由于我的group和查询是一种并行算法，因此等于结果集被取出了两遍（目标中的group是类似taobao的产品列表的类别归类查询页面，所以group是一个独立结果集并非输出结果集），目前测试下来还没有感觉内存消耗有极其大的影响，但不知道在高负荷状态下的水平，因此还需要继续查看。
关于group的算法，如果有更好的办法和算法或者在lucene下有更好的解决方案欢请路过不要吝啬你的idea告诉我吧。
