The Prague Stringology Conference 2009
Domenico Cantone, Simone Faro and Emanuele Giaquinta
Adapting Boyer-Moore-Like Algorithms for Searching Huffman Encoded Texts
| Abstract: |
| In this paper we propose an efficient approach to the compressed string matching problem on Huffman encoded texts, based on the Boyer-Moore strategy. Once a candidate valid shift has been located, a subsequent verification phase checks whether the shift is codeword aligned by taking advantage of the skeleton tree data structure. Our approach leads to algorithms with a sublinear behavior on the average, as shown by extensive experimentation. |
| Download paper: |  |
 |
 |
| PostScript | BibTeX reference |
| Download presentation: |  |