Parallel history search and encoding for dictionary-based compression

摘要

Systems, devices and methods for data compression using history search for dictionary based compression. Systems, devices and methods may use parallel processing techniques for data compression and encoding. Systems, devices and methods may provide memory search techniques for hardware.

主权项

1. A circuit for history searching an input data stream to generate a history search output stream, the circuit comprising:
(a) an input unit to receive an incoming input data stream, the input data stream comprising a sequence of symbols; (b) a memory device to store the sequence of symbols of the input data stream at storage locations; (c) a parallel processor to implement a dictionary based history search on the input data stream in the memory device using a parallel sort to generate the history search output data stream of tokens, each token defining a type, the type being a literal token or a copy token, each literal token defining a literal symbol of the sequence of symbols of the input data stream, each copy token having a copy reference pointer identifying a position of one or more copied symbols in the sequence of symbols of the input data stream, the position corresponding to a storage location of the storage locations of the memory device storing the input data stream, the one or more copied symbols having corresponding one or more literal symbols of the literal tokens of the history search output data stream; (d) a comparator to compare the sequence of symbols from the storage locations in the memory to identify the one or more copied symbols and the corresponding one or more literal symbols for the parallel sort; (e) a memory selector to select, for each copy reference pointer, the storage location corresponding to the position identified by the respective copy reference pointer; and (f) an output unit configured to connect to a recipient device to output the history search output stream for compression of the input data stream.