基于字符信息量法則的串匹配算法研究.pdf

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算法;該算法充分利用了字符分布的不平衡性和不同字符所表征單詞的信息量不同,選擇部分列表進行