基于Java的搜索引擎Nutch中文搜索技術(shù)研究

基于Java的搜索引擎Nutch中文搜索技術(shù)研究

摘要：Nutch是一個優(yōu)秀的基于Java的開放源碼搜索引擎，為了使它能夠支持中文搜索，本文在分析了Nutch結(jié)構(gòu)的基礎(chǔ)上，采用詞表分詞技術(shù)和前向匹配分詞算法對中文信息進行分詞，以JavaCC腳本實現(xiàn)上下文相關(guān)文法中文分析模塊，成功實現(xiàn)了Nutch中文搜索功能。關(guān)鍵詞：搜索引擎;分詞;正規(guī)Abstract:InordertoenableChinesesearchinNutch，whichisanexcellentJava-basedopensourcesearchengine，thispaperanalysesthestructureofNutchandseparateswordsinChineseinformationbasedonChinesedictionaryandforwardmatchingalgorithm.ChineseanalysismoduleisgeneratedbyJavaCCscript;thatresultsinsupportingChinesesearchinNutch.Keywords:SearchEngine;WordSegmentation;RegularExpression1前言搜索引擎[1]是當今網(wǎng)絡(luò)應(yīng)用的核心問題，已經(jīng)受到各企業(yè)和研究部門的廣泛關(guān)注。Lucene和Nutch是針對國外英文系統(tǒng)環(huán)境的搜索引擎，本文在研究了中文分詞技術(shù)和JavaCC技術(shù)的基礎(chǔ)上，成功地實現(xiàn)了Lucene和Nucth的中文分析模塊，使Lucene和Nucth能夠?qū)崿F(xiàn)中文信息檢索。2Nutch分析Lucene是開放源碼的基于Java的全文檢索引擎，其貢獻者DougCutting是一位資深全文索引/檢索專家。作為一個全文檢索系統(tǒng)，在進行檢索之前需要建立索引，索引的過程是先讀取文章中的詞語，然后一一存放在稱為倒排索引文件的索引數(shù)據(jù)庫(IndexDatabase)中。索引數(shù)據(jù)庫記錄了詞語出現(xiàn)的位置，頻率等相關(guān)信息，以備后面讀取。Nutch是Cutting創(chuàng)建的另一個Java開源項目，目的是提供全功能的搜索引擎，其底層借助了Lucene的部分功能，并且索引結(jié)構(gòu)與Lucene兼容。Lucene和Nutch并沒有規(guī)定數(shù)據(jù)源的格式，而只提供了一個通用的結(jié)構(gòu)（Document對象）來接受索引的輸入，因此輸入的數(shù)據(jù)源可以是數(shù)據(jù)庫、WORD文檔、PDF文檔和HTML文檔，只要能夠設(shè)計相應(yīng)的解析轉(zhuǎn)換器將數(shù)據(jù)源構(gòu)造成Docuement對象即可進行索引。對于大批量的數(shù)據(jù)索引，還可以通過調(diào)整IndexerWrite的文件合并頻率屬性（MergeFactor）來提高批量索引的效率。用戶輸入查詢字符串（QueryString），然后經(jīng)過分析器的分析，就會產(chǎn)生一個Query對象。真正搜索時，使用IndexSearcher類的search方法，它返回Hits對象。通過遍歷Hits對象的所有文檔(document)，就可以找到所有被搜索到的文章（頁面）。查詢字符串的語法定義為：Query::=(Clause)*Clause::=["+"，"-"][<TERM>":"](<TERM>|"("Query")")中間的邏輯包括：andor+-&&||等符號，而且還有"短語查詢"和針對西文的前綴/模糊查詢等?？偟膩碚f，這是其他很多搜索引擎都不具備的功能。通過修改QueryParser的語法生成腳本，還可以修改或擴展查詢分析器的功能，使它更加適用于中文環(huán)境。所有的問題都通過一個額外抽象層來方便以后的擴展和重用，通過重新實現(xiàn)來達到自己的目的，而對其他模塊而不需要。可以簡單的應(yīng)用入口Searcher，Indexer，并調(diào)用底層一系列組件協(xié)同的完成搜索任務(wù)。所有的對象的任務(wù)都非常專一，比如搜索過程QueryParser分析將查詢語句轉(zhuǎn)換成一系列的精確查詢的組合(Query)，通過底層的索引讀取結(jié)構(gòu)IndexReader進行索引的讀取，并用相應(yīng)的打分器給搜索結(jié)果進行打分/排序等。所有的功能模塊原子化程度非常高，因此可以通過重新實現(xiàn)而不需要修改其他模塊。除了靈活的應(yīng)用接口設(shè)計，Lucene和Nutch還提供了一些適合大多數(shù)應(yīng)用的語言分析器實現(xiàn)（SimpleAnalyser，StandardAnalyser），這也是新用戶能夠很快上手的重要原因之一。3Nutch中文搜索3.1中文分詞在搜索引擎和各種語言處理的需要中，分詞可以說是最基本的操作。漢語句子是由詞語組成的，人們在使用漢語時，可以直接理解并使用它。對于計算機，是不可能達到人類的智能的，也不能理解人類語言。但是，由于人類仍然希望計算機能理解人類的語言，并且迫切的希望使用在各種商業(yè)和技術(shù)領(lǐng)域中，因此提出了計算機形式文法[2]。但是現(xiàn)有形式文法是建立在事先分詞的基礎(chǔ)上的。對于某些語言，單詞之間有特定的符號隔開（一般是空格），所以沒有任何分詞的困難。而漢語與其他語言都有很大的不同，漢字之間沒有空格。如果想繼續(xù)沿用西方的形式文法理論處理漢語，那么必然涉及到中文分詞問題[3]。在系統(tǒng)實現(xiàn)中使用詞表分詞。詞表中文分詞的原理，是根據(jù)現(xiàn)有詞庫進行字符串模式匹配，把長的字符串分割為若干個詞庫中已經(jīng)存在的詞語即可。因此，制作詞庫成為必須的，詞庫中詞語的選擇也要慎重。系統(tǒng)選擇的是一個大小為53301個中文詞語，按照拼音順序排列的文本格式的詞庫，詞語之間使用回車符隔開。這個詞庫在使用時，要全部調(diào)入內(nèi)存。為此，使用哈希表來實現(xiàn)。這是因為詞庫是使用最頻繁的公有資源，把詞庫的調(diào)入和查詞工作封裝到WordDataBase類中，這是一個靜態(tài)類作為公有資源使用，不允許產(chǎn)生多個實例。分詞系統(tǒng)同時為Lucene索引器、Lucene查詢分析器和Nutch分析器提供服務(wù)。詞庫選擇的好壞，直接影響著Lucene和Nutch的表現(xiàn)。對于Lucene來說，是否收入長詞語并沒有多大關(guān)系。因為Lucene可以將相對短的詞語進行索引，查詢時，不會造成什么影響。例如，“中華人民共和國”這個詞語并不存在于詞庫中，而是“中華”，“人民”，“共和國”三個詞語存在。在索引時，這三個詞語被連續(xù)的索引。Lucene查詢分析器將“中華人民共和國”解釋為一個短語查詢對象（PhraseQuery），由三個TermQuery組成，分別是“中華”，“人民”，“共和國”。由于PhraseQuery查詢要求索引中的詞語順序必須與組成它的TermQuery的順序一致且必須連續(xù)，因此在查詢時同樣能正確的查到。如此一來，似乎可以不再需要詞庫，直接對每一個漢字做索引就可以了。這樣做當然沒有任何問題，有些搜索引擎就是這么做的。但是為了查準率，這樣做就有一個缺點，即分詞中的交叉歧義和包含歧義問題。由于是在無語義的情況下分詞，只能作某些字符串運算（實際上是字符串模式匹配）來進行分詞，因此出現(xiàn)了不同的分詞策略。每一種策略的分詞結(jié)果可能不同，這完全依賴于詞庫。所有的分詞方法為：前向遞增最大匹配分詞、前向遞減最大匹配分詞、前向遞增最小匹配分詞、前向遞減最小匹配分詞、后向遞增最大匹配分詞、后向遞減最大匹配分詞、后向遞增最小匹配分詞和后向遞減最小匹配分詞，共計8種方法。系統(tǒng)實現(xiàn)了4種前向分詞方法，基本上就可以滿足需要。由于現(xiàn)代漢語文章中，充斥著大量的英文單詞甚至句子，尤其是計算機方面。鑒于英文是世界上使用最廣泛的語言，中文文章中含有另外的語言的可能性不大。英文分詞是很簡單的，根據(jù)空格作為分隔符即可。但是，還有一些特殊的單詞，必須要考慮。另外涉及到一個重要問題，也是最復雜的一個問題，就是漢字之間的空格如何處理。一般來講，漢字之間不可能出現(xiàn)空格。在計算機中，有時候為明確區(qū)分漢字，也人為地加上空格。處理方法是決不可以把空格當作中文的詞語分隔符，因為空格一般恰恰是出現(xiàn)在詞語的中間。對于整個分詞系統(tǒng)來說，還應(yīng)該允許用戶自由選擇需要的詞語，即提供過濾功能。系統(tǒng)允許用戶設(shè)置中文詞語，英文詞語，中文停止詞，英文停止詞分別是否要加入結(jié)果Word列表中。停止詞表示一種語言中的大量出現(xiàn)且無關(guān)緊要的通用詞語，例如助詞、嘆詞和介詞等。這些信息預先定義在WordDataBase中。對于中文來說，“的”，“地”，“得”等都可以作為停止詞。對于英文，則有“this”，“are”，“the”等。3.2JavaCC分析JavaCC是集分詞和語法分析與一身的針對Java語言的文本自動分詞軟件包[4]，類似于Unix系統(tǒng)中的LEX和YACC工具。JavaCC把這兩者的功能結(jié)合，形成了一個功能強大的分析工具。用戶只需寫出分析腳本，JavaCC就會生成符合用戶要求的類，用來進行詞法和語法分析。JavaCC使用了自動機的理論，而不是遞歸下降分析，Lucene和Nutch正是利用JavaCC這個十分強大的工具，生成系統(tǒng)的分詞器。JavaCC的語法定義是由正規(guī)式(RegularExpression)來完成的。在這里，指的是上下文無關(guān)文法。理解形式文法的定義，才能更好的理解和使用JavaCC。在一種語言中，存在非終結(jié)符和終結(jié)符兩種單詞。正規(guī)式就定義了一個非終結(jié)符怎樣被替換為另一個字符串。正規(guī)式可以描述一種語言，符合該正規(guī)式定義的所有句子都是這個語言的句子。或者，正規(guī)式描述了正規(guī)文法，又稱線性文法，或上下文無關(guān)文法[5]。稱為線性，是因為這種文法可以從前到后順序的被指定為一個句子。JavaCC的語法定義功能十分強大，可以做幾乎所有的限制和指定。它提供了四種正規(guī)式類型：regexpr_kind::="TOKEN"|"SPECIAL_TOKEN"|"SKIP"|"MORE"TOKEN:它表示語法中的單詞(Token)，這個段中的正規(guī)式規(guī)定了這種語言中單詞的語法，即分詞的依據(jù)。單詞管理器(TokenManager)依據(jù)每一個正規(guī)式來匹配下一個單詞，這是按照最大匹配規(guī)則進行的。如果有多個匹配，那么選擇最長的單詞返回。如果有幾種正規(guī)式產(chǎn)生了相同長度的最長單詞，那么以較笨重正規(guī)式的順序，返回最先定義的正規(guī)式產(chǎn)生的單詞。單詞管理器匹配出要返回的單詞后，即返回給語法分析器。SPECIAL_TOKEN:在SPECIAL_TOKEN段寫出的正規(guī)式規(guī)定了特殊單詞。特殊單詞也是一種單詞，但是并不起實際的作用，也不能從getNextToken中訪問到。它的訪問方式是從Token類的specialToken屬性來讀取。對于一種語言，如果某些單詞不起語法的作用，但也是句子的一部分，那么可以使用特殊單詞。例如編程語言中的注釋。SKIP:由SKIP段產(chǎn)生的單詞被跳過（即忽略）。當我們不惜望出現(xiàn)某種模式的單詞時，即可使用SKIP段。MORE:當一個單詞不能一次被產(chǎn)生，而必須逐漸產(chǎn)生時，則使用MORE。未完成的Token被存儲在一個StringBuffer對象中，我們可以任意修改。所謂正規(guī)式，實際就是產(chǎn)生式。它的語法格式如下：javacode_production::="JAVACODE"java_return_typejava_identifier"("java_parameter_list")"java_blockJAVACODE產(chǎn)生式可以寫入任何Java代碼，也可以寫EBNF（擴展的Backus-Naur范式）。實際上，在某種程度上上下文無關(guān)語言就變成了上下文相關(guān)語言，因為Java代碼可以處理有關(guān)語境的信息。例如，在修改的腳本加入了代碼以后，就是一個上下文相關(guān)語言。有時候，當EBNF無法自行描述語法時，也可以借助“無所不能的”Java代碼。例如下面的代碼，非終結(jié)符"skip_to_matching_brace"的作用是跳過完整匹配的括號。實際上，這個工作是EBNF無法完成的，因為它描述的不是線性文法。但是，使用Java代碼可以很容易的解決：JAVACODEvoidskip_to_matching_brace(){Tokentok;intnesting=1;while(true){tok=getToken(1);if(tok.kind==LBRACE)nesting++;if(tok.kind==RBRACE){nesting--;if(nesting==0)break;}tok=getNextToken();}}3.2利用JavaCC構(gòu)造中文分析模塊JavaCC是根據(jù)西方語言的形式文法理論設(shè)計的，不能直接解決中文問題。當仔細研究后，發(fā)現(xiàn)所謂的“中文問題”實際上就是如何把上下文無關(guān)文法轉(zhuǎn)變?yōu)樯舷挛南嚓P(guān)文法。EBNF當然不能解決這個問題。通過寫入Java代碼，用各種對象和標志變量制作特殊的“上下文”環(huán)境，就可以實現(xiàn)JavaCC的中文分詞。Lucene和Nutch原來的腳本在TOKEN段進行了精細的刻畫，對于英文單詞、主機地址、電子郵件地址、數(shù)字、縮寫等各種格式都進行了考慮。只需利用中文分詞功能，直接傳入中文句子，得到ArrayList類型的返回結(jié)果。因此，唯一的工作就是事先分出一個全部是中文的字符串，這一點通過下面的定義實現(xiàn)：<CHINESE:(<CJK>)+(""|<CJK>)*><#CJK:["\u3040"-"\u318f"，"\u3300"-"\u337f"，"\u3400"-"\u3d2d"，"\u4e00"-"\u9fff"，"\uf900"-"\ufaff"]>上面的CHINESE的定義為：由漢字開頭，包含漢字或空格的最長的字符串，而漢字則定義為CJK。CJK即中國、日本、朝鮮和韓國使用的中國漢字的總稱，全稱為CJKIdeographs(CJK象形文字)，這是Unicode標準所定義的。在Lucene中，一旦實現(xiàn)了中文字符串的提取，就可以把它進行分詞，然后在next方法中返回。但是，在Nutch中QueryParser已經(jīng)取