| 摘要 |
A lossless data compression system and method compresses a set of M data words stored in a computer memory. A first table stores data representing last occurrence positions among those of the M data words already processed for all distinct word values. A second table stores for each data word an entry indicating the position, if any, of a most recent prior occurrence of another data word with the same word value. A dictionary index indicates how many distinct data word values have beeen encoutered during processing of M data words. The M data words are processed in sequential order. For each data word, it is determined by referencing the first table whether at least one data word with the same word value is located earlier in the M data words. When the data word being processed is unequal to all previously processed data words, a code representing the data word's value is output. Otherwise, the second table is referenced to identify earlier data words that match the current data word's value, and those references are used to identify a longest sequence of earlier data words that match an equal number of data words starting with the current data word. When the longest sequence's length is greater than one data word, a run length code that indicates said longest sequence's length and position is output, and otherwise a distinct code is output. In all cases, after each data word is processed, the first and second tables are updated. |
