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.
2012
string matching; compression algorithms; Huffman coding; Boyer-Moore algorithm; text processing; information retrieval
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11769/30594
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 2
social impact