..畢業設計〔論文題目：基于VSM模型的文本相似性的比較姓名XXXXX學號AAAAA所在學院BBBBB專業班級CCCCC指導教師DDDDD日期摘要在互聯網迅速發展的時代,網絡上的信息數量越來越多,種類也比較紛雜。雖然能在我們查詢相關信息是提供大量選擇,但是靠人工瀏覽的方式在浩瀚的信息庫中找到自己最需要最相關的信息,無疑給用戶帶來了麻煩,而且效率也十分低下。為了解決這一個問題,關于判斷文本相似度的技術應運而生,目前廣泛運用于計算機,電信等行業。本文著重闡述了計算文本相似度的過程中會遇到的難題,以及解決這些難題需要用到的相應算法,最后利用VSM模型進行簡單的設計與運用,完成基于web的相似網頁檢測程序關鍵字：文本相似度；相似網頁檢測；VSM模型ABSTRACTWiththeInternetdevelopingrapidly,therearemoreandmoreInformationontheInternet,andthevarietiesofInformationisbecomingmorecomplex.AlthoughwehaveabiggerchancetousetheInformation,itisverydifficultandinefficientforuserstofindtheInformationwhichtheyaremostneededintheInformationDatabase.Tosolvethisproblem,therelevanttechnologyisinventedandnowwidelyusedinComputerandTelecomfield.Thispassageismainlydemonstratedtheproblemswemaymeetwhenwecalculatethetextsimilarityandtherelevantalgorithmsolvingtheproblemsabove.Intheend,weuseVSMmodeltodesignandcompletetheProject-SimilarWebdetectionBasedOnWebKeyWords：textsimilarity;similarwebdetection;VSMmodel目錄TOC\o"1-4"\h\z\u摘要-1-ABSTRACT-2-目錄-3-第一章緒論-6-1.1選題背景-6-1.2研究意義-6-1.3國內外研究現狀-6-國外文本相似度研究狀況-6-國內文本相似度研究情況-7-1.4開發語言-8-1.5本文的主要工作和論文結構-8-主要工作-8-論文結構-9-第二章系統原理介紹-10-2.1原理概述-10-2.2系統相關知識點簡介-10-向量空間模型-10-中文分詞技術-11-統計方法-12-算法-13-數據降維-16-相似度計算方法-16-2.3系統實現思想-17-第三章系統分析與設計-19-3.1系統需求分析-19-3.2系統功能概述-19-系統流程-19-功能模塊介紹-20-3.3系統性能要求-21-第四章系統實現-22-4.1系統運行環境-22-4.2核心相關代碼分析-22-分詞類的介紹-22-核心代碼解析-23-第五章系統測試-29-5.1文章分詞測試-29-5.2獲取關鍵字測試-29-5.3抓取網頁內容測試-30-5.4計算文本相似度-30-第六章總結與展望-31-6.1總結-31-6.2展望-31-致謝-33-參考文獻-34-附錄Ⅰ中文-35-附錄Ⅱ譯文-39-第一章緒論1.1選題背景隨著internet的迅猛發展,人們的生活越來越離不開網絡。www<worldwideweb>技術以其使用直觀、高效、簡單等優點逐步成為Internet上最為重要的信息發布與交互方式,據美國因特網監制公司Netcraft發布的數據表明,截止20XX2月底,全球互聯網網站數量超過1.6億,達162662053,較前一個月增加了450萬。網頁數量也達到百億級別。1.2研究意義由于WWW的迅猛發展,越來越多的信息可供用戶在網上查詢,但是信息膨脹和豐富的同時,加大了用戶尋求自己最需要信息的負擔,特別是目前用戶對查詢信息提出了新的需求,除了需要高效率,高準確性等要求外,用戶有時需要在互聯網上搜索與一篇文檔〔例如txt文件、word文檔等或一張圖片最相關、最相似的信息,這就給目前的技術提出了新的挑戰,而與文本相似度有關的算法應運而生。同時,我國學術論文抄襲現象頻頻發生,非法復制等文檔侵權問題也比較嚴重。在如今的高校中,學生的論文抄襲、作業抄襲現象更是屢見不鮮。學生日益對自己的作業馬虎了事,隨便抄抄了事。尤其是對于有些枯燥的專業課程通常要進行實驗并撰寫電子實驗報告,這就給不想動手動腦的同學以可乘之機。這種現象長此發展下去,不僅老師不能把握學生專業課程學習的情況,而且學生學習的積極性也會嚴重下降,抄襲的風氣將影響到整個高校的學術氛圍。那么文本進行相似度檢測應用就成了眼下一個現實的需求。1.3國內外研究現狀1.3.1國外文本相似度基本研究狀況目前,國內外有很多學者在研究文本相似度計算問題并且已經有很多文本相似度模型被提出并得到廣泛應用,如字符串相似度,文檔結構相似度以及統計相似度等模型。字符串相似度模型將文檔構成的基本單位視為字符串,通過將一個字符串轉換為另一個字符串的替換、插入和刪除操作次數或最大匹配字符串來計算相似度,如Levenshtein距離和Likelt方法。Nirenberg等也提出了兩種串匹配的方法,即更規范的"切塊+匹配+重組"方法和整句級匹配的方法。這兩種方法所采用的相似度衡量機制都是詞組合法。該系統的相似度計算采用罰分制,兩個句子匹配所得到的總罰分值由句子中每個對應單詞對的比較所得的罰分組合而成。文檔結構相似度模型通過文檔結構上的相似程度來計算文檔的相似度,如：Lambros等提出同時依據句子的表層結構和內容計算相似度的方法。在計算相似度時,系統使用了兩級動態規劃技術,應用動態規劃算法允許在兩個長度不同的句子之間計算語句相似度。統計相似度模型：如GerardSalton和McGill于早期提出的向量空間模型,他的思想是把文檔簡化為以特征項的權重為分量的向量表示,通過詞頻統計與向量降維處理來計算相似度。基于向量的文本相似度計算方法是目前主流的文本相似度計算方法,該方法將要比較相似度的文本根據文本中的詞語將文本映射為n維空間向量,然后通過比較向量間的關系來確定文本間的相似度,其中最常見的方式是計算空間向量間的余弦值,但傳統向量空間模型就利用文本而不是用詞來表示詞語之間的關系。現在研究的主流方向就是基于空間向量模型。除了以上的模型以后還有一些其他方法被提出和發展。如：挪威Agdcr大學的VladimirOleshchuk等人提出基于本體的文本相似度比較方法,將本體論引入了文本相似度計算,它能計算文本的語義相似度。此外還有學者在研究句子間相似度的計算,如哥倫比亞大學的CarbonellJ.等人的最大邊緣相關的MMR方法。1.3.2國內文本相似度研究情況在國內,國內學者盤謙紅、王炬提出利用屬性論計算文本相似度,建立了文本屬性重心剖分模型,通過坐標點與坐標點的距離計算關鍵字與關鍵字的相關性,通過坐標點與單純形的關系計算關鍵詞與文本的相關度。張煥炯、王國勝、鐘義信〔2001提出了基于漢明距離的文本相似度計算,該方法提出了漢明碼的概念。與其他的文本相似度計算公式相比較,因為該方法只是利用模2加等運算,其方便性是不言而喻的,他完全避開了諸如在歐式空間中求相似度的大量乘法運算,因此,可以較大的提高速度。其次,它跳出了傳統的借用空間的理念,而是用碼字的方式來表征文本信息的特征,可以不僅限于關鍵字等孤立的信息,這為聯合的描述文本的信息提供了可能。1.4開發語言JAVA語言。JAVA是一種可以撰寫跨平臺應用軟件的面向對象的程序設計語言,是由SunMicrosystems公司于1995年5月推出的Java程序設計語言和Java平臺〔即JavaEE,JavaME,JavaSE的總稱。Java自面世后就非常流行,發展迅速,對C++語言形成了有力沖擊。Java技術具有卓越的通用性、高效性、平臺移植性和安全性,廣泛應用于個人PC、數據中心、游戲控制臺、科學超級計算機、移動和互聯網,同時擁有全球最大的開發者專業社群。選擇JAVA作為開發語言,一方面是因為自己對這種語言比較熟知,另一方面是因為它的確有著一些優于其他語言的特點：<1>Java是簡單的Java與C++極為相似,但卻簡單得多。高級編程語言的所有特性中,不是絕對需要的都已刪去了。例如,Java沒有算符過載、標題文件、預處理、指針運算、結構、聯合、多維數組、模板及隱式類型變換。<2>Java是編譯型的當運行Java程序時,它首先被編譯成字節代碼。字節代碼非常類似于機器指令,所以Java程序非常高效。然而,字節代碼并不專對一種特定的機器,所以Java程序無需重新編譯便可在眾多不同的計算機上執行。<3>Java是可移植的Java程序是一次編譯,處處運行。所以Java的移植卻很容易,而且不需要進行重新編譯。<4>Java是健全的Java程序不可能造成計算機崩潰。Java系統仔細檢測對內存的每次訪問,確認它是合法的,而且不致引起任何問題。不過,即使Java程序也可能有錯誤。如果出現某種出乎意料之事,程序不會崩潰,而把該例外拋棄。1.5本文的主要工作和論文結構1.5.1主要工作本文先介紹空間向量模型以及中文分詞的相關基本知識,在此基礎上,利用Java語言對某篇TXT文檔進行分詞、詞頻統計、選出關鍵詞、調用Baidu搜索網頁相關內容、下載網頁頁面、網頁去標簽獲取主題內容、計算余弦值得出相似度,通過上述過程完成基于WEB的相似網頁檢測。本文的研究內容體現在以下四個方面：<1>VSM空間向量模型<2>中文分詞策略<3>HTML解析策略<4>計算文本相似度1.5.2論文結構本文共分為六個章節,具體章節內容安排如下：第一章：緒論,介紹了選題背景和研究意義,然后粗略的講述了國內外相關研究情況,最后介紹了本文的研究內容和文章結構。第二章：系統原理介紹,主要介紹了系統需要用到的相關知識點,例如向量空間模型、中文分詞技術、相似度的計算方式、下載網頁內容并進行解析等。第三章：系統分析與設計,主要闡述了基于WEB相似檢測的需求和項目設計的思想和流程。第四章：系統實現,系統的核心代碼和算法抽取出來進行詳細的講解和闡述。第五章：系統測試,抽取一個TXT文件進行測試,查看結果是否符合預期要求。第六章：總結與展望,總結做畢業設計過程的經驗,吸取教訓,展望未來的生活。最后是參考文獻和致謝。第二章系統原理介紹2.1原理概述本系統是基于向量空間模型〔VSM來設計的。我們將一篇文檔都看成一個向量,每個詞作為向量的一個維度,而詞的頻率看成其值〔有向,即向量,這樣每篇文章的詞及其頻率就構成了一個i維空間圖,兩個文檔的相似度就是兩個空間圖的接近程度,即它們之間夾角的大小,我們通過計算余弦系數來體現。計算機不會像人一樣自動識別文檔里的每個詞,所以要對文檔進行分詞處理,然后統計詞頻,最后根據余弦系數計算公式得出相似度比較結果。2.2系統相關知識點簡介2.2.1向量空間模型VSM模型〔VSM：VectorSpaceModel即向量空間模型,由Salton等人于20世紀70年代提出,并成功地應用于著名的SMART文本檢索系統。向量空間模型的基本思想為將文本簡化為特征向量表示,將相似度計算問題簡化為空間向量的運算,由此使得問題的復雜性大大降低。該方法根據文本中的詞語將文本映射為n維空間向量,通過計算空間向量的余弦值來確定文本的相似度,即利用空間的相似性來解決文本上的相似性,直觀易懂。通過向量空間模型,文本數據就轉換成了計算機可以處理的結構化數據,兩個文檔之間的相似性問題轉變成了兩個向量之間的相似性問題。我們可以這樣來理解一下向量空間模型。對于每篇文檔來說,它都是由很多詞條組成的。對此,我們可以對文檔〔Document和其所包含的詞條〔Term之間的關系進行一個研究。我們可以將一篇文檔看成一個向量D〔term1,term2,……,termn。這樣,假設某兩篇文檔中都出現了term1和term2,就可以用一個二維的坐標來表示文檔和詞條之間的關系,如圖2-1所示。從圖中可看出,文檔1中Term1共出現3次,Term2出現1次；而文檔2中Term2出現3次,Term1出現1次。所以,可以用向量D1〔3,1、D2〔1,3來表示這兩篇文檔。以此類推,一個搜索引擎的索引庫,可以看成是一個由詞條組成的N維向量空間。每一篇文檔均為其中的一個向量。在這種情況下,文檔之間就出現了特定的關系。例如,當兩篇文檔內容相近時,它們的詞條也就差不多。因此,從邏輯上看,它們可能就會在這個向量空間中處于一種很"接近"的位置。此時,"接近"真實含義指的是這兩個向量之間的夾角比較小。Term1Term2文檔1文檔2圖2-1文檔和詞條的向量空間Term1Term2文檔1文檔2圖2-1文檔和詞條的向量空間2.2.2中文分詞技術眾所周知,中文是世界上最復雜的語言之一。那么要對文本進行相似度計算,首先就要進行分詞處理。分詞,即將一段文本拆分成多個詞。現有的分詞方式主要有單字分詞、二分法、詞典分詞。單字分詞,顧名思義即在對中文文本進行分詞時,以字為單位進行切分。按這種方式建立索引,則索引中所有的詞條的集合就是中文漢字庫的一個子集合。字索引比較靈活,但需要復雜的單字匹配算法,以及大量的CPU運算。二分法,即將每兩個字當作一個詞語進行切分,然后建立索引。它明顯的減少了每個詞條后位置信息的長度。如Lucene的CJKAnalyzer就是對中文采取二分的方式進行分詞。本系統采用IKAnalyzer分詞器進行分詞,也相當于使用詞典分詞,是目前來講分詞比較準確的一種方法,即通過構造一個常用詞詞典來對遇到的文本進行詞語的切分。中國科學院計算技術所研究的ICTCLAS在中文分詞領域是較為先進的分詞系統,其分詞詞典也是世界公認的精準。使用詞典分詞法在文本中匹配單詞時用到一些常用的算法：正向最大匹配算法：從左到右將待分詞文本中的幾個連續字符與詞庫匹配,如果匹配上,則切分出一個詞。逆向最大匹配算法：從被處理文檔的末端開始匹配掃描,每次取最末端的2i個字符〔i字字串作為匹配字段,若匹配失敗,則去掉匹配字段最前面的一個字,繼續匹配。其采用的分詞詞典是逆序詞典,對文檔進行處理時先要進行倒排處理,生成逆序文檔。有的時候,需多種方式對文本進行切分,當它們切分的結果相同,表示這個詞就是真正需要的詞。2.2.3TF統計方法TF的全稱TermFrequency,也就是詞條頻率。用數學方法來描述即某個詞語出現的次數除以該文檔中的詞條總數。常用于情報檢索與文本挖掘,用以評估一個詞對于一個文檔的重要程度。如今在信息科學領域,比較經典的詞頻統計方法有基于匹配的詞頻統計算法和基于樹結構的詞頻統計算法。對于單關鍵詞匹配算法國內外都有了深入的研究,比較著名的匹配算法有BF<BruteForce>算法、KMP<Knuth-Morris-Pratt>算法、BM<Boyer-Moore>算法等。<1>BF算法BF算法亦稱蠻力算法。其基本思想是：首先S[1]和T[1]比較,若相等,則再比較S[2]和T[2],一直到T[M]為止；若S[1]和T[1]不等,則T向右移動一個字符的位置,再依次進行比較。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],則匹配成功；否則失敗。<2>KMP算法KMP算法是由高德納〔DonaldErvinKnuth和VaughanPratt在1977年合作發明的。其基本思想為：假設在模式匹配的進程中,執行T[i]和W[j]的匹配檢查。若T[i]=W[j],則繼續檢查T[i+1]和W[j+1]是否匹配。若T[i]<>W[j],則分成兩種情況：若j=1,則模式串右移一位,檢查T[i+1]和W[1]是否匹配；若1<j<=m,則模式串右移j-next<j>位,檢查T[i]和W[next<j>]是否匹配。重復此過程直到j=m或i=n結束。<3>BM算法BM算法由BobBoyer和JStrotherMoore在1977年提出,它是一個非常有效的字符串匹配算法。它的基本思想是：假設將主串中自位置i起往左的一個子串與模式進行從右到左的匹配過程中,若發現不匹配,則下次應從主串的i+dist<si>位置開始重新進行新一輪的匹配,其效果相當于把模式和主串向右滑過一段距離distance〔si,即跳過distance〔si個字符而無需進行比較。基于匹配的詞頻統計方法,不可避免的是要對待處理的文檔進行多次掃描。當待處理文檔數據量比較大時,這無疑是要付出更高的時間和空間代價。針對這個問題,有學者又提出了基于樹結構的詞頻統計算法。其基本思想是：首先根據已有的關鍵詞集合構建一棵查找樹,然后利用這個查找樹對文檔進行掃描,從而進行關鍵詞的統計。進行詞頻統計時,非常好的是每當從文檔中讀取一個詞與查找樹比較時,只需對文檔掃描一遍,則可統計出所有關鍵詞的信息。這種方法減少了一些不必要的匹配過程,大大提高了統計效率。2.2.4TF-IDF算法TF-IDF簡介TF-IDF〔termfrequency–inversedocumentfrequency是一種用于資訊檢索與資訊探勘的常用加權技術。TF-IDF是一種統計方法,用以評估一字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現的次數成正比增加,但同時會隨著它在語料庫中出現的頻率成反比下降。TF-IDF加權的各種形式常被搜尋引擎應用,作為文件與用戶查詢之間相關程度的度量或評級。除了TF-IDF以外,因特網上的搜尋引擎還會使用基于連結分析的評級方法,以確定文件在搜尋結果中出現的順序。在一份給定的文件里,詞頻<termfrequency,TF>指的是某一個給定的詞語在該文件中出現的次數。這個數字通常會被歸一化〔分子一般小于分母區別于IDF,以防止它偏向長的文件。〔同一個詞語在長文件里可能會比短文件有更高的詞頻,而不管該詞語重要與否。逆向文件頻率<inversedocumentfrequency,IDF>是一個詞語普遍重要性的度量。某一特定詞語的IDF,可以由總文件數目除以包含該詞語之文件的數目,再將得到的商取對數得到。某一特定文件內的高詞語頻率,以及該詞語在整個文件集合中的低文件頻率,可以產生出高權重的TF-IDF。因此,TF-IDF傾向于過濾掉常見的詞語,保留重要的詞語。TF-IDF主要思想如果某個詞或短語在一篇文章中出現的頻率TF高,并且在其他文章中很少出現,則認為此詞或者短語具有很好的類別區分能力,適合用來分類。TFIDF實際上是：TF*IDF,TF詞頻<TermFrequency>,IDF反文檔頻率<InverseDocumentFrequency>。TF表示詞條在文檔d中出現的頻率〔另一說：TF詞頻<TermFrequency>指的是某一個給定的詞語在該文件中出現的次數。IDF的主要思想是：如果包含詞條t的文檔越少,也就是n越小,IDF越大,則說明詞條t具有很好的類別區分能力。如果某一類文檔C中包含詞條t的文檔數為m,而其它類包含t的文檔總數為k,顯然所有包含t的文檔數n=m+k,當m大的時候,n也大,按照IDF公式得到的IDF的值會小,就說明該詞條t類別區分能力不強。〔另一說：IDF反文檔頻率<InverseDocumentFrequency>是指果包含詞條的文檔越少,IDF越大,則說明詞條具有很好的類別區分能力。但是實際上,如果一個詞條在一個類的文檔中頻繁出現,則說明該詞條能夠很好代表這個類的文本的特征,這樣的詞條應該給它們賦予較高的權重,并選來作為該類文本的特征詞以區別與其它類文檔。這就是IDF的不足之處.在一份給定的文件里,詞頻〔termfrequency,TF指的是某一個給定的詞語在該文件中出現的頻率。這個數字是對詞數<termcount>的歸一化,以防止它偏向長的文件。〔同一個詞語在長文件里可能會比短文件有更高的詞數,而不管該詞語重要與否。對于在某一特定文件里的詞語來說,它的重要性可表示為：以上式子中是該詞在文件中的出現次數,而分母則是在文件中所有字詞的出現次數之和。逆向文件頻率〔inversedocumentfrequency,IDF是一個詞語普遍重要性的度量。某一特定詞語的IDF,可以由總文件數目除以包含該詞語之文件的數目,再將得到的商取對數得到：其中|D|：語料庫中的文件總數：包含詞語的文件數目〔即的文件數目如果該詞語不在語料庫中,就會導致被除數為零,因此一般情況下使用然后某一特定文件內的高詞語頻率,以及該詞語在整個文件集合中的低文件頻率,可以產生出高權重的TF-IDF。因此,TF-IDF傾向于過濾掉常見的詞語,保留重要的詞語。TF-IDF算法示例有很多不同的數學公式可以用來計算TF-IDF。這邊的例子以上述的數學公式來計算。詞頻<TF>是一詞語出現的次數除以該文件的總詞語數。假如一篇文件的總詞語數是100個,而詞語"母牛"出現了3次,那么"母牛"一詞在該文件中的詞頻就是3/100=0.03。一個計算文件頻率<DF>的方法是測定有多少份文件出現過"母牛"一詞,然后除以文件集里包含的文件總數。所以,如果"母牛"一詞在1,000份文件出現過,而文件總數是10,000,000份的話,其逆向文件頻率就是log<10,000,000/1,000>=4。最后的TF-IDF的分數為0.03*4=0.12。根據關鍵字k1,k2,k3進行搜索結果的相關性就變成TF1*IDF1+TF2*IDF2+TF3*IDF3。比如document1的term總量為1000,k1,k2,k3在document1出現的次數是100,200,50。包含了k1,k2,k3的docuement總量分別是1000,10000,5000。documentset的總量為10000。TF1=100/1000=0.1TF2=200/1000=0.2TF3=50/1000=0.05IDF1=log<10000/1000>=log<10>=2.3IDF2=log<10000/100000>=log<1>=0；IDF3=log<10000/5000>=log<2>=0.69這樣關鍵字k1,k2,k3與docuement1的相關性=0.1*2.3+0.2*0+0.05*0.69=0.2645其中k1比k3的比重在document1要大,k2的比重是0.在某個一共有一千詞的網頁中"原子能"、"的"和"應用"分別出現了2次、35次和5次,那么它們的詞頻就分別是0.002、0.035和0.005。我們將這三個數相加,其和0.042就是相應網頁和查詢"原子能的應用"相關性的一個簡單的度量。概括地講,如果一個查詢包含關鍵詞w1,w2,...,wN,它們在一篇特定網頁中的詞頻分別是:TF1,TF2,...,TFN。〔TF:termfrequency>。那么,這個查詢和該網頁的相關性就是:TF1+TF2+...+TFN。TF-IDF算法深度剖析在上面的例子中,詞"的"站了總詞頻的80%以上,而它對確定網頁的主題幾乎沒有用。我們稱這種詞叫"應刪除詞"〔Stopwords>,也就是說在度量相關性是不應考慮它們的頻率。在漢語中,應刪除詞還有"是"、"和"、"中"、"地"、"得"等等幾十個。忽略這些應刪除詞后,上述網頁的相似度就變成了0.007,其中"原子能"貢獻了0.002,"應用"貢獻了0.005。細心的讀者可能還會發現另一個小的漏洞。在漢語中,"應用"是個很通用的詞,而"原子能"是個很專業的詞,后者在相關性排名中比前者重要。因此我們需要給漢語中的每一個詞給一個權重,這個權重的設定必須滿足下面兩個條件：<1>一個詞預測主題能力越強,權重就越大,反之,權重就越小。我們在網頁中看到"原子能"這個詞,或多或少地能了解網頁的主題。我們看到"應用"一次,對主題基本上還是一無所知。因此,"原子能"的權重就應該比應用大。<2>應刪除詞的權重應該是零。我們很容易發現,如果一個關鍵詞只在很少的網頁中出現,我們通過它就容易鎖定搜索目標,它的權重也就應該大。反之如果一個詞在大量網頁中出現,我們看到它仍然不很清楚要找什么內容,因此它應該小。概括地講,假定一個關鍵詞w在Dw個網頁中出現過,那么Dw越大,w的權重越小,反之亦然。在信息檢索中,使用最多的權重是"逆文本頻率指數"〔Inversedocumentfrequency縮寫為IDF,它的公式為log〔D/Dw其中D是全部網頁數。比如,我們假定中文網頁數是D＝10億,應刪除詞"的"在所有的網頁中都出現,即Dw＝10億,那么它的IDF＝log<10億/10億=log<1>=0。假如專用詞"原子能"在兩百萬個網頁中出現,即Dw＝100萬,則它的權重IDF＝log<500>=6.2。又假定通用詞"應用",出現在五億個網頁中,它的權重IDF=log<2>則只有0.7。也就只說,在網頁中找到一個"原子能"的比配相當于找到九個"應用"的匹配。利用IDF,上述相關性計算個公式就由詞頻的簡單求和變成了加權求和,即TF1*IDF1+TF2*IDF2+...+TFN*IDFN。在上面的例子中,該網頁和"原子能的應用"的相關性為0.0161,其中"原子能"貢獻了0.0126,而"應用"只貢獻了0.0035。這個比例和我們的直覺比較一致了。2.2.5數據降維數據降維,是詞頻統計中所要考慮的一個因素。當文檔中的詞條數目很多,即向量的維度較高,那么為了提高效率,我們需要降低維度,即去除一些無關緊要的詞語,減少詞語的數量。而且采取降維的策略在一定程度上,還可以提高精度。文本特征向量降維主要有如下的兩類：<1>特征選擇：是指代去除那些不能表示信息或者表示的信息量很小的詞<從廣義上說：不存在不能表示信息或者意義的詞,否則它就沒有了存在的必要,自然這個詞就無法存在>,以提高文本相似度計算的效率并且減少復雜度,基本上可以被分為如下幾種方法：①根據單詞的IDF值來進行判斷：當單詞的IDF值小于一個閾值或者大于另一個閾值的時候都要去除；②根據單詞的文本頻度TF值來判斷：當單詞的TF值小于或者大于某個給定的闕值也要去除；③根據X2統計量進行判斷：其值越大,單詞與文本之間的獨立性越小,相關性越大,所以要去除X2小的詞；·④根據互信息MI來進行判斷：<MI>越大,兩個單詞之問的關系就越強。其中第一種方法效果較好。<2>特征重構：是通過合并或轉化特征項來構造新的特征項,以達到降維的目的,一些文獻中使用的奇異值分解方法就是這種思想的一種實現。2.2.6相似度計算方法基于向量空間模型,我們將兩篇文檔理解為兩個向量,將它們之間的相似度理解為這兩個向量在空間上的接近程度,即它們之間的夾角。我們通過計算余弦系數來比較兩篇文章的相似度,余弦系數計算方法為,向量內積/各個向量的模的乘積,如圖2-2所示。圖2-2兩個向量余弦值的計算其中,、分別為待比較的兩個文本的特征向量,、分別為向量的第i維,n為特征向量的維數。余弦計算的好處是其值正好是一個介于0到1的數,如果向量一致就是1,如果正交就是0,符合相似度百分比的特性。為了讓過程更加的簡潔明了,下面舉例說明：假設共有十個詞：W1,W2,,W10,而共有三篇文章,d1,d2,d3。統計出文章的詞頻表,如圖2-3所示。文檔W1W2W3W4W5W6W7W8W9W10d112579d23468d3101112131415圖2-3詞頻表的統計結果假設計算d1和d2的文本相似度,根據圖2-2公式可得結論,如圖2-4所示。圖2-4向量余弦值的示例計算2.3系統實現思想我們將兩篇文檔當作兩個向量,通過計算相似度來宏觀的表現它們的接近程度。本系統主要按如下的思路進行：根據2.2節相關技術的介紹,本系統采用向量空間模型,主要流程可以細分為如下模塊進行,分詞處理,詞頻統計,選擇關鍵字調用百度搜索查詢,下載網頁并解析,相似度計算。注釋：分詞處理主要利用IKAnalyzer分詞器〔下面統一簡稱為IK分詞器IKAnalyzer是一個開源的,基于java語言開發的輕量級的中文分詞工具包。從20XX12月推出1.0版開始,IKAnalyzer已經推出了4個大版本。最初,它是以開源項目Luence為應用主體的,結合詞典分詞和文法分析算法的中文分詞組件。從3.0版本開始,IK發展為面向Java的公用分詞組件,獨立于Lucene項目,同時提供了對Lucene的默認優化實現。在2012版本中,IK實現了簡單的分詞歧義排除算法,標志著IK分詞器從單純的詞典分詞向模擬語義分詞衍化。其相關特性如下：<1>采用了特有的"正向迭代最細粒度切分算法",具有60萬字/秒的高速處理能力。<2>采用了多子處理器分析模式,支持：英文字母〔IP地址、Email、URL、數字〔日期,常用中文數量詞,羅馬數字,科學計數法,中文詞匯〔姓名、地名處理等分詞處理。對中英聯合支持不是很好,在這方面的處理比較麻煩.需再做一次查詢,同時是支持個人詞條的<3>優化的詞典存儲,更小的內存占用。支持用戶詞典擴展定義<4>針對Lucene全文檢索優化的查詢分析器IKQueryParser；采用歧義分析算法優化查詢關鍵字的搜索排列組合,能極大的提高Lucene檢索的命中率。第三章系統分析與設計3.1系統需求分析隨著計算機的普及和網絡的飛速發展,互聯網上以及各種電子文檔的數量以空前的速度增長,人們獲取知識的途徑也發生了深刻的變化。面對如此巨大的知識海洋,如何快速查找相關信息變得非常重要。如果沒有有效的組織和提取方式,普通用戶查找自己想要的信息所用的時間可能比了解信息本身所花費的時間還長,這是人們無法容忍的。文本相似度是表示兩個或多個文本之間匹配程度的一個度量參數,相似度大,說明文本相似程度高,反之文本相似度低。對于文本聚類、信息檢索、問答系統、網頁去重、文本分類等很多領域,文本相似度的有效計算問題是其進行信息處理的關鍵。論文抄襲是一種嚴重的造假行為。當前出現的各種學術造假、論文抄襲現象,已嚴重的影響到整個高校的學術氛圍。大學是一個要求學生獨立自主學習的地方,而現在越來越多的學生放慢自己的行為,對老師布置的作業抄抄了事。這樣老師既不能對學生的學習情況得到一個真實的掌握,學生學習的積極性也慢慢下降。這牽涉到的是一個誠信問題。誠信是社會道德的一道防線,也是大學生誠信責任的一道防線。現在這道防線岌岌可危,我們應采取積極地措施加以保護。本課題就在網上搜索與已經存在的TXT文件相似的內容做了一個系統設計。系統一方面在理論方面進行了一定的探究,了解了文檔相似度相關方面的知識,另一方面在實際的應用上也有一定的價值。本系統只是簡單實現了基本功能,有些地方還需進一步完善優化,用戶可用此系統較為方便的搜索與自己已有文檔相似的網頁內容,老師也可以將此作為檢查學生抄襲情況的工具,盡量減少學生抄襲的念頭。3.2系統功能概述3.2.1系統流程首先,用戶選擇一個要查詢的TXT文件,確定TXT文件所在的文件夾,然后是進行文檔分詞,統計詞頻,得到一個HashMap；排序后,選擇所需數量的關鍵詞后調用Baidu搜索相關的網頁并下載；整理并去掉網頁標簽得到純文本內容,提取內容存入到電腦；最后計算得到兩篇文章的相似度。比較各個網頁與原TXT文件的相似度,相似度越接近1則表示越相近；相似度越接近0則表示內容越來越不匹配。3.2.2功能模塊介紹本課題設計的基于WEB的相似網頁檢測主要是進行一個理論的研究,可以搜索與TXT文件相似的網頁內容,每一次檢測的對象都是放在同一文件夾下,然后對文檔進行相似度的檢測。另外,本系統對圖片、表格等是不進行識別和檢測的。根據實際的需求,基于WEB的相似網頁檢測可以分成四個功能模塊,如圖3-1所示。基于WEB的相似網頁檢測基于WEB的相似網頁檢測分詞統計模塊調用Baidu查詢模塊下載網頁解析模塊計算文本相似度模塊圖3-1系統模塊圖各模塊實現的功能如下：<2>分詞統計模塊此模塊實現文本分詞,并對分詞進行統計。選擇TXT文件所在的文件夾,讀取文件內容存為字符串,利用IK分詞器將字符串〔也就是文本內容進行分詞,并且統計分詞出現的次數,最后計算詞頻。<3>調用Baidu查詢模塊此模塊實現調用Baidu對關鍵詞進行網絡查詢。其中百度的查詢代碼是[此處為搜索的詞語]&tn=monline_4_dg"抽取搜索的網頁中的百度鏈接所用的方法是使用正則表達式://baidu/link\\?url=\\w+<\\S+>?\"<4>下載網頁進行解析模塊此模塊對下載的模塊進行解析。下載下來的內容為HTML語言,而我們只需要的是里面的文字內容,標簽以及標簽中的嵌套都不是我們所需。得到的純文本內容寫入文件。<5>文本相似度計算模塊此模塊實現對向量的計算,得出文本相似度。文件通過上述過程都轉換成了計算機可以計算的向量空間,調用計算向量的函數得到一個介于0~1的結果。通過結果可以判定兩個文本的相似程度。3.3系統性能要求<1>系統設計的合理性在設計系統時要考慮實際的系統性能和硬件要求,不能忽視所處環境,也不能一味地追求新的設計方法,要保證系統實現的合理性。<2>系統的簡單易用性本系統側重于對相似度檢測進行一個理論的研究,所以并不需要過于美觀、應用的界面,作為用戶最終需要的只是兩篇文檔的相似度比較結果。因此設計時本著"簡單易用"的原則,方便用戶操作。<3>系統的可靠性要比較的兩篇文檔,可能是數據量很大的文本,就要考慮到系統運行的效率,采取相應的算法加以優化,盡可能的保證系統高性能有效的運行。第四章系統實現4.1系統運行環境1、硬件環境：處理器：InterCore或更高內存：2GB2、軟件環境：操作系統：WindowsXP或者Windows7語言開發工具：Eclipse4.2核心相關代碼分析4.2.1分詞類的介紹<1>類org.wltea.analyzer.core.IKSegmenter：說明：這是IK分詞器的核心類。它是獨立于Lucene的Java分詞器實現。當需要在Lucene以外的環境中單獨使用IK中文分詞組件時,可以使用IKSegmenter。publicIKSegmenter<Readerinput,booleanuseSmart>說明：IK主分詞器構造函數參數1：Readerinput,字符輸入讀取參數2：booleanuseSmart,是否采用智能切分策略。true使用智能切分,false使用最細粒度切分。publicIKSegmentation<Readerinput,Configurationcfg>說明：IK主分詞器新構造函數參數1：Readerinput,字符輸入讀取參數2：Configurationcfg,分詞器配置。用戶可以定制自己的Configuration類,來改變詞典配置。publicsynchronizedLexemenext<>throwsIOException說明：讀取分詞器切分出的下一個語義單元,如果返回值為null,表示分詞器已經結束。返回值：Lexeme語義單元對象,即相當于Lucene的詞元對象Token說明：這是IK分詞器的語義單元對象,相當于Lucene中的Token詞元對象。由于IK被設計為獨立于Lucene的Java分詞器實現,因此它需要Lexeme來代表分詞的結果。publicintgetBeginPosition<>說明：獲取語義單元的起始字符在文本中的位置返回值：int,語義單元相對于文本的絕對起始位置publicintgetEndPosition<>說明：獲取語義單元的結束字符的下一個位置返回值：int,語義單元相對于文本的絕對終止位置的下一個字符位置publicintgetLength<>說明：獲取語義單元包含字符串的長度返回值：int,語義單元長度=getEndPosition–getBeginPositionpublicStringgetLexemeText<>說明：獲取語義單元包含字符串內容返回值：String,語義單元的實際內容,即分詞的結果4.2.2核心代碼解析privatestaticMap<String,Integer>segString<Stringcontent>{//分詞Readerinput=newStringReader<content>;//智能分詞關閉〔對分詞的精度影響很大IKSegmenteriks=newIKSegmenter<input,true>;Lexemelexeme=null;Map<String,Integer>words=newHashMap<String,Integer><>;try{while<<lexeme=iks.next<>>!=null>{if<words.containsKey<lexeme.getLexemeText<>>>{words.put<lexeme.getLexemeText<>,words.get<lexeme.getLexemeText<>>+1>;}else{words.put<lexeme.getLexemeText<>,1>;}}}catch<IOExceptione>{e.printStackTrace<>;}returnwords;}該函數主要實現分詞功能,參數是讀取TXT文件后存入變量中的字符串。利用IK分詞器循環對字符串進行分詞,得到的分詞存入到HashMap中。其中HashMap鍵值對中key指的是分詞,value是該分詞在字符串中出現的次數。privatestaticHashMap<String,Double>tf<Map<String,Integer>segWordsResult>{HashMap<String,Double>tf=newHashMap<String,Double><>;if<segWordsResult==null||segWordsResult.size<>==0>{returntf; }Doublesize=Double.valueOf<segWordsResult.size<>>;Set<String>keys=segWordsResult.keySet<>;for<Stringkey:keys>{ Integervalue=segWordsResult.get<key>; tf.put<key,Double.valueOf<value>/size>;}returntf;}該函數實現詞頻的統計。參數為通過分詞函數得到的〔分詞,出現次數鍵值對的HashMap。而詞頻的計算方式為該詞出現次數/總次數,即是Double.valueOf<value>/size。publicstaticMap<String,Map<String,Double>>allTf<Stringdir>{try{ ReadFile.fileList=ReadFile.readDirs<dir>;for<StringfilePath:ReadFile.fileList>{ Stringcontent=ReadFile.readFile<filePath>; Map<String,Integer>segs=segString<content>;allSegsMap.put<filePath,segs>;allTfMap.put<filePath,tf<segs>>; } }catch<FileNotFoundExceptionffe>{ ffe.printStackTrace<>; }catch<IOExceptionio>{ io.printStackTrace<>; }returnallTfMap;}該函數實現對一個文件夾下所有的TXT文件進行詞頻的統計。該函數的參數是一個文件夾路徑名〔注意并非文件名,遍歷讀取文件夾下面的文件內容后用上面所說的segString函數對文件內容進行分詞然后存儲到Map中。返回值是一個嵌套的Map,Map<String,Map<String,Double>>中的前一個String代表文件路徑名,后一個Map中的String代表一個分詞,Double即是詞頻。publicstaticMap<String,Integer>getMostFrequentWords<intnum,Map<String,Integer>words>{ Map<String,Integer>keywords=newLinkedHashMap<String,Integer><>;intcount=0; //詞頻統計 List<Map.Entry<String,Integer>>info=newArrayList<Map.Entry<String,Integer>><words.entrySet<>>; Collections.sort<info,newComparator<Map.Entry<String,Integer>><>{publicintcompare<Map.Entry<String,Integer>obj1,Map.Entry<String,Integer>obj2>{returnobj2.getValue<>-obj1.getValue<>; } }>; //高頻詞輸出for<intj=0;j<info.size<>;j++>{ //詞-->頻if<info.get<j>.getKey<>.length<>>1>{if<num>count>{ keywords.put<info.get<j>.getKey<>,info.get<j>.getValue<>>; count++; }else{break; } } }returnkeywords; }該函數實現功能是獲取最高詞頻的分詞,其中需要的最高詞頻的分詞個數可以自己選擇。其中排序算法用到了Java集合中的Collections.sort方法對list排序的方法。其中一種是list中的對象實現Comparable接口,另一種是根據Collections.sort重載方法來實現,本文采取后一種方式排序。值得注意的是后一種方式需要實現comparator接口中的compare方法。publicStringparse<Stringhtml>{ StringBuildersb=newStringBuilder<>;intstatus=0;//0-->notstart1-->startedfor<inti=0;i<html.length<>;i++>{charch=html.charAt<i>;if<status==0>{if<ch=='<'>{if<html.startsWith<"script",i+1> ||html.startsWith<"SCRIPT",i+1>> status=2;elseif<html.startsWith<"style",i+1> ||html.startsWith<"STYLE",i+1>>{ status=3; }else{ status=1; } }elseif<ch=='&'>{ //finda';'within5charsintk=1;for<k=1;k<5;k++>{if<html.charAt<i+k>==';'>break; }if<k<5> i+=k;else{ sb.append<ch>; } }elseif<ch==''||ch=='\r'||ch=='\n'||ch=='\t'>{ }else{ sb.append<ch>; } }else{if<ch=='>'>{if<status==1>{ status=0; }elseif<status==2>{if<html.startsWith<"/script",i-"/script".length<>> ||html.startsWith<"/SCRIPT", i-"/SCRIPT".length<>>>{ status=0; } }elseif<status==3>{if<html.startsWith<"/style",i-"/style".length<>> ||html.startsWith<"/STYLE", i-"/STYLE".length<>>>{ status=0; } } } } }returnsb.toString<>; }此函數主要實現了HTML去掉標簽的功能,為了得到我們需要的網頁內容,我們需要對下載的HTML代碼進行去標簽處理。去除腳本語言<script>和</script>以及樣式<style>和</style>間的內容。第五章系統測試5.1文章分詞測試選擇需要進行分詞的文件,我選擇的測試文件為D:\\text\\LOLtEXT,測試結果如圖5-1所示。圖5-1文章分詞測試結果結果顯示了D:\\text\\LOLtEXT文件夾下的"新建文本文檔.txt"文件的分詞結果,以及詞頻tf的統計。由于分詞比較多,上圖只是部分截圖。5.2獲取關鍵字測試通過以上分詞以及結果統計后,我們得到了文章的所有分詞,此時我們需要抽取