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

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

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

3、對此缺陷進行改進，即 ABSQ(the inverted index Algorithm based SpanQuery span query)算法。由于SpanQuery跨度查詢匹配的條數(shù)有所限制，所以本文據(jù)此還針對數(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進行對比。
　　實驗結果表明，RRSA和ABSQ比較，在索引文件少文件內容少的情況下，RRSA在運行時間上優(yōu)于ABSQ，而隨著索引文件和文件內容的不斷增大，ABSQ在運行時間上明顯要優(yōu)于RRSA。而ABAS和ABKS兩算法與AB