SYSTEM AND METHOD FOR DATA COMPRESSION AND STORAGE ALLOWING FAST RETRIEVAL

摘要

The invention relates to the field of data compression, database management systems and more particularly the systems and methods for compressing, storing and retrieval data from the compressed form. The offered data compression method allowing fast retrieval comprises the steps of representing a set of strings as a context-free grammar, encoding the context-free grammar into compressed file, wherein the said context-free grammar is the LM-grammar, which has one or more starting non-terminals and wherein the right-hand side of every production rule of the said context-free grammar is either an empty string, or the leftmost grammar symbol of the right-hand side represents only one non-empty string and for every two alternatives with the same left- hand side and both non-empty right-hand sides, the string represented by the leftmost grammar symbol of the right-hand side of one alternative is not a prefix of the string represented by the leftmost grammar symbol of the right-hand side of the other alternative.