Lucene中文分词“庖丁解牛”

 Lucene中文分词 “庖丁解牛”

 附件 为本人设计编写的组件，中文分词“庖丁解牛”，具有相当好的使用价值。。。

高效率：我的赛扬PC 1 秒解析 >>> 20000汉字的词语  (实际测试结果数据，可达1秒10万+汉字。)
高可维护性：使用“庖丁”隐喻，形象明晰
高灵活性，可扩展：OOD

对比：《终于突破中文分词的效率问题》http://www.lucene.org.cn/read.php?tid=54&fpage=2 他的效率为 6秒 解析2588汉字
 

2007-08-08：

由于庖丁解牛进行了一些调整和重构，这里的附件代码已经是"较旧"的，最新的下载地址：

http://code.google.com/p/paoding/downloads/list

SVN地址为：http://paoding.googlecode.com/svn/trunk/paoding-analysis/ 

同时也可以通过浏览器访问http://paoding.googlecode.com/svn/trunk/paoding-analysis/  直接浏览代码。

最新的在JavaEye的发布帖子是：

http://www.iteye.com/topic/110148   中文分词 庖丁解牛 2.0.0 发布

 

• Paoding.rar (1.1 MB)
• 描述: 中文分词“庖丁解牛”，面向对象，高效率，高扩展性
• 下载次数: 6782

• HashBinaryDictionary.java.rar (2.2 KB)
• 描述: 原来的HashBinaryDictionary.java使用对第一个字符hash+二份查找。这个算法已经不错。 但下面的更新使用了更好的策略。可连续hash词语的字符。理论上这个词典算法应该到达极致了。 覆盖HashBinaryDictionary.java在com/sohospace/dictionary下
• 下载次数: 2578

• Main1.java.rar (6.1 KB)
• 描述: 对一个长度2185856的字符串(4,347,520字节)的分词效率测试。 下载解压后添加到源文件中
• 下载次数: 2402

分享到：

Apache httpd和Tomcat结合配置web应用 应 ...

• 2007-01-23 12:19
• 浏览 49253
• 评论(72)
• 论坛回复 / 浏览 (66 / 133830)
• 分类:企业架构
• 查看更多

评论

32 楼 imjl 2007-01-26  

呵呵，，泼点冷水，，从应用角度来看

我觉得个人做ｌｕｃｅｎｅ中文分词，没有什么商业价值．
因为中文分词牵涉的不单单是编程知识，还有自然语言等方面的知识．
ＹＡＨＯＯ目前采用的中文分词还是购买的．
什么样的公司需要自己订做中文分词？　就ｌｕｃｅｎｅ的两个ａｎａｌｙｚｅｒ足够用了。
有多少是做类似ｙａｈｏｏ，ｂａｉｄｕ这样大的搜索引擎，，只有这样的公司需要中文分词，国内还有其他公司需要自己中文分词吗？我觉得都用不到。包括ｓｉｎａ，１６３，ｓｏｈｕ这样的门户。


从技术角度我支持你。

31 楼 lordhong 2007-01-26  

拜达人...

30 楼 Qieqie 2007-01-26  

考虑中，我的思考点是：

1、能够促进持续改进，相互提升
2、鼓励实践中做适应性的变更
3、保护开放源代码机制


有人专门研究各开源协议的不？

29 楼 netfishx 2007-01-26  

alin_ass 写道

Qieqie同志


能不能把你的代码挪到我的开源项目里？保留你的声明和作者名，包名和代码要修改

同问，作者能不能定下来用什么开源协议？否则我们不敢用啊。

28 楼 alin_ass 2007-01-26  

Qieqie同志


能不能把你的代码挪到我的开源项目里？保留你的声明和作者名，包名和代码要修改

27 楼 billgmh 2007-01-26  

Qieqie 写道

billgmh 写道

我也正在就中文分词方向进行研究，也是使用首字hash＋折半查找的方法构造词典的，是我尝试过分词效率最高的一种词典实现方式，但是最近我收集到一份论文《基于双数组Trie树的词典查询算法》，发现效率可能比基于双数组Trie树的词典查询算法还要高（利用有穷自动机的原理与Trie树的易扩展性），不知楼主有没有尝试过这种方法呢？

