搜索引擎中文分詞原理與實現(xiàn)

1、搜索引擎中文分詞原理與實現(xiàn)搜索引擎中文分詞原理與實現(xiàn)因為中文文本中，詞和詞之間不像英文一樣存在邊界，所以中文分詞是一個專業(yè)處理中文信息的搜索引擎首先面對的問題，需要靠程序來切分出詞。一、一、Lucene中的中文分詞中的中文分詞Lucene在中處理中文的常用方法有三種，以“咬死獵人的狗”為例說明之：單字：【咬】【死】【獵】【人】【的】【狗】二元覆蓋：【咬死】【死獵】【獵人】【人的】【的狗】分詞：【咬】【死】【獵人】【的】【狗】Lucene

2、中的StardTokenizer采用單子分詞方式，CJKTokenizer采用二元覆蓋方式。1、Lucene切分原理Lucene中負責語言處理的部分在g.apache.lucene.analysis包，其中，TokenStream類用來進行基本的分詞工作，Analyzer類是TokenStream的包裝類，負責整個解析工作，Analyzer類接收整段文本，解析出有意義的詞語。通常不需要直接調(diào)用分詞的處理類analysis，而是由Luce

3、ne內(nèi)存內(nèi)部來調(diào)用，其中：（1）在索引階段，調(diào)用addDocument（doc）時，Lucene內(nèi)部使用Analyzer來處理每個需要索引的列，具體如下圖：圖1Lucene對索引文本的處理IndexWriterindex=newIndexWriter(indexDirectynewCnAnalyzer()用于支持分詞的分析器!incrementalIndexWriter.MaxFieldLength.UNLIMITED)（2）在搜索階段

4、，調(diào)用QueryParser.parse（queryText）來解析查詢串時，QueryParser會調(diào)用Analyzer來拆分查詢字符串，但是對于通配符等查詢不會調(diào)用Analyzer。Analyzeranalyzer=newCnAnalyzer()支持中文的分詞QueryParserparser=newQueryParser(Version.LUCENE_CURRENT“title“analyzer)因為在索引和搜索階段都調(diào)用了分詞過

5、程，索引和搜索的切分處理要盡量一致，所以分詞效果改變后需要重建索引。為了測試Lucene的切分效果，下面是直接調(diào)用Analysis的例子：Analyzeranalyzer=newCnAnalyzer()創(chuàng)建一個中文分析器TokenStreamts=analyzer.tokenStream(“myfield“newStringReader(“待切分文本“))取得Token流含第一個字符的節(jié)點有指針指向下一個字符的節(jié)點，依次類推。這樣組成一

6、個層次結構的樹，樹的第一層包括所有單詞的第一個字符，樹的第二層包括所有單詞的第二個字符，依次類推，數(shù)字搜索樹的最大高度是詞典中最長單詞的長度。比如：如下單詞序列組成的詞典（asatbebyheinisitofonto）會生成如下圖所示的數(shù)字搜索樹：圖3數(shù)字搜索樹數(shù)字搜索樹的結構獨立于生成樹時單詞進入的順序，這里，Trie樹的高度是2。因為樹的高度很小，在數(shù)字搜索Trie樹種搜索一個單詞的速度很快。但是，這是以內(nèi)存消耗為代價的，樹中每個節(jié)

7、點都需要很多內(nèi)存。假設每個詞都是由26個小寫英文字母中的一個組成的，這個節(jié)點中會有26個指針。所以不太可能直接用這樣的數(shù)字搜索樹來存儲中文這樣的大字符集。Trie樹在實現(xiàn)上有一個樹類（SearchTrie）和一個節(jié)點類（TrieNode）。SearchTrie的主要方法有兩個：（1）增加單詞到搜索樹，方法原型是：addWd（Stringwd）。（2）從文本的指定位置開始匹配單詞，方法原型是：matchLong（Stringtextint

8、offset）。2、三叉Trie樹在一個三叉搜索樹（TernarySearchTrie）中，每一個節(jié)點包括一個字符，但和數(shù)字搜索樹不同，三叉搜索樹只有三個指針：一個指向左邊的樹；一個指向右邊的樹；還有一個向下，指向單詞的下一個數(shù)據(jù)單元。三叉搜索樹是二叉搜索樹和數(shù)字搜索樹的混合體。它有和數(shù)字搜索樹差不多的速度但是和二叉搜索樹一樣只需要相對較少的內(nèi)存空間。樹是否平衡取決于單詞的讀入順序。如果按順序后的順序插入，則生成方式最不平衡。單詞的讀入