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

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

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

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

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

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