加粗的句子看不明白是什么意思。

HashBinaryDictionary.java.rar中的java文件，他不是单纯的首字hash+折半查找。

只要参数设置的好，可以认为采用hash查找的时间复杂度是O(1)，而折半不管怎么说也是log2n，而且每次折半比较都要对字符串和目标词语各个字符进行compare。所以，不能只满足对首字进行hash。

我的原始想法是： 每读入字符串一个新的字符，都要能够把字符串限制到最可能小的位置范围中，直至这个限制在很小很小的范围内(由下面的C来衡量)，然后在最终的这个很小很小的范围内判断是否有该字符串，从而达到最快查找。[分词效率高不高，关键是词典查找算法构造得是否优化关系很大，跟分词采用策略关系较少]

我具体采用的是，尽量hash每个字符：

第一次 对第0个字进行hash，所有首字相同的词语是一个子集合。这个子集合相对整个词典称为子词典。
循环每个子词典
   

• 如果这个子词典的词语数 < 某个常数C(我暂使用C=16) 那这个子词典使用二分查找(对应BinaryDictionary.java)。
    
• 否则 继续对这个子词典做与第一次一样的hash(只是这一次hash的字符是上一次hash的字符的后一位，即上次是第0个字符，这一次就是第1个字符，以此类推)，分解出再下一级的子词典。

极端情况下设置C=2，那就是逐字匹配算法，词语查找就和词典的词汇量没有关系了，O(1)。
[该算法已在HashBinaryDictionary.java.rar的java体现。需要下载该rar替代Paoding.rar中的HashBinaryDictionary.java]

多谢楼主的解释，受教了……我之前也尝试过双重Hash，但是效率没有首字hash＋折半查找高，我第一层Hash是根据词汇的长度来计算的，第二层Hash是首字Hash，最后得到词汇子表进行折半查找，可是我发现效率反而比不上首字Hash＋折半查找来得高。
PS：加粗部分写错了，《基于双数组Trie树的词典查询算法》文中介绍的词典实现宣称比现有的词典实现的效率都高，楼主有空可以上google搜索这篇论文来比对一下。

26 楼 Qieqie 2007-01-26  

对了，“庖丁”是支持自定义算法的。实现特制的Knife，然后注册到Paoding这个类便可。现在这个注册过程由XFactory.java负责，有兴趣时可以弄成Spring xml配置。

25 楼 Qieqie 2007-01-25  

我矛盾中....

“羽毛球拍卖了”如何解词？ 最短路径的切分方法的切分结果会是什么？

24 楼 方世玉 2007-01-25  

Qieqie 写道

菲利浦思 写道

这种切分还是有很明显的缺点.例如下面一段文字:
"发展社区老年活动场所和服务设施"

如果我想搜索日本的和服相关资料,输入关键字"和服"的时候,上面的资料也会被搜索出来

搜索引擎是第一步搜索：
      在浩瀚的信息中，快速集结最后可能是所想要的结果，按照可能是最好的顺序展现出来。

人的眼睛是第二步搜索：
      找寻最符合要求的结果，同时将机器无法轻易识别的少数“无效”结果过滤

“和服”问题，涉及了汉语语义的问题，几乎不可完全解决(可作为“特例”解决，或通过排序方法，将他排到相对靠后等价解决)。

涉及语义的问题也可以通过数学的方法来解决。楼主可以参考一下google上的那个基于最短路径的切分方法。
象“结合成分子时”这样的句子用词库的最长匹配是解决不了。基于概率的最短路径就可以。

23 楼 Qieqie 2007-01-25  

billgmh 写道

我也正在就中文分词方向进行研究，也是使用首字hash＋折半查找的方法构造词典的，是我尝试过分词效率最高的一种词典实现方式，但是最近我收集到一份论文《基于双数组Trie树的词典查询算法》，发现效率可能比基于双数组Trie树的词典查询算法还要高（利用有穷自动机的原理与Trie树的易扩展性），不知楼主有没有尝试过这种方法呢？

加粗的句子看不明白是什么意思。

HashBinaryDictionary.java.rar中的java文件，他不是单纯的首字hash+折半查找。

