Compressed Index for Approximate String Matching : From Theory to Practice

空間壓縮下搜尋近似字串的索引 : 從理論到實作

吳柏儒(Bor-Ru Wu)

指導教授 ： 韓永楷

國立清華大學/電機資訊學院/資訊工程學系/碩士(2009年)

https://doi.org/10.6843/NTHU.2009.00658

摘要

Abstract
Let T be a text string of length n and P be a pattern string of length
m, such that the characters in both strings are chosen from a fixed finite
alphabet A. The k-difference approximate matching problem is to find the
occurrences of P in T that have edit distance at most k from P. In this
thesis, we propose an index for T such that for any given P we can report
the desired occurrences in the above problem efficiently. Our index is based
on suffix array and inverse suffix array, which is further combined with a
technique called suffix sampling for reducing index space. The space complexity
of the index is O(n log |A|) bits, while reporting the occurrence can
be done in O(|A|mlog2 n + occ log n) time; here, occ denotes the number
of occurrences reported. In addition, we compare this index empirically
with two other existing indexes for their practical performances. Our results
demonstrated that our index is the best choice under many different
situations.

關鍵字

字尾陣列 ； 反向字尾陣列 ； 近似字串比對

並列摘要

中文摘要
假定我們有一個長度為n的文字字串T, 以及長度為m的比對字串P, 兩者的字元皆是由
一固定的字元範圍A中選出。在k-difference approximate matching 的問題裡, 我們
希望能找出P在T中出現的位置, 而且它的edit distance 最多為k。也就是說, 我們找
出在T中, 與P的edit distance 小於k 的地方。在這篇論文當中, 我們提出了一個新
的索引方法, 使得我們對於任何的字串T以及P, 都能有效率的解決上述的問題。我們
的索引方法是建立於suffix array 以及inverse suffix array 的基礎觀念, 再結合了一
個suffix sampling 的新技巧, 達到壓縮空間的效果。這個索引方法使用的空間複雜度
為O(n log |A|) bits, 時間複雜度為O(|A|mlog n+occ log n), 其中occ指的是P在T中
出現的次數。除此之外, 我們將前人提出過的兩種索引方法, 與我們的索引方法進行比
較, 看看實際上的表現會是如何。而實驗的結果發現, 在許多不同的情形之下, 我們的索
引方法會是最好的選擇。

並列關鍵字

approximate string matching ； inverse suffix array ； suffix array

參考文獻

and M. Rodeh. Text Indexing and Dictionary Matching With One

Searching Over Tree Cross Products. In Proceedings of European Symposium

Burrows-Wheeler Transform: Linking Range Searching and Text Indexing.

In Proceedings of Data Compression Conference, pages 252–

[5] A. L. Cobbs. Fast Approximate Matching Using Suffix Trees. In