Back to results
US 2016/0112062 A1Published application
Parallel dictionary-based compression encoder
AssigneeHuawei Technologies Co., Ltd.
InventorsBarnaby DALTON, Zahra LAK, Manuel SALDANA, Brian MOODY
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.
Claims21
A circuit for encoding an input data stream to generate a compressed output stream, the circuit comprising:
- (a) an input unit to receive an incoming input data stream, the input data stream comprising a sequence of tokens, each token defining a position in the input data stream, a length and a type, the type being a literal token or a copy token, each literal token defining a literal symbol, each copy token having an offset to the position of another token in the sequence of tokens in the input data stream;
- (b) the memory device to store the sequence of tokens of the input data stream at storage locations;
- (c) a parallel processor to encode the tokens using a parallel scan of the input data stream in the memory device to simultaneously process each token of the input data stream while referencing other tokens that precede the position of the respective token in the sequence of tokens of the input data stream, the parallel processor to generate the compressed output stream by eliminating a portion of the tokens of the input data stream based on the results of the parallel scan;
- (d) a plurality of comparators to compare the sequence of tokens from the storage locations in the memory for the parallel scan;
- (e) a memory selector to select, for each copy token, the storage location corresponding to the position of the offset;
- and
- (f) an output unit configured to connect to a recipient device to output the compressed output stream.
4 more elements
A process for encoding comprising:
- (a) receiving input data stream, the input data stream comprising a sequence of tokens, each token defining a position in the input data stream, a length and a type, the type being a literal token or a copy token, each literal token defining a literal symbol, each copy token having an offset to the position of another token in the sequence of tokens in the input data stream;
- (b) encoding the tokens using a parallel scan of the input data stream in the memory device to simultaneously process each token of the input data stream while referencing other tokens that precede the position of the respective token in the sequence of tokens of the input data stream;
- (c) generating a compressed output stream by eliminating a portion of the tokens of the input data stream based on the results of the parallel scan;
- and
- (d) making available the encoded compressed output data as non-transitory computer readable medium or shared memory or transmission.
2 more elements
Dependencies are inferred from the claim text.