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 that exhibit a sublinear behavior on the average, as shown by extensive experimentation.
Adapting Boyer-Moore-like algorithms for searching Huffman encoded texts
CANTONE, Domenico;FARO, SIMONE;
2012-01-01
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 that exhibit a sublinear behavior on the average, as shown by extensive experimentation.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
2012 CantoneFaroGiaquinta IJFCS.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
Dimensione
272.57 kB
Formato
Adobe PDF
|
272.57 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.