Back to results
US 2016/0112064 A1Published application
Parallel history search and encoding for dictionary-based compression
AssigneeHuawei Technologies Co., Ltd.
InventorsBarnaby DALTON, Zahra LAK, Brian MOODY, Manuel SALDANA
Life of this patent
Estimating the term…
Abstract
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.
Claims23
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.
4 more elements
A process comprising:
- (a) receiving an incoming input data stream, the input data stream comprising a sequence of symbols;
- (b) storing on a memory device the sequence of symbols of the input data stream at storage locations;
- (c) parallel processing the input data stream in the memory device using a parallel sort to generate a history search output data stream of tokens, each token defining a type, the type being either 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) comparing symbols from the storage locations in the memory device to identify the one or more copied symbols and the corresponding one or more literal symbols for the parallel sort;
- (e) selecting, for each copy reference pointer, the storage location corresponding to the position identified by the respective copy reference pointer;
- and
- (f) connecting to a recipient device to output the history search output stream for compression of the input data stream.
4 more elements
Dependencies are inferred from the claim text.