Method and apparatus for sorting data blocks

• US 6,199,064 B1
• Filed: 11/14/1997
• Issued: 03/06/2001
• Est. Priority Date: 11/15/1996
• Status: Expired due to Fees

• Current Assignee: Michael Schindler
• Original Assignee: Michael Schindler
• Inventors: Schindler, Michael
• Primary Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/970,220
• Time in Patent Office: 1,208 Days
• Field of Search: 707/7, 707/101, 707/100, 341/107, 341/51
• US Class Current: 1/1
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of sorting a block of data is provided which includes ordering a plurality of data values into a source data block. A non-unique sort order, based on a limited number of comparisons of the data values in the source data block, is established and, after the comparisons, a unique sort order of the data values based on position of the data values in the source data block is established. The method further includes restoring the source data block from the unique sort order. An apparatus for sorting a block of data is also provided, the apparatus including, inter alia, a first mechanism for calculating a non-unique sort order based on a limited number of equal comparisons of the data values in the source data block and a second mechanism for establishing, after the comparisons, a unique sort order of the data values based on position of the data values in the source data block. The apparatus further includes a third mechanism for restoring the source data block from the established sort order.

Claims

1. A method of compressing a source data block having a plurality of data values, whereby each data value within the source data block has a context, the method comprising:

using the context to define a primary sort key of a fixed, predetermined length for each data value;

deriving a secondary sort key for each data value from the position of the data value within the source data block;

generating a sorted source data block, comprising;

sorting the data values according to the primary sort key; and

for data values whose primary sort key is the same, further sorting the data values according to the secondary sort key; and

compressing the sorted source data block into a compressed data block.

2. The method of claim 1 wherein the secondary sort key is used implicitly.

3. The method of claim 1 wherein sorting comprises employing a radix sort.

4. The method of claim 1 wherein the source data block is restorable from the compressed data block.

5. The method of claim 4 wherein the source data block is restorable by calculating a transposition vector.

6. The method of claim 5 wherein the transposition vector is derived from a Burrows-Wheeler Transform.

7. The method of claim 1 further comprising deriving the context from the source data block.

8. The method of claim 1 further comprising determining the context independently from the source data block.

9. An apparatus for and compressing a source data block having a plurality of data values, whereby each data value within the source data block has context, comprising:

a primary sort key of a fixed, predetermined length for each data value defined by the context;

a secondary sort key for each data value derived from the position of the data value within the source data block;

a sorter for creating a sorted source data block, the sorter comprising;

a primary sorter for sorting the data values according to the primary sort key;

for data values having identical primary sort keys, a secondary sorter for sorting the data values according to the secondary sort key; and

compressing the sorted source data block into a compressed data block.

10. The apparatus of claim 9 wherein the secondary sort key is used implicitly.

11. The apparatus of claim 9 wherein the sorter employs a radix sort algorithm.

12. The apparatus of claim 9 wherein the source data block is restorable from the compressed data block.

13. The apparatus of claim 12 wherein the source data block is restorable from a transposition vector.

14. The apparatus of claim 13 wherein the transposition vector is derived from a Burrows-Wheeler Transform.

15. The apparatus of claim 9 wherein the context is derived from the source data block.

16. The apparatus of claim 9 wherein the context is determined independently from the source data block.

17. An article of manufacture comprising:

a machine-readable medium;

a method stored in the machine-readable medium to compress a block of data, the method comprising;

using the context to define a primary sort key of a fixed, predetermined length for each data value;

deriving a secondary sort key for each data value from the position of the data value within the source data block;

generating a sorted source data block, comprising;

sorting the data values according to the primary sort key; and

for data values whose primary sort key is the same, sorting the data values according to the secondary sort key; and

compressing the sorted source data block into a compressed data block.

18. The article of claim 17 wherein the secondary sort key is used implicitly.

19. The article of claim 17 wherein the sorting comprises employing a radix sort.

20. The article of claim 17 wherein the source data block is restorable from the comprised data block.

21. The article of claim 20 wherein the source data block is restorable by calculating a transposition vector.

22. The article of claim 21 wherein the transposition vector is derived from a Burrows-Wheeler Transform.

23. The article of claim 17 wherein the method further comprises deriving the context from the source data block.

24. The article of claim 17 wherein the method further comprises determining the context independently from the source data block.