|
Published Articles >> Table of Contents >> Abstract
15th International Conference on Electronics, Communications and Computers (CONIELECOMP'05)
pp. 258-261
Approximate Searching on Compressed Text
Carlos Avendaño Pérez, Instituto Nacional de Astrofísica Óptica y Electrónica
Claudia Feregrino Uribe, Instituto Nacional de Astrofísica Óptica y Electrónica
Gonzalo Navarro, Universidad de Chile
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CONIEL.2005.23
Send link to a friend
| Abstract |
|
The approximate searching problem on compressed
text tries to find all the matches of a pattern in a
compressed text, without decompressing it and
considering that the match of the pattern with the text
can have a limited number of differences. This
problem has diverse applications in information
retrieval, computational biology and signal
processing, among others. One of the best solutions to
this problem is to execute a multipattern search of a set
of pieces of the pattern, followed by a local
decompression and a direct verification in the
decompressed areas. In this work an improvement to
this solution concerning verification is presented,
where instead of executing a decompression process
and searching for the pattern, bit-parallel automata
are constructed that recognize the pattern. In this way,
we perform the entire searching process without
decompressing the text and obtain competitive times,
compared to decompressing text and searching it with
the best existing algorithms.
|
 Additional Information
|
Citation:
Carlos Avendaño Pérez, Claudia Feregrino Uribe, Gonzalo Navarro,
"Approximate Searching on Compressed Text,"
conielecomp,
pp. 258-261,
15th International Conference on Electronics, Communications and Computers (CONIELECOMP'05),
2005
|
|
