Lempel-Ziv compressed structures for document retrieval
A lot of research was done in the field of reducing the space of document retrieval indexes. It is mostly focused on the reduction of the number of required bits per character (bpc). This is around 17--21 bpc, but some representations use only 7 bpc -- if so, there is some additional cost of slowing down query times per retrieved document (at best \(O(\lg^{1+\epsilon} n)\), where \(n\) is the collection size and \(\epsilon > 0\) is a small constant). Currently, there are several reduced-space solutions built on compressed suffix arrays, where the compression is statistical. As an alternative there are the LZ-indexes (Lempel-Ziv 1978, LZ78 compression method). They are faster and have also other advantages. LZ indexes are a novel efficient approach to document search and retrieval. This is related to the fact that LZ78 parses the text into \(n'\) phrases: at most there are \(n\lg_\sigma n\) (\(\sigma\) the size of the alphabet) phrases and in practice this is 1/20--1/6 of \(n\). The authors were able to use the fast and large structures on the sequences of \(n'\) phrases, not of \(n\) symbols, and reduce their size by an order of magnitude, with the same speed. The proposed indexes use \((3-5)nH_l + O(n)\) bits, where \(H_l\) is the \(l\)th-order entropy and in practice this gives 7--10 bpc. The worst case required to retrieve the answer is up to \(O(m \lg^2 n)\) time (\(m\) is the pattern length), and \(O(\lg^3 n)\) for top-\(k\) retrieval. It turned out that each answer was returned in 10--100 microseconds on their computer machine. During the experiments it turned out that the first 75\%--80\% of the answers were retrieved in \(O(1)\) time. The top-\(k\) retrieval index returns approximate answers using \(2nH_l + O(n)\) bits (4--6 bpc). The authors were able to show that their proposed solutions are faster than existing ones needing very short times. The whole paper is divided into 7 sections. Section 2 shows the theoretical background, whereas the next one gives a description of the original LZ78-based pattern-matching index. Section 4 presents the main results obtained, with expansion in Section 5 to a new solution for document listing, and some test in Section 6 related to important details for approximate top-\(k\) document retrieval. The paper ends with a conclusion in Section 7.
- An analysis of the Burrows-Wheeler transform
- Compressed representations of sequences and full-text indexes
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Compression of individual sequences via variable-rate coding
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- Fully functional static and dynamic succinct trees
- General document retrieval in compact space
- scientific article; zbMATH DE number 3887059 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 2119724 (Why is no real title available?)
- Implementing the LZ-index, theory versus practice
- Improved compressed indexes for full-text document retrieval
- Improved range minimum queries
- Improved single-term top-k document retrieval
- Indexing compressed text
- Indexing text using the Ziv--Lempel trie
- Information retrieval. Implementing and evaluating search engines.
- New algorithms on wavelet trees and applications to information retrieval
- New text indexing functionalities of the compressed suffix arrays
- On compressing and indexing repetitive sequences
- On the height of digital trees and related problems
- Representing trees of higher degree
- Space-Efficient Algorithms for Document Retrieval
- Space-efficient data-analysis queries on grids
- Space-Efficient Framework for Top-k String Retrieval Problems
- Space-efficient frameworks for top-k string retrieval
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
- Stronger Lempel-Ziv based compressed text indexing
- Succinct data structures for flexible text retrieval systems
- Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
- Succinct representation of balanced parentheses and static trees
- Succinct Trees in Practice
- Suffix Arrays: A New Method for On-Line String Searches
- Top-\(k\) document retrieval in optimal time and linear space
- Top-\(k\) ranked document search in general text databases
- Inverted file compression through document identifier reassignment.
- Improved compressed indexes for full-text document retrieval
- Unique-order interpolative coding for fast querying and space-efficient indexing in information retrieval systems
- Sensitivity of string compressors and repetitiveness measures
- A linear lower bound on index size for text retrieval
- FLPI: an optimal algorithm for document indexing based on LPI
- Space-Efficient Algorithms for Document Retrieval
- scientific article; zbMATH DE number 1304039 (Why is no real title available?)
This page was built for publication: Lempel-Ziv compressed structures for document retrieval
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272976)
