In this paper, we investigate a text sparsification technique based on the identification of local maxima. In particular, we first show that looking for an order of the alphabet symbols that minimizes the number of local maxima in a given string is an Np-hard problem. Successively, we describe how the local maxima sparsification technique can be used to filter the access to unstructured texts. Finally, we experimentally show that this approach can be successfully used in order to create a space efficient index for searching a DNA sequence as quickly as a full index.
TEXT SPARSIFICATION VIA LOCAL MAXIMA / P. CRESCENZI; A. DEL LUNGO; R. GROSSI; E. LODI; L. PAGLI; G. ROSSI. - STAMPA. - (2000), pp. 290-301. (Intervento presentato al convegno TWENTIETH CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE) [10.1007/3-540-44450-5_23].
TEXT SPARSIFICATION VIA LOCAL MAXIMA
CRESCENZI, PIERLUIGI;
2000
Abstract
In this paper, we investigate a text sparsification technique based on the identification of local maxima. In particular, we first show that looking for an order of the alphabet symbols that minimizes the number of local maxima in a given string is an Np-hard problem. Successively, we describe how the local maxima sparsification technique can be used to filter the access to unstructured texts. Finally, we experimentally show that this approach can be successfully used in order to create a space efficient index for searching a DNA sequence as quickly as a full index.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
