Better Filtering with Gapped q-Grams (2003)
Burkhardt,Stefan, Kärkkäinen,Juha
A popular and well-studied class of filters for approximate string matching compares substrings of length $q$, \emph{the $q$-grams}, in the pattern and the text to identify text areas that contain...
Simple Linear Work Suffix Array Construction (2003)
Kärkkäinen,Juha, Sanders,Peter
A suffix array represents the suffixes of a string in sorted order. Being a simpler and more compact alternative to suffix trees, it is an important tool for full text indexing and other string...
Fast Lightweight Suffix Array Construction and Checking (2003)
Burkhardt,Stefan, Kärkkäinen,Juha
We describe an algorithm that, for any $v\in[2,n]$, constructs the suffix array of a string of length $n$ in $\Oh{vn + n \log n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the input (the...
Better Filtering with Gapped q-Grams (2003)
Burkhardt, Stefan, Kärkkäinen, Juha
A popular and well-studied class of filters for approximate string matching compares substrings of length $q$, \emph{the $q$-grams}, in the pattern and the text to identify text areas that contain...
Simple Linear Work Suffix Array Construction (2003)
Kärkkäinen, Juha, Sanders, Peter, Baeten, Jos C.M., Lenstra, Jan Karel, Parrow, Joachim, Woeginger, Gerhard J.
A suffix array represents the suffixes of a string in sorted order. Being a simpler and more compact alternative to suffix trees, it is an important tool for full text indexing and other string...
Fast Lightweight Suffix Array Construction and Checking (2003)
Burkhardt, Stefan, Kärkkäinen, Juha, Baeza-Yates, R., Chávez, E., Crochemore, M.
We describe an algorithm that, for any $v\in[2,n]$, constructs the suffix array of a string of length $n$ in $\Oh{vn + n \log n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the input (the...
Full-Text Indexes in External Memory (2003)
Kärkkäinen, Juha, Rao, S. Srinivasa, Meyer, Ulrich, Sanders, Peter, Sibeyn, Jop
One-Gapped q-Gram Filters for Levenshtein Distance (2002)
Burkhardt,Stefan, Kärkkäinen,Juha
We have recently shown that $q$-gram filters based on gapped $q$-grams instead of the usual contiguous $q$-grams can provide orders of magnitude faster and/or more efficient filtering for the Hamming...
Computing the threshold for q-gram filters (2002)
Kärkkäinen, Juha, Penttonen, Martti, Meineche Schmidt, Erik
A popular and much studied class of filters for approximate string matching is based on finding common $q$-grams, substrings of length $q$, between the pattern and the text. A variation of the basic...
One-Gapped q-Gram Filters for Levenshtein Distance (2002)
Burkhardt, Stefan, Kärkkäinen, Juha, Apostolico, Alberto, Takeda, Masayuki
We have recently shown that $q$-gram filters based on gapped $q$-grams instead of the usual contiguous $q$-grams can provide orders of magnitude faster and/or more efficient filtering for the Hamming...