Method and apparatus for sorting data blocks

[0002] 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.

[0003] 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.

[0004] 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.

[0005] 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.

[0006] 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.

[0007] 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.

[0008] 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.

[0009] 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.

[0010] 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.

[0011] 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.

[0012] FIG. 1 is a schematic block diagram of a computing system in accordance with a preferred embodiment of the invention.

[0013] FIG. 2 is a block diagram of an encoder using internal contexts in accordance with a preferred embodiment of the invention.

[0014] FIG. 3 is a block diagram of a decoder using internal contexts in accordance with a preferred embodiment of the invention.

[0015] FIGS. 4A-4B illustrates a method of sorting for compression using internal contexts.

[0016] FIGS. 5A-5B illustrate a method of unsorting the sorted text of FIG. 4B for decompression using internal contexts.

[0017] FIG. 6 is a block diagram of an encoder using external contexts in accordance with a preferred embodiment of the invention.

[0018] FIG. 7 is a block diagram of an decoder using external contexts in accordance with a preferred embodiment of the invention.

[0019] FIGS. 8A-8D illustrate a method used in situations where the contexts for each data item to be coded are supplied as input data known to both the encoder and decoder.

[0020] FIG. 9 is a flowchart of a preferred method for implementing a transform function.

[0021] FIG. 10 is a flowchart of a preferred method of an inverse transform function.

[0022] FIG. 11 is a flowchart of a preferred method of another inverse transform function.

[0023] FIG. 12 is a flowchart of a high-order method for a transform function.

[0024] FIG. 1 is a schematic block diagram of a computing system in accordance with a preferred embodiment of the invention. Illustrated are two computers 10, 20 communicating over a communication link 30 via respective modems 18, 28. Each computer 10, 20 is operated by a respective user 2, 2′. Data is stored on respective disks 15, 25.

[0025] In accordance with a preferred embodiment of the invention, each computer 10, 20 executes a respective data coder 50, 50′. Each data coder 50, 50′ includes a respective encoder 52, 52′ for compressing data and a respective decoder 54, 54′ for decompressing data. The data coder 50, 50′ communicates with the modem 18, 28 to encode data for transmission over the communication link 30 and to decode received data from the communication link 30. The data coder 50, 50′ can also encode data for storage on the disk 15, 25 and decode the stored data read from the disk 15, 25.

[0026] In a preferred embodiment of the invention, the coder 50 is incorporated within a computing system having one or more computing devices. The coder 50 can be an executable software program or a hardware module. In either case, the coder 50 is embodied in a machine-readable medium, such as magnetic or optical storage or directly fabricated into a circuit device. A computer program embodying preferred embodiments of the invention is preferably distributed on a magnetic storage medium (e.g. hard disk, floppy disk, or tape) or on an optical storage medium (e.g. CD-ROM). It will also be understood that a computer can be specialized machines. For example, compressed data can be stored on a machine-readable medium and decompressed by a dedicated decompressor for use by any machine, such as a typesetting machine.

[0027] In particular, preferred embodiments of the invention include a method for sorting data which brings together data items which occur in a similar environment (the “context”). This reordering (“transformation”) of the data block allows it to be compressed more effectively using known compression algorithms. The contexts can be “internal”, meaning that they can be established by the other bytes in the data block being encoded. The contexts can also be “external”, meaning that they can be provided as data known to both the encoder 52 and the decoder 54.

[0028] FIG. 2 is a block diagram of an encoder 52 using internal contexts in accordance with a preferred embodiment of the invention. A source data block 105 is processed by a transform function 110, using either the prior art Burrows-Wheeler Transform (BWT) or a transform as described below. A start index 115 which is needed to reverse the transform is stored. The transformed data is then compressed by an compression transform data function 120 using any suitable compression method. Two or more stage arithmetic coding using a cache and two special symbols for binary representation of a repetition count have been useful. The encoded data 125 includes the compressed transform data and the start index 115.

[0029] FIG. 3 is a block diagram of a decoder 54 using internal contexts in accordance with a preferred embodiment of the invention. To restore the original data block 105, the compression algorithm 120 (FIG. 2) is reversed. The start index 115 is separated from the encoded data 125. The remaining data is then decompressed by a decompressor 150. The resulting decoded data and the start index 115 are then processed by an inverse transform function 155, which completes the decoding and yields a decoded data block 105′ identical to the original data block 105.

[0030] The difference between preferred embodiments of the invention and the BWT is the transform 110 (FIG. 2) and the inverse transform 155 (FIG. 3). The transform in accordance with the present invention and the differences from BWT are more fully described in the following example.

