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

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

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

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

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