Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1997-11-14
2001-03-06
Homere, Jean R. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06199064
ABSTRACT:
RELATED APPLICATIONS
This application is a Continuation-in-Part which claims priority to Austrian patent application serial number AT 2001/96, entitled “Sortierverfahren und System zur Datenkompression” and filed on Nov. 15, 1996 by Dipl-Ing. Michael Schindler and to a PCT application entitled “Computer Sorting System for Data Compression” and filed on Nov. 14, 1997 by Dipl-Ing. Michael Schindler, the teachings of which are both incorporated herein by reference in their entirety.
BACKGROUND
Data compression is state of the art in permanent data storage (e.g. fixed disk, tape, diskette) as well as in data transfer (e.g. using a modem). There are well known methods for this, implemented either in software (e.g. as part of an operating system) or in hardware (e.g. chips in magnetic tape and data transfer devices). Although data can be sequentially compressed as a data stream, the better data compression methods require searching or sorting which complicates implementation in hardware and which makes the processing time indeterminate in software.
One example of a sorting method is the Burrows-Wheeler Transform (BWT) which processes a block of data as a single unit. A reversible transformation is applied to a block of text to form a new block having the same characters. This transformation tends to group like characters together so as to improve the probability of finding a character close to another instance of the same character. This sorted text can then be compressed with locally-adaptive algorithms, such as move-to-front coding in combination with Huffman or arithmetic coding.
SUMMARY OF THE INVENTION
A goal of preferred embodiments of the invention is to make a computer sorting system that is very simple, fast, deterministic in time and well suited for hardware implementation. The slow sorting of a data block and the recommended run-length encoding of the prior art is replaced by a new method. The output of this method is then compressed by any state of the art encoding method suitable for this task.
In case of equality after a predetermined number of steps, the position of the data within the data block is used as sort key instead of further comparisons. This position will always be different for different data items and will therefore always lead to a unique result. By using the position as the secondary sort key, only a predetermined limited number of characters is used for sorting (limited context). A context size of 4-6 characters is sufficient for most cases.
The main advantage is not this early exit but that in most cases, where the number of compared symbols is not much larger than the base two logarithm of the size of the to be sorted data block, a radix sorting algorithm, originally developed for mechanical sorting, can be used. This sorting method has all characteristics demanded in the original problem description: its hardware implementation is simple and its processing time is fast and fixed. A second advantage is that if radix sort is used, the throughput is not influenced by the block size. This allows the use of large data blocks, which improves compression. Depending on the circumstances, a bucket sort or a variant of a multikey quicksort may be better suited for the sorting task.
Another advantage of limited context is that anything can be used as context, for example the corresponding field of the last similar dataset. This allows improves compression for many applications.
The sorting described above can be reversed, which is essential for decompression. For reversal the starting points for each sort key (context) have to be known. In the case of internal contexts example one shows a way to count all contexts and thus calculate starting points for each. Furthermore, a modification of prior art methods can be used to count contexts. In case of external contexts all context information is known at the decoder.
Contrary to prior art sorts which establishes a unique order by continuing comparisons, a unique order in accordance with preferred embodiments of the invention is established in doubt by considering the original position.
The above and other features of the invention, including various novel details of construction and combination of parts, will now be more particularly described with reference to the accompanying drawings and pointed out in the claims. It will be understood that the particular Computer Sorting System for Data Compression embodying the invention is shown by way of illustration only and not as a limitation of the invention. The principles and features of this invention may be embodied in varied and numerous embodiments without departing from the scope of the invention.
REFERENCES:
patent: 3611316 (1971-10-01), Woodrun
patent: 4862167 (1989-08-01), Copeland, III
patent: 5150430 (1992-09-01), Chu
patent: 5153591 (1992-10-01), Clark
patent: 5274805 (1993-12-01), Ferguson et al.
patent: 5394143 (1995-02-01), Murray et al.
patent: 5396622 (1995-03-01), Lee et al.
patent: 5490269 (1996-02-01), Cohn et al.
patent: 5530854 (1996-06-01), Emery et al.
patent: 5551018 (1996-08-01), Hansen
patent: 5842208 (1998-11-01), Blank et al.
patent: 6075470 (2000-06-01), Little et al.
Fenwick, P., “Block Sorting Text Compression—Final Report,” Technical Report 130, ISSN 1173-3500, Apr. 23, 1996.
Burrows, M., et al., “A Block-Sorting Lossless Data Compression Algorithm,” SRC Search Report, pp. 1-18, XP646918, (1994).
Yokoo, H., et al., “Data Compression by Context Sorting,”IEICE Transactions on Fundamentals of Electronics, E79-A(5) :681-686 (1996).
Wongsawang, D., et al., “Dependency Data Compression with Self-Organizing Lists,”Transactions of Information Processing in Japan, 35(6) :955-965 (1994).
Hamilton Brook Smith & Reynolds P.C.
Homere Jean R.
LandOfFree
Method and apparatus for sorting data blocks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for sorting data blocks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for sorting data blocks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2487230