具有間隙約束的搜索引擎原型系統(tǒng)的研究與實現(xiàn).pdf

1、搜索引擎是為人們能夠快速、準(zhǔn)確地在浩瀚的互聯(lián)網(wǎng)資源中查找自己所需要的信息而誕生的，是Internet和時代飛速發(fā)展的產(chǎn)物。盡管現(xiàn)有的搜索引擎已經(jīng)具備成熟、完善的檢索機制，但其還是在檢索結(jié)果中存在各種各樣的不足，即各種搜索引擎都不支持具有間隙約束的搜索，因此對具有間隙約束的搜索進行研究是非常有實際應(yīng)用意義的。
　　模式匹配問題也稱作串匹配問題，它是計算機科學(xué)領(lǐng)域的基本問題的其中之一，它在眾多領(lǐng)域都有重要的應(yīng)用。而具有間隙約束的模式匹

2、配是模式匹配的一個重要的研究內(nèi)容。多年來研究者們致力于研究多個間隙約束的模式匹配問題，一般可描述為P=p0[min0,max0]p1...[minj-1,maxj-1]pj...[minm-1,maxm-1]pm，這里，minj-1和maxj-1分別指在pj-1和pj之間可以通配的最小和最大間隙，具有多個間隙約束的模式匹配問題在諸多領(lǐng)域具有重要應(yīng)用。據(jù)此，由于前面所述搜索引擎存在的不足，本文結(jié)合倒排索引和跨度查詢(SpanQuery)來

3、對此缺陷進行改進，即 ABSQ(the inverted index Algorithm based SpanQuery span query)算法。由于SpanQuery跨度查詢匹配的條數(shù)有所限制，所以本文據(jù)此還針對數(shù)組和鍵值對兩種不同存儲方式設(shè)計了匹配條數(shù)更多的兩個算法。分別為ABAS(the inverted index Algorithm Based on Array Storage)以及ABKS算法(the inverted

4、index Algorithm Based on Key-value Storage)，此外，還實現(xiàn)了不用索引的算法RRSA(Recently the Right Scan Algorithm)來和ABSQ進行對比。
　　實驗結(jié)果表明，RRSA和ABSQ比較，在索引文件少文件內(nèi)容少的情況下，RRSA在運行時間上優(yōu)于ABSQ，而隨著索引文件和文件內(nèi)容的不斷增大，ABSQ在運行時間上明顯要優(yōu)于RRSA。而ABAS和ABKS兩算法與AB