Patent ID: 7209926

Claim:
A method of lexicographically sorting data for use by a data compressor to produce compressed data, the method comprising the acts of: receiving a set of N cyclic shifts of N characters; creating a sorting array of indexes {0, 1, 2, . . . , N−1} for identifying the set of N cyclic shifts of N characters, wherein each array element of the sorting array is the index of the array element in the array; creating an inverse sorting array of indexes, such that each array element at index i of the inverse sorting array is the index of the array element in the sorting array containing the index i; sorting the set of cyclic shifts based on a first character of each cyclic shift, where the array elements in the soiling a my are updated in accordance with the sorting of the set of cyclic shifts and the array elements in the inverse sorting array are updated such that each array element at index i of the inverse sorting array is the index of the array element in the sorting array containing the index i; iteratively sorting the set of cyclic shifts by, for an nth sorting iteration of the set of cyclic shifts, where n=1, 2, 3, . . . , up to 2 n >N; identifying a subset of cyclic shifts which are equivalent for the first 2 (n−1) characters; updating indexes of the sorting array by: for each array element of the sorting array associated with the identifed subset of cyclic shifts, retrieving the array element of the inverse sorting array indexed by the array element of the sorting array plus 2 (n−1) (modulo N); sorting the retrieved array elements from the inverse sorting array; and ordering the array elements of the sorting array corresponding to the sorting of the retrieved array elements from the inverse sorting array; updating the array elements of the inverse sorting array based on the updated array elements of the sorting array, such that each array element at index i of the inverse sorting array is the index of the array element in the sorting array containing the index i; and repeating the iterative sorting steps for a next nth sorting iteration as necessary until the set of cyclic shifts are lexicographically sorted for the data compressor.