The Commons

Back to Results

Patent Title: Method and system in a data processing system for efficiently compressing data using a sorting network

Assignee: IBM
Patent Number: US5659755
Issue Date: 08-19-1997
Application Number:
File Date:11-20-1995


Abstract: In a data processing system, a block of N bytes is selected, wherein N is greater than one. Thereafter, a group of N data cells is created wherein each cell has a physical tag for indicating a physical order in the group and a substring that includes a sequence of bytes from the block of N bytes. Next, the group of N cells is sorted lexically to establish a lexical order based upon the lexical value of the substring in each of the N cells. Matching strings in the substrings of selected ones of the N cells are identified in the lexically sorted group of N cells. Thereafter, the block of N bytes is encoded utilizing the identified matching strings to produce a compressed data set, wherein the compressed data set is efficiently produced by identifying redundant information in the lexically sorted group of N cells. Such encoding may be accomplished by comparing lexically adjacent cells in the lexically sorted group of N cells to identify matching strings.

Notes:

Link to USPTO

IBM Pledge dated 1/11/2005