只要参数设置的好，可以认为采用hash查找的时间复杂度是O(1)，而折半不管怎么说也是log2n，而且每次折半比较都要对字符串和目标词语各个字符进行compare。所以，不能只满足对首字进行hash。

我的原始想法是： 每读入字符串一个新的字符，都要能够把字符串限制到最可能小的位置范围中，直至这个限制在很小很小的范围内(由下面的C来衡量)，然后在最终的这个很小很小的范围内判断是否有该字符串，从而达到最快查找。[分词效率高不高，关键是词典查找算法构造得是否优化关系很大，跟分词采用策略关系较少]

我具体采用的是，尽量hash每个字符：

第一次 对第0个字进行hash，所有首字相同的词语是一个子集合。这个子集合相对整个词典称为子词典。
循环每个子词典
   

• 如果这个子词典的词语数 < 某个常数C(我暂使用C=16) 那这个子词典使用二分查找(对应BinaryDictionary.java)。
    
• 否则 继续对这个子词典做与第一次一样的hash(只是这一次hash的字符是上一次hash的字符的后一位，即上次是第0个字符，这一次就是第1个字符，以此类推)，分解出再下一级的子词典。

极端情况下设置C=2，那就是逐字匹配算法，词语查找就和词典的词汇量没有关系了，O(1)。
[该算法已在HashBinaryDictionary.java.rar的java体现。需要下载该rar替代Paoding.rar中的HashBinaryDictionary.java]

22 楼 alin_ass 2007-01-25  

Qieqie 写道

感觉在RedSage.com上申请个版本控制服务是个不错注意

code.google.com的svn最好用了啊，又不用申请
前阵子光纤断了我都照用，

sf目前的速度基本废了



你求职的事情，我发你站内短信了，请回复或加我msn

21 楼 alin_ass 2007-01-25  

为了在我的eclipse里看你的代码， 我中午牺牲休息时间写了一个小小的批量转码的软件，类似iconv

20 楼 Qieqie 2007-01-25  

感觉在RedSage.com上申请个版本控制服务是个不错注意

19 楼 dwangel 2007-01-25  

subversion不好吗?

18 楼 Qieqie 2007-01-25  

netfishx 写道

查了一下，楼主似乎没有处理噪声词啊

是啊，bug!

bugfix:

请在com.sohospace.paoding.cjk.FileWordsLoader.java的loadCJKVocabulary方法返回前加上如下以行代码：

Merger.remove(base, ejk.get("x干扰词"));

经过调试解决了该bug！

alin_ass 写道

lz,你的代码包是gbk的，我把源码部分转成utf8传上来，需要的来下附件

>>>>>感谢中，我已经把说明加到主贴上了。


不知哪里有较好的网上 版本控制器 推荐下？ 这样该代码就好办了。

17 楼 netfishx 2007-01-25  

查了一下，楼主似乎没有处理噪声词啊

16 楼 alin_ass 2007-01-25  

lz,你的代码包是gbk的，我把源码部分转成utf8传上来，需要的来下附件

15 楼 Qieqie 2007-01-25  

Merger.merge()方法在com.sohospace.paoding.cjk.FileWordsLoader.java的loadCJKVocabulary()方法中使用。

目的是：将读到的多个词语清单(LinkedList的形式)合并到第一个LinkedList中，并且保持升序。从而支持多个词典文件组成一个大词典(Vocabulary)。

Merger.merge()采用的是归并算法。

14 楼 xingqing 2007-01-25  

/*
* 本代码所有权归作者所有 但在保持源代码不被破坏以及所有人署名的基础上 任何人可自由无限使用
*/
package com.sohospace.dictionary.support.merging;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.ListIterator;

