基于字符信息量法則的串匹配算法研究.pdf_第1頁
已閱讀1頁,還剩50頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

1、字符串匹配問題是文本信息處理領域中的一門非常重要的課題。隨著網(wǎng)絡和信息技術(shù)高速發(fā)展,極度膨脹的信息量,使得對信息處理的性能和效率要求越來越高,在某種程度上,字符串匹配的效率甚至成為了人們準確獲取自己所需信息的瓶頸。
   在科學領域(比如計算機科學、生物學、人口統(tǒng)計學、金融等)、自然界和社會生活中(比如單詞頻率、數(shù)字中首數(shù)字出現(xiàn)的頻率等)很多的現(xiàn)象,被證實內(nèi)在的很多特性都符合冪律分布的規(guī)律。冪律分布利用統(tǒng)計規(guī)律揭示了許多表面上看

2、起來絲毫沒有關聯(lián)的事物之間的關系,而這種關系或稱之為不平衡性。事實上,不平衡性的分布特點可以從另外一個角度幫助大家研究和理解事物本質(zhì)。Zipf定律、Heaps定律、Benford定律等便是研究長尾分布的幾種重要定律。
   本文以zipf定律、Heaps定律、Benford定律為參照,首先研究英文單詞詞表中不同字符所蘊含的內(nèi)在特性,并提出字符表征單詞個數(shù),即字符的信息量的概念,驗證表明字符倒序排名與其信息量的分布也符合冪律分布,

3、并據(jù)此提出字符信息量的法則。更進一步的,本文通過字符的信息量的不平衡性特點用于指導字符串匹配算法問題的研究。并經(jīng)過實驗得出,基于字符信息量的法則可以很快的加速字符串匹配的過程,提高字符串匹配算法的性能,結(jié)合字符信息量的法則,本文提出了基于字符信息量法則的字符串匹配算法的三個變種算法:SMCI-no-sort算法、SMCI-partial-sort、SMCI-all-sort算法。實驗表明字符信息量的法則在字符串匹配問題上,可以加速模式串

4、在文本串中的跳躍過程,從而提高字符串匹配的速度。
   具體來說,本文具有創(chuàng)新的研究成果主要體現(xiàn)在以下幾點:
   1,定義了用字符來表征單詞的概念和字符蘊含的信息量概念,通過實證,得到字符的排名倒數(shù)與字符蘊含的信息量同樣符合冪律分布,進而提出字符信息量法則(Character’s Law)。
   2,提出SMCI-no-sort算法;該算法思想是完全基于字符的倒排索引結(jié)構(gòu)進行字符串的查找,通過字符分布的不平衡

5、性,加速字符查找過程。該算法預處理過程只需建立倒排索引結(jié)構(gòu),而不涉及子串的排序操作,所以預處理時間消耗很低。
   3,提出SMCI-all-sort算法;該算法與SMCI-no-sort算法對應,在預處理階段通過對所有列表進行排序,在搜索時,根據(jù)完全有序的列表,只需要進行二元搜索。
   4,提出SMCI-partial-sort算法;該算法充分利用了字符分布的不平衡性和不同字符所表征單詞的信息量不同,選擇部分列表進行

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論