【文章內(nèi)容簡介】 的短語(key phrase)，準確的找尋到，這樣既能夠準確的解讀文檔中的關(guān)鍵信息，同時能夠大大提高聚類的可讀性。提取出來的短語首先要確保的是其完整性。提出了短語完整性的概念。設文檔T，其長度為N，T的完整子字符串S定義為：S稱為T的完整子字符串，當S在T中出現(xiàn)互不相同的k次的位置P， P2.. .， Pk時，其中至少存在一對吏得T中第(/01個字符與第個字符不相同（左完整性），并且，其中至少存在一對(/，/)(1^〗^_/^/0使得了中第(p， +|s1)個字符與第(/^ +岡)個字符不相同(右完整性)。我們以文檔T= “to—be—or—not—to—be”和T的子字符串“to_be”為例，說明一下以上的概念。左完整：子字符串“to_be”是左完整的，比較第(01)個字符，和第（131)個字符（“―”），兩者不同，根據(jù)以上概念定義，“to—be”是左完整的。右完整：子字符串“to_be”也是右完整的，比較T中第(0+5)個字符（“一”）和第（13+5)個字符(T的結(jié)尾處），兩者不相同，根據(jù)以上概念定義，“to—be”也‘ 是右完整的。 根據(jù)完整字符串的定義，“to_be”就是T的完整字符串。在LINGO算法中，后綴數(shù)組(Suffix Array)是一個重要的數(shù)據(jù)的結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)的特點就是效率特別的高，高效率來自于它能夠準確的對文檔或者文本中的信息進行充分的解讀，并從中找出關(guān)鍵性的短語。設一個文檔T，長度為N，T的后綴數(shù)組S指將T所有的后綴按照字符順序排序，而令后綴起始的位置（按排序后的順序）構(gòu)成的數(shù)組。例如，設文檔T ： to_be_or_not_to_be?它的后綴集合為rs，則有下表所示：表1 表3. 2后綴數(shù)組表表3. 2從上述表格可以看出，實際需要存儲的僅僅是表格的中間一列，很明顯后綴數(shù)組的存儲只需要0(aO的空間，其中N為文檔的長度。而創(chuàng)建后綴數(shù)組的算法的期望時間復雜度也是0(aO，查找一個長度為P的字符串只需要0(尸+ logJV)的時間。 LINGO算法基礎之隱含語義分析隱含語義其實是漢語語法中的一個重要的特色，在其他語言中也有所體現(xiàn)，簡言之，隱含語義分析就是針對日常用語中的同義詞或者近義詞進行有效的歸類和合理的分析，同時對具有相同意思表達的詞組短語進行有效的應用，例如，在漢語中，“教師”和“先生”是完全不一樣的兩個詞，但是在詞語的詞義和實際的應用中可以做到語義互換，能夠表達出同樣的含義。如果利用向量空間模型對所有的詞語或者關(guān)鍵詞進行完全匹配，必然無法將同義詞這種意思相同表達不同的詞語做到完全區(qū)分，即如果將“教師”作為關(guān)鍵詞進行搜索，那么對文檔進行聚類分析之后，以“先生”為關(guān)鍵詞內(nèi)容的相關(guān)意思一致的文檔也就無法顯示出來，這給我們的搜索引擎發(fā)展帶來了技術(shù)性的瓶頸。事實上，在搜索引擎的實際應用中，對詞組或者是關(guān)聯(lián)詞的使用，是搜索引擎技術(shù)發(fā)展的一個必由之路，因為在漢語中，有很多類似的隱含語義分析的詞組短語，而它們在外表上看是格格不入的。例如，“高等院校招生”，“高等院?！焙汀罢猩笔莾蓚€相互獨立、又有一定聯(lián)系的關(guān)鍵詞，如果用戶搜索“招生”，就會顯示出含有“招生”作為關(guān)鍵詞的文檔匹配項，但是很可能有一部分包含有“高等院?！钡膬?nèi)容，但是不包含“招生”。所以我們認為這兩個詞存在著一定的語義關(guān)系，這類文檔也可能包含了用戶所需信息。作為一種常用的信息檢索技術(shù)，隱含語義分析（Latent Semantic Indexing， LSI)的出現(xiàn)最重要的作用是彌補向量空間模型所存在的缺陷。根據(jù)隱含語義分析（Latent Semantic Indexing， LSI)的觀點，詞語的選擇背后是隱含著一種來自語言含義方面的信息流，這種信息流是搜索的精髓，如何利用隱含語義分析的方法，從詞中提取的抽象概念替換或者取代與搜索關(guān)鍵詞意思相同的內(nèi)容。即將向量空間模型中簡單的詞匯的匹配替代為語義的匹配。 如果把用來檢索的文檔之間的內(nèi)容看做是詞空間下面的一個子空間，那么任意兩個不同的文檔之間的子空間距離越小，則這兩個文檔之間的語義上就越相關(guān)，因此，詞往往被視作是一個文檔空間內(nèi)下屬的一個子空間，通過對兩個詞語之間的子空間距離進行的判斷，可以對兩個詞語之間的相關(guān)程度進行大致的判斷和分類。在實際操作中，由于詞與詞，文檔與文檔，以及詞語文檔之間的子空間的分布不是隨機分布的狀態(tài)，而是出于全文整體語義、詞義的內(nèi)容之中的，因此會受到上下文和整個文章所要表達的思想的束縛和限制。在這種情況下，語義空間表現(xiàn)出了詞詞、詞文檔、文檔文檔之間在語義上相關(guān)性。而在實際操作中，由于詞文檔矩陣的數(shù)據(jù)往往非常龐大，而且鑒于漢語文化的博大精深，常常會出現(xiàn)一詞多義，多詞一義的情況，這種情況的出現(xiàn)在現(xiàn)代漢語語文的行文和應用充非常常見，因此會給我們的判斷帶來干擾和迷惑，在這種情況下，與向量空間模型中的文檔高維表示不同，潛在語義標引還需要利用數(shù)學工具將原來的文檔高維表示投影到低維的空間、即潛在語義空間中，簡化語義的空間結(jié)構(gòu)，從而達到縮小問題規(guī)模，消除并減少常見的迷惑和干擾。進而在得到潛在語義空間之后，就可以根據(jù)各個詞和文檔的向量坐標進一步進行分析。 LINGO算法過程分析所謂的文本預處理，是指為了進一步提高取類標簽的準確性，將文本以聚類算法可用處理的形式進行預處理，具體包括兩個階段：第一個階段叫做特征表示，第二個階段稱為特征提取。一般常見的理論認為，文本的特征表示的模型有很多，常見的諸如概率檢索模型、布爾模型、概率檢索模型、向量空間模型等都是比較常見的模型，其中最流行的模型當屬向量空間模型。下面具體介紹向量空間模型，根據(jù)向量空間模型的原理，文檔集C中的每個文檔Dj都是一個特征向量，且向量空間模型中所有文檔的特征向量都具有相同的維數(shù)：設為n，這個相同的尾數(shù)是全部文檔中所有不同特征項的總數(shù)目。文檔Dj的特征向量就可以用文檔中的特征項Ti及其權(quán)重Wij來表示：V(Dj={T，W。T，W，i；。T?W， }特征項Ti的權(quán)重Wij的計算才用TFIDF方法的標準定義：= TF，j X IDIf = X logAVDI^在以上的公式中，文檔集C的所有文檔的總和為N，TFi」為特征項T，在文檔Dj中出現(xiàn)的次數(shù)，DFi為文檔集C中包含Ti的文檔數(shù)目。類標簽的提取是第二個步驟，是指在提取之前，需要對所有的包括關(guān)鍵詞和詞組在內(nèi)的關(guān)鍵詞進行提取。我們所采用的LINGO算法在此步驟中采用的方法被稱為奇異值分解法(SVD： Singular Value Deposition)。通過奇異值分解法(SVD： Singular Value Deposition)來發(fā)現(xiàn)抽象的概念，主要是單一主題或者相關(guān)主題的集合，這種方法的有點在于能夠高效率的客服重復的詞組、短語，以及同義詞、近義詞和相關(guān)的人稱物主代詞，切實提高系統(tǒng)的便捷性和高效性。LINGO算法在關(guān)鍵詞組的提取方面采用的技術(shù)被稱為后綴數(shù)組技術(shù)。類標簽的提取大致可以分為三個步驟：即抽象概念的發(fā)現(xiàn)、詞匹配和標簽提取。其中，抽象概念發(fā)現(xiàn)階段主要是通過奇異值分解獲得文檔集合的潛在語義關(guān)系，LINGO認為詞文檔矩陣A經(jīng)奇異值分解后產(chǎn)生三個矩陣U、S和V即：j = USV.39。.， U的列向量就代表抽象概念。最常用的獲得A的最佳近似矩陣Ak的方法如下式所示：Ml，名 II，乏？其中||y4||，..，是矩陣A的Frobenius范數(shù)，q是一個控制參數(shù)，明顯地g值越大獲得的k值也就越大，最終聚類獲得的類別數(shù)也就越多，默認情況下LINGO取q=0. 775。詞匹配和標簽提取主要解決的問題是類標簽的確定。由于抽象概念和關(guān)鍵詞組都可以在同一個向量空間中描述，因此LINGO使用cosine距離公式來度量抽象概念和關(guān)鍵詞或關(guān)鍵詞組之間的相似度。P表示關(guān)鍵詞關(guān)鍵詞組矩陣，它可以通過將關(guān)鍵詞組看作偽文檔的方式來構(gòu)造，Uk表示抽象概念，因此抽象概念和關(guān)鍵詞、關(guān)鍵詞組的關(guān)系就可以通過下式來表示：M = U/P最后，類標簽提取還要考慮重疊標簽的修剪。構(gòu)造一個詞一文檔矩陣Z，其中類的候選標簽表示一個文檔，執(zhí)行ZZ得到類標簽之間的相似關(guān)系，選擇結(jié)果矩陣每行中超過標簽相似度閾值(Label Similarity Threshold)并且最大者為. 該類的類標簽。本文中所稱的文檔分配，具體是指在一個定義的矩陣Q中，用每一個行向量表示一個類標簽，用C表示文檔的分配矩陣，那么整個文檔分配的具體構(gòu)造過程可以用下面的公式所表示：C=Q39。A在上面的公式中，A是輸入文檔的詞文檔矩陣，結(jié)果矩陣中的元素Cij表示第j個文檔屬于第i個類別的程度，定義一個文檔分配域值ASSIGNMENT—THRESHOLD，當CijASSIGNMENT—THRESHOLD時將第j個文檔分配到第i個類，最后將沒有被分配的文檔分配到Other類，默認情況ASSIGNMENT—THRESH0LD=0. 225。 LINGO聚類算法最終要形成最終聚類，聚類的結(jié)果的作用是將經(jīng)過處理后類權(quán)重排序后返回給用戶，下面的公式是根據(jù)LINGO算法采用的類權(quán)重計算方法：C/ote/ = labelscore x ||C||其中Ctote/ =7^^amp。/^^076乂||6|是分配到類別C的文檔數(shù)。 LINGO聚類算法的優(yōu)缺點作為搜索引擎技術(shù)中眾多優(yōu)秀算法的一種，LIGNO聚類算法經(jīng)過長期的發(fā)展和演變，不斷的將技術(shù)應用中存在的問題和缺陷進行修補和完善，發(fā)展至今，LINGO聚類算法已經(jīng)成為比較成熟、易用性強、對不同的系統(tǒng)適應程度高的一個比較好的優(yōu)選算法，本文對LINGO聚類算法的介紹，還停留在技術(shù)應用的表面，LINGO聚類算法的優(yōu)點還有很多，特別是在系統(tǒng)的應用中，和對搜索引擎技術(shù)的發(fā)展方面，還有很多值得肯定的方面，下面簡單對LINGO聚類算法的優(yōu)點總結(jié)如下：首先，LINGO聚類算法能夠為聚類結(jié)果創(chuàng)建有意義的類標題。通過類標題的使用，能夠大大提高算法的準確度和處理速度，對快速得到結(jié)果，并準確的優(yōu)選出最佳結(jié)果具有重要的意義。其次，LINGO聚類算法可以通過利用奇異值分解的方法獲取取文檔集合的抽象概念，該標簽能夠最大限度的反映出不同類別中的文檔的語義信息，通過準確的聚類，實現(xiàn)在LINGO聚類算法的運用下的模糊聚類（即一個文檔能夠同時出現(xiàn)在多個相關(guān)的類別中）。同時，我們也應該看到，在發(fā)展的過程中，由于系統(tǒng)環(huán)境和實際應用環(huán)境的變遷，LINGO聚類算法的發(fā)展也在繼續(xù)，在計算機網(wǎng)絡技術(shù)快速發(fā)展的今天，作為一種優(yōu)秀的算法，LINGO聚類算法也需要不斷的與時俱進，通過不斷的自我完善和修補獲得更好的用戶體驗，具體而言，目前LINGO聚類算法的發(fā)展中主要存在的最主要的的缺點和不足就是，在LINGO聚類算法中，詞權(quán)重公式采用了傳統(tǒng)的TFIDF，這種情況不能充分的考慮并照顧到不同的詞性因素與位置因素，也正因為如此，LINGO聚類算法中LINGO形成的聚類缺乏層次關(guān)系。這也是我們在本搜索引擎系統(tǒng)的設計中需要重點關(guān)注和克服的問題之一。總體而言，LINGO聚類算法還是優(yōu)點多于缺點的，具體在系統(tǒng)的應用中，還需要我們根據(jù)不同的情況，結(jié)合實際中遇到的問題，對出現(xiàn)的新情況、新問題進行重點解決和集中克服，力爭揚長避短，用好LINGO聚類算法服務我們的“妙搜”系統(tǒng)。 本章小結(jié)在本章中，我們對文本聚類的概念進行了集中的介紹，重點從文本聚類中的重要方法，LINGO聚類算法進行了闡述，并對LINGO聚類算法的全過程，包括運行的計算過程中的每一個步驟進行了詳細的介紹，并對LINGO聚類算法的優(yōu)點和存在的不足進行了分別的描述，通過以上對LINGO聚類算法的全面詳盡的介紹，從理論上論證搜索引擎系統(tǒng)所需要應用的基礎理論，從而將移動環(huán)境下搜索引擎技術(shù)所涉及的相關(guān)原理和技術(shù)理論進行了一個全面的介紹，從下一章開始，我們將對本文中的重點內(nèi)容：“妙搜”移動搜索引擎項目進行闡述和介紹，行文的體例將從“妙搜”移動搜索引擎項目的需求分析入手。第4章 妙搜移動搜索引擎系統(tǒng)的需求分析 前文我們用了一定的篇幅對當前實際應用中，移動環(huán)境下搜索引擎技術(shù)的發(fā)展及其相關(guān)基礎技術(shù)和理論進行了介紹，特別是結(jié)合移動互聯(lián)網(wǎng)中搜索引擎技術(shù)的關(guān)鍵性、核心技術(shù)進行了闡述，將包括索引、中文分詞、查詢倒排技術(shù)以及文本聚類等技術(shù)理論進行了分別的敘述，本章重點在前面的基礎上，介紹本文中的重點內(nèi)容：“妙搜”移動搜索引擎項目的系統(tǒng)設計背景、系統(tǒng)所要實現(xiàn)的目標以及系統(tǒng)的具體結(jié)構(gòu)和性能等方面，展開進行深入的分析。 “妙搜”移動搜索引擎項目的研究，主要的背景是目前互聯(lián)網(wǎng)技術(shù)發(fā)展的大背景下，以手機、平板電腦為代表的移動客戶端發(fā)展速度迅猛，成為移動互聯(lián)網(wǎng)發(fā)展的重要硬件依托，而從軟件方面來看，目前移動互聯(lián)網(wǎng)在軟件發(fā)展方面還相對滯后，發(fā)展移動環(huán)境下的互聯(lián)網(wǎng)搜索引擎技術(shù)大有可為，筆者結(jié)合自身的工作實際認識到，在移動環(huán)境下的互聯(lián)網(wǎng)發(fā)展中，進行照搬照抄原有的互聯(lián)網(wǎng)搜索引擎技術(shù)服務是行不通的，因為手機設備用戶對移動環(huán)境下的互聯(lián)網(wǎng)搜索引擎技術(shù)有著差異化的需求，正是這種需求，成為本文開發(fā)“妙搜”移動搜索引擎項目的動力和靈感源泉，本文試圖以“妙搜”移動搜索引擎項目的基礎，在充分借鑒前人理論成果的基礎上，深入發(fā)掘移動環(huán)境下的互聯(lián)網(wǎng)搜索引擎技術(shù)的發(fā)展方向，力求開發(fā)出一整套能夠針對移動互聯(lián)網(wǎng)終端的、適合移動用戶使用的移動環(huán)境下互聯(lián)網(wǎng)搜索引擎服務系統(tǒng)。區(qū)別于傳統(tǒng)的PC端互聯(lián)網(wǎng)技術(shù)，移動環(huán)境下的互聯(lián)網(wǎng)技術(shù)發(fā)展，在當今互聯(lián)網(wǎng)時代信息技術(shù)和計算機技術(shù)飛速發(fā)展的今天，呈現(xiàn)出與以往互聯(lián)網(wǎng)發(fā)展完全不同的新特點，在這樣的基礎上，我們認識到，作為傳統(tǒng)互聯(lián)網(wǎng)服務領(lǐng)域使用最多的搜索引擎服務，目前在國內(nèi)市場上，針對漢語特點和移動環(huán)境下互聯(lián)網(wǎng)發(fā)展規(guī)律的搜索引擎還鳳毛麟角，現(xiàn)有的搜索引擎技術(shù)大多是對PC端的互聯(lián)網(wǎng)搜索引擎技術(shù)進行照搬照抄，完全沒有根據(jù)移動環(huán)境下的互聯(lián)網(wǎng)用戶的特點和需求進行差異化發(fā)展，據(jù)此，筆者在結(jié)合自身工作、學習的基礎上，機會設計在移動環(huán)境下的互聯(lián)網(wǎng)搜索引擎服務系統(tǒng)：“妙搜”移動搜索引擎。這套移動搜索引擎系統(tǒng)的設計中，最大限度的考慮到移動環(huán)境下互聯(lián)網(wǎng)用戶的需求和體驗，是為移動環(huán)境下互聯(lián)網(wǎng)用戶量身訂做的一套互聯(lián)網(wǎng)搜索引擎服務系統(tǒng)。首先