[0031] FIGS. 4A-4B illustrates a method of sorting for compression using internal contexts. As illustrated in FIG. 4A, the example uses order 2, text ‘abracadabra’, alphabet {‘a’,‘b’,‘c’,‘d’,‘r’}. The source data block 105 is therefore the ordered letters:

[0032] a b r a c a d a b r a

[0033] From each letter in the source data block 105, the previous two letters 107 are determined to be:

[0034] ra aa ab br ra ac ca ad da ab br Each letter in the source data block 105 is also associated with a respective text position or index 109 in the source data block 105. Because there are eleven letters, there are eleven text positions 107 (1-11), as illustrated.

[0035] The letters are then sorted by the previous letters as illustrated in FIG. 4B. The sort looks first at the immediately preceding letter, and if they are equal, it compares the next previous letter. If two letters have the same context, they are listed in the order that they occur in the original data block.

[0036] The resulting sorted letters 112 are:

[0037] b d b a c r r a a a a

[0038] For each letter, the previous letters 107′ and text position 107′ from the original source data block 105 is retained. The sorted text “bdbacrraaaa” can now be compressed by the compression transform data function 120 (FIG. 2).

[0039] With larger blocks and higher order (for text approximately 4 to 6) blocks appear like those with the full sorting of the BWT. For example the letters “sor” are often followed by the letter ‘t’ on this page.

[0040] When using the BWT, it would be necessary to consider the contexts “dabra” and “aabra” to determine sort order of a(1) and c(5). In some cases (for example 1000 zero-bytes) the context can become very large before a sort order can be established. That drawback is avoided using preferred compression methods as described below.

[0041] FIGS. 5A-5B illustrate a method of unsorting the sorted text of FIG. 4B for decompression using internal contexts. After decoding, the sequence of decoded text 112′ is known. It is also known that the letters preceding them were sorted in order, and this sequence 151 can be generated from the decoded text using a sorting or counting method similar to the inverse BWT, which returns the sequence “aaaaabbcdrr”. These letters 151 are the predecessors of each of the letters in the decoded text 112′.

[0042] Because the processor sort sequence 151 is the context byte immediately prior to the sorted text item, they can be combined with the decoded text 112′ to make pairs bf letters 152 known.

[0043] Each of these pairs of letters is also the context for one of the letters in the decoded text. These pairs 152 are then sorted by the last character first as was done in encoding, which yields a sort order 153 in the same order as the decoded text 107 (FIG. 4B). A sequential index 154 is then associated with the sorted pairs 153.

[0044] The order of the source data block can now be reconstructed as illustrated in FIG. 5B. As with the BWT, the position of the originally last (or first) character—index 11 in this case, which is associated with the context ‘br’ from the sorted pairs 153 and which itself is the context for an ‘a’ from the decoded text 112—is sorted. Alternatively, the context of the first character can be stored.

[0045] Either way one gets ‘bra’ as context for the first character. Now one searches the first context ‘ra’ (index 4) and gets another ‘a’ as next letter. Context ‘aa’→b(1), context ‘ab’→r(6), because the first appearing letter comes first in the sorted file in case of non-unique contexts, ‘br’→a(10), ‘ra’→c(5, since index 4 is already used), ‘ac’→a(8), ‘ca’→d(2), ‘ad’→a(9), ‘da’→b(3), and ‘ab’→r(7). In this way the original text “abracadabra” 105′ can be recovered completely.

[0046] In a practical implementation a pointer to the start of each context is stored in a hash-table. If this context appears, one follows the pointer and finds the correct continuation. Then the pointer is incremented by one.

[0047] For higher order, the order can be raised this way: the known n-letter combinations are extended by the letter following them, like here the known 1-letter contexts established by sorting or counting were extended to two-letter contexts. This results in knowledge of all n+1-letter combinations of the original text. This process can be repeated until the context size is large enough.

[0048] It is also possible to apply inverse BWT on the sorted text—all order+1 long letter combinations are returned correct and thus give all contexts of the original text. It could be that the inverse BWT returns to the origin early; if this is the case the inverse BWT must be restarted again with an unvisited index until all indices are visited.

[0049] FIG. 6 is a block diagram of an encoder 52 using external contexts in accordance with a preferred embodiment of the invention. For each item in a source data block 205 to be encoded, a corresponding context 210 is provided. A transform 215 in accordance with the present invention is then implemented, and the transformed data block is then encoded into encoded data 225 by a compression transformed data function 220 using any suitable method.

