分词算法千差万别。正向最大匹配算法应该算比较简单的一种。

性能不是很高,并且不能显示词性等,比较依赖于词典,不能进行语法分析等。

 

今天在学习的时候,在博客上看到了用到字典树,自己也总结一下。

以下是算法思想:


 

正向最大匹配算法:从左到右将待分词文本中的几个连续字符与词表匹配,如果匹配上,则切分出一个词。但这里有一个问题:要做到最大匹配,并不是第一次匹配到就可以切分的 。我们来举个例子:

           待分词文本:   content[]={“中”,”华”,”民”,”族”,”从”,”此”,”站”,”起”,”来”,”了”,”。”}

           词表:   dict[]={“中华”, “中华民族” , “从此”,”站起来”}

(1) 从content[1]开始,当扫描到content[2]的时候,发现”中华”已经在词表dict[]中了。但还不能切分出来,因为我们不知道后面的词语能不能组成更长的词(最大匹配)。

(2) 继续扫描content[3],发现”中华民”并不是dict[]中的词。但是我们还不能确定是否前面找到的”中华”已经是最大的词了。因为”中华民”是dict[2]的前缀。

(3) 扫描content[4],发现”中华民族”是dict[]中的词。继续扫描下去:

(4) 当扫描content[5]的时候,发现”中华民族从”并不是词表中的词,也不是词的前缀。因此可以切分出前面最大的词——”中华民族”。

 

由此可见,最大匹配出的词必须保证下一个扫描不是词表中的词或词的前缀才可以结束。


 

在用前缀的时候,很明显用Trie树比较合适的。

先把所有的字典建树,然后再把整个字符串不断的查询,速度很快。

源码的话。

这个博客写的不错:http://www.cnblogs.com/chenying99/archive/2012/09/30/2709025.html

SimHash算法在文档关联时的应用

1.使用背景 最近在做中国软件杯,涉及到文档关联,一开始用的方法是提取文档关键词,然后建立特征向量。 当上传一篇文档的时候,对文档分词,去掉停词,然后...

阅读全文

最大生成树在图片拼接中的应用

之前已经写过一篇 stitching_detailed的源码理解了。里面提到了最大生成树的问题。 今天想单独拿出来放在一个专栏里面,以后持续的写下去。   以前在ACM...

阅读全文

欢迎留言

*