/**
*
* @author [e-mail]
*
* @since 1.0
*
*/
public class Merger {

public static void merge(LinkedList<String> a, LinkedList<String> b) {
ListIterator<String> aIter = (ListIterator<String>) a.iterator();
ListIterator<String> bIter = (ListIterator<String>) b.iterator();
while (aIter.hasNext() && bIter.hasNext()) {     //判断有没有元素
String aWord = aIter.next();
System.out.println("aWord="+aWord);
boolean bGoOn = true;
while (bGoOn && bIter.hasNext()) {
String bWord = bIter.next();
System.out.println("bWord="+bWord);
int r = bWord.compareTo(aWord);
System.out.println("r="+r);
if (r == 0) {
continue;
}
if (r < 0) {
aIter.previous();
aIter.add(bWord);
aIter.next();
}
else {
bIter.previous();
bGoOn = false;
}
}
}
while (bIter.hasNext()) {
a.add(bIter.next());
}
}

public static void remove(LinkedList<String> a, LinkedList<String> b) {
ListIterator<String> aIter = (ListIterator<String>) a.iterator();
ListIterator<String> bIter = (ListIterator<String>) b.iterator();
while (aIter.hasNext() && bIter.hasNext()) {
String aWord = aIter.next();
boolean bGoOn = true;
while (bGoOn && bIter.hasNext()) {
String bWord = bIter.next();
int r = bWord.compareTo(aWord);
if (r == 0) {
aIter.remove();
if (aIter.hasNext()) {
aWord = aIter.next();
}
}
else if (r < 0){
continue;
}
else {
bIter.previous();
bGoOn = false;
}
}
}
}

public static void main(String[] args) {
LinkedList<String> a = new LinkedList<String>();
LinkedList<String> b = new LinkedList<String>();
a.add("1");
a.add("4");
a.add("a");
a.add("c");

b.add("2");
b.add("3");
b.add("b");
b.add("d");
b.add("太阳");

Merger.merge(a, b);
//Merger.remove(a, b);

System.out.println(Arrays.toString(a.toArray(new String[]{})));
   // System.out.println(Arrays.toString(b.toArray(new String[]{})));
}
}

运行后为aWord=1
bWord=2
r=1
aWord=4
bWord=2
r=-2
bWord=3
r=-1
bWord=b
r=46
aWord=a
bWord=b
r=1
aWord=c
bWord=b
r=-1
bWord=d
r=1
[1, 2, 3, 4, a, b, c, d, 太阳]
这个类在程序中起到什么作用?

13 楼 billgmh 2007-01-25  

<br/>
<strong>Qieqie 写道：</strong><br/>
<div class='quote_div'>
<p><font><strong>Lucene中文分词 “庖丁解牛” </strong></font></p>
<p><font>附件 为本人设计编写的组件，中文分词“庖丁解牛”，具有相当好的使用价值。。。 </font></p>
<p>高效率：我的赛扬PC <strong>1 秒</strong>解析 <strong>&gt;&gt;&gt; 20000</strong>汉字的词语  (实际测试结果数据，可达<strong>1秒10万</strong>汉字)<br/>
高可维护性：使用“庖丁”隐喻，形象明晰<br/>
高灵活性，可扩展：OOD</p>
<p><font>对比：《终于突破中文分词的效率问题》<a href='http://www.lucene.org.cn/read.php?tid=54&amp;amp;fpage=2 '>http://www.lucene.org.cn/read.php?tid=54&amp;fpage=2 </a>他的效率为 <strong>6秒</strong> 解析<strong>2588</strong>汉字<br/>
 <br/>
示例程序为<font>com.sohospace.lucene.analysis.xanalyzer.Main0</font></font></p>
<p><font/></p>
<p><font>附带广告&lt;偶<strong>寻觅工作中</strong>&gt;：</font> </p>
<p><font><strong>我是</strong>： <br/>
接近5年Java/J2EE开发经验。good at Java底层基础, 网站开发架构与技术, 设计模式, 面向对象。 <br/>
崇尚有效的工作和管理。 </font></p>
<p><font><strong>我要</strong>： <br/>
找一个Java/J2EE架构师、高级工程师职位(北京)。</font></p>
<p><font>我的联系方法： <br/>
email: [e-mail] <br/>
skype:jimudugushi <br/>
tel: 133-xxxx-0083</font></p>
<p><font> </font></p>
<p> </p>
</div>
我也正在就中文分词方向进行研究，也是使用首字hash＋折半查找的方法构造词典的，是我尝试过分词效率最高的一种词典实现方式，但是最近我收集到一份论文《<font>基于双数组Trie树的词典查询算法》，发现效率可能比<font>基于双数组Trie树的词典查询算法还要高（利用有穷自动机的原理与Trie树的易扩展性），不知楼主有没有尝试过这种方法呢？</font></font><br/>

« 上一页 1 2 3 4 下一页 »