Practical High-Order Entropy-Compressed Text Self-Indexing

doi:10.1109/TKDE.2021.3114401

Practical High-Order Entropy-Compressed Text Self-Indexing

2023-03-01

3

PRE

AI

Jeffrey Scott Vitter *

DOI：10.1109/TKDE.2021.3114401

原文链接

原文求助

摘要

En 中文

Compressed self-indexes are used widely in string processing applications, such as information retrieval, genome analysis, data mining, and web searching. The index not only indexes the data, but also encodes the data, and it is in compressed form. Moreover, the index and the data it encodes can be operated upon directly, without need to uncompress the entire index, thus saving time while maintaining small storage space. In some applications, such as in genome analysis, existing methods do not exploit the full possibilities of compressed self-indexes, and thus we seek faster and more space-efficient indexes. In this paper, we propose a practical high-order entropy-compressed self-index for efficient pattern matching in a text. We give practical implementations of compressed suffix arrays using a hybrid encoding in the representation of the neighbor function F. We analyze the performance in theory and practice of our recommended indexing method, called GeCSA. We can improve retrieval time further using an iterated version of the neighbor function. Experimental results on the tested data demonstrate that the proposed index GeCSA has good overall advantages in space usage and retrieval time over the state-of-the-art indexing methods, especially on the repetitive data.

Keyword:

Entropy

Arrays

Indexing

Bioinformatics

Pattern matching

Genomics

Encoding

Text indexing

text retrieval

entropy-compressed

compressed data structures

pattern matching

Practical High-Order Entropy-Compressed Text Self-Indexing

摘要

期刊

机构