[0050] FIG. 7 is a block diagram of an decoder 54 using external contexts in accordance with a preferred embodiment of the invention. To restore the original data block 205, the encoded data 225 is first decoded by a decoder function 250 which uses the inverse of the algorithm that was used in the compression transform data function 225 (FIG. 6). In order to perform an inverse transform 255, the same context data 210 that was presented to the encoder 52 is supplied as input data. This enables the original data block to be restored by the inverse transform 255 as a decoded data block 205′ identical to the original data block 205. Further details of a preferred embodiment of the invention using external contexts will be described in the following example.

[0051] FIGS. 8A-8D illustrate a method used in situations where the contexts for each data item to be coded are supplied as input data known to both the encoder and decoder. As in the above example, the method sorts the data items according to the contexts, and when contexts are equal, the position in the original data block is used as a secondary sort key. An example of this type of application is for coding image data using a binary pyramid.

[0052] As illustrated in FIG. 8A, each pixel 300 is assigned a label, here “A”, “b”, “c”, “d”, and “e”. As illustrated in FIG. 8B, the image to be encoded is subdivided into little squares 305 (here edges are four pixels lengths long), and the corners are labeled with “A” and processed first. Then the centers of these little squares (labeled “b”) are processed. As illustrated in FIG. 8C, the pixels labeled “A” and “b” together give smaller squares 310 rotated standing on a corner. The center points of these smaller squares (labeled “c”) are next to be processed. As illustrated in FIG. 8D, the pixels labeled “A”, “b” and “c” together form still smaller squares 315 with an edge size of two pixel lengths. The center points of those squares (labeled “d”) come next. This is continued until all pixel are processed. The initial square size can be larger than the 4 pixels used in this example, and the processing would be the same except for the increase in the number of levels (f,g,h, . . . ) over the five (A . . . e) used here.

[0053] The encoding of the image can be done as five separate blocks. The first contains all of the “A”-labeled pixels, the second contains the “b”-labeled pixels, followed by the “c”,“d”, and “e”-labeled pixels. When the “A”-labeled pixel block is encoded, no other context data is known, so the “A”-labeled pixels must be encoded using a method which does not require external contexts. The method illustrated by FIGS. 4A-4B could be used, or any other method. The method in accordance with a preferred embodiment of the invention is used for processing the “b”-labeled pixels and the subsequent levels.

[0054] Each “b”-labeled pixel has a context determined by the four “A”-labeled pixels at its corners. Because the “A”-labeled pixels were previously encoded, they will be known to the decoder when it decodes the “b”-labeled pixels. The “b”-labeled pixels are the source data block 205 (FIG. 6), and the contexts formed by the “A”-labeled pixels for each “b”-labeled pixel are the context data 210. If each context consists of four bytes, such as when four eight-bit “A”-labeled pixels are concatenated into a 32 bit word, the transform 215 is an order 4 sort, as shown in the second implementation below. Once transformed, the same encoding algorithm can be used for the encode transform data function 225 as was used above. After the “b”-labeled pixels have been encoded, the “A” and “b”-labeled pixels can be used as the contexts to transform the “c”-labeled pixels. This process is continued until all levels have been processed.

[0055] Many variations are possible. Instead of using the pixel values as the source data block 205, the data can include errors from predicted values. In this case, the contexts would not be directly formed by concatenating the raw “A”-labeled corner pixels, but rather would be consist of an error estimator synthesized from those “A”-labeled pixels. Such variations do not affect preferred methods of the present invention, as the sorting of the data according to the contexts would still be done in the same way.

[0056] This example demonstrates how the combination of a finite-context sort followed by a sort-by-position can be used as a solution to a wide range of applications in data compression to bring similar contexts together. Note that including a unique position in a sort key is equivalent to the method described herein—it just becomes part of the primary key instead of being a secondary key or handled implicit like in the following first implementation. This is true even if the so constructed key uses infinite context because any comparison will stop at the unique position.

[0057] Four sample implementations are set forth below. The first three implementations use an order 2 (two byte) context, which allows the counters used in the method to be handled using simple arrays and which then allows the use of the block position as a secondary sort key to be most easily understood. The first implementation describes an encoder that can be used for both internal and external contexts. The second implementation describes a decoder for external contexts. The third implementation describes a decoder for internal contexts. The fourth implementation describes an encoder using internal contexts which can handle higher orders and which uses the radix sort.

[0058] Preferred embodiments of the invention use counters to determine the frequency of each context and then to determine its position in the sorted data block. This is described with respect to the first, second and third implementations below. These preferred implementation provides three counter functions:

[0059] InitCounters—sets the counter values to zero

[0060] GetAndlncrement—retrieves and post-increments the counter value associated with a context

[0061] AddCounters—replaces each counter value with a sum of previous counter values

[0062] The first, second and third implementations implement these functions for order 2 (two byte context), which allows use of a simple array that provides a counters[i] value for each possible context i. At higher orders, an array representing all possible contexts may not be practical, and the simple array can be replaced by a trie, tree, hash-table, or other approach. Note that trees and tries can be walked in the order needed for AddCounters, whereas the contexts are additionally sorted for AddCounters if using a hash-table. A prototype pseudo-code fragment for implementing counters in accordance with a preferred embodiment of the invention for order 2 is as follows:

[0063] FIG. 9 is a flowchart of a preferred method for implementing a transform function. The method 400 is used for the transform functions 110 (FIG. 2), 215 (FIG. 6) for internal and external contexts that are used in compression. Data variables are initialized at step 405. At step 410, the source data block is read. At step 415, the frequency of occurrence of each context in the data block is calculated. At step 420, the position of the first instance of each context in the data block is calculated. At step 425, the data from the data block is sorted by context.

[0064] At step 430, a check is made to determine whether internal contexts are being used. If so, then the index of the last element in the sorted data is stored at step 435.

[0065] A prototype pseudo-code fragment implementing the flowchart of FIG. 9 is given below. It is assumed that a function context(i) exists that gives the context of each symbol in the block to be processed. For internal contexts, this function returns the previous four bytes in the block. This example uses a bucketsort to show the relation to the decoder better. Items are sorted by the value of their context.

[0066] FIG. 10 is a flowchart of a preferred method of an inverse transform function. The method 500 is applicable to the inverse transform 250 (FIG. 7) used for external contexts in decompression. At step 505, data variables are initialized. At step 510, the decompressed data block is read. At step 515, the frequency of occurrence of each context in the data block is calculated. At step 520, the position of the first instance of each context in the data block is calculated. At step 525, the data is unsorted.

[0067] A prototype pseudo-code fragment implementing the flowchart of FIG. 10 is given below. It is assumed that a function context(i) exists that gives the context of each symbol in the block to be processed. Note that with external contexts all contexts 210 (FIGS. 6-7) are already known, so this function is defined.

[0068] FIG. 11 is a flowchart of a preferred method of another inverse transform function. The method 600 is applicable to the inverse transform 155 (FIG. 3) for internal contexts used in decompression.

[0069] Unlike the inverse transfer method 500 of FIG. 10, more effort is needed here to determine context frequencies. The initialization step 505 (FIG. 10) is extended by construction of a transposition vector at step 605. At step 610, counts are initialized. The counting step 515 (FIG. 10) is replaced by a more complex sequence of steps (steps 615-625) which use repeated inverse BWT attempts. At step 630, context positions are determined as above in FIG. 10 (step 520). At step 635, the data is unsorted. A prototype pseudo-code fragment for implementing the method of FIG. 11 is as follows:

[0070] FIG. 12 is a flowchart of a high-order method for a transform function. The method 700 can be applied as a higher order transform 110 (FIG. 2) for internal contexts. A particular preferred implementation of the transform supports 6 byte contexts and uses the radix sort to achieve fast encoding speeds. It sorts the data in three passes, using two bytes of the context in each pass.

[0071] At step 705, data variables are initialized as above. At step 710, each context is counted as above. At step 715, all smaller contexts are summed independent of the system end as above.

[0072] At step 720, a loop begins to process multiple passes of sorting. A loop index is incremented at step 720. At step 725, the sort is performed for the current pass. At step 730, the loop can return to step 720 for another pass or processing can exit.

[0073] Preferred embodiments of the invention can be implemented in hardware easily, by replacing variable with storage, loops with counters and indices with memory readouts where the index is sent to the address connectors. There are optimizations which can be exploited by hardware implementations. For example it may make sense to collect some bytes in fast static ram and then transmit them as a block to slow dynamic ram. It is also possible to introduce pipelining easily; one block is postprocessed, some others are in different sorting stages or are preprocessed/counted. Because any intermediate stage is possible (CPU+ROM program—hardware or software) all such combinations are understood to be within the scope of the invention. A prototype pseudo-code fragment is as follows:

[0074] Equivalents

[0075] While the invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood to those skilled in the art that various changes in form and detail can be made without departing from the spirit and scope of the invention as defined by the appended claims. For example, although the invention has been described with reference to particular hardware and software embodiments, it will be understood that various aspects of the invention can be embodied in either hardware, software or firmware.

[0076] These and all other equivalents are intended to be encompassed by the following claims.