Computer implemented methods for constructing a compressed data structure from a data string and for using the data structure to find data patterns in the data string

• US 6,119,120 A
• Filed: 06/28/1996
• Issued: 09/12/2000
• Est. Priority Date: 06/28/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Miller, John W.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): FREDERICK, GILBERTO
• Application Number:
  US08/673,427
• Time in Patent Office: 1,537 Days
• Field of Search: 382/229, 382/230, 382/231, 707/6, 707/3, 707/7, 707/101, 707/2
• US Class Current: 1/1
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for constructing a data structure for a data string of characters includes producing a matrix of sorted rotations of the data string. This matrix defines an A array which is a sorted list of the characters in the data string, a B array which is a permutation of the data string, and a correspondence array C which contains correspondence entries linking the characters in the A array to the same characters in the B array. A reduced A'"'"' array is computed to identify each unique character in the A array and a reduced C'"'"' array is computed to contain every s^th entry of the C array. The B array is segmented into blocks of size s. During a search, the A'"'"' and C'"'"' arrays are used to index the B array to reconstruct any desired row from the matrix of rotations. Through this representation, the matrix of rotations can thus be used as a conventional sorted list for pattern matching or information retrieval applications. A data structure containing only the A'"'"', B, and C'"'"' has very little memory overhead. The B array contains the same number of characters as the original data string, and can be compressed in a block wise manner to reduce its size. The A'"'"' array is a fixed size equal to the size of the alphabet used to construct the data string, and the C'"'"' array is variable size according to the relationship n/s, where n is the number of characters in the data string and s is the size of the blocks of the B array. Accordingly, the data structure enables a tradeoff between access speed and memory overhead, the product of which is constant with respect to block size s.

Claims

1. A method comprising the following steps:

producing a matrix of sorted rotations of a data string of characters, the matrix defining an A array comprising a sorted listing of the characters in the data string and a B array which is a permutation of the data string and a C array which contains entries of correspondence information linking the characters in the A array to the same characters in the B array;

segmenting the B array into blocks;

defining indexing information used to find particular characters within the blocks to reconstruct patterns of characters within the data string;

storing the blocks of the B array and the indexing information in a data structure; and

finding patterns of characters within the data string using the data structure.

2. A method as recited in claim 1, further comprising the step of compressing the blocks of the B array individually of each other.

3. A method as recited in claim 1, wherein the defining step comprises the following steps:

examining each block of the B array; and

for each associated block, constructing character type information that identifies which types of characters and how many characters of particular types are contained within the associated block.

4. A method as recited in claim 3, further comprising the step of organizing the data structure to include the blocks of the B array and a header associated with each block which contains the character type information.

6. A method as recited in claim 1, wherein the defining step comprises the following steps:

examining each block of the B array; and

for each block, constructing character jump information to reference where a next character of a particular type occurs in the blocks of the B array.

7. A method as recited in claim 6, further comprising the step of organizing the data structure to include the blocks of the B array and a header associated with each block which contains the character jump information.

9. A storage medium storing a data structure constructed according to the steps in the method as recited in claim 1.

10. A computer programmed to perform the steps of the method as recited in claim 1.

11. A computer-readable memory which directs a computer to perform the steps of the method as recited in claim 1.

5. A method comprising the following steps:

producing a matrix of sorted rotations of the data string, the matrix defining a B array which is a permutation of the data string;

segmenting the B array into blocks;

defining indexing information used to find particular characters within the blocks to reconstruct patterns of characters within the data string;

storing the blocks of the B array and the indexing information in a data structure;

examining each block of the B array;

for each associated block, constructing character type information that identifies which types of characters and how many characters of particular types are contained within the associated block;

organizing the data structure to include the blocks of the B array and a separate array containing the character type information for correlated blocks; and

finding patterns of characters within the data string using the data structure.

8. A method comprising the following steps:

producing a matrix of sorted rotations of the data string, the matrix defining a B array which is a permutation of the data string;

segmenting the B array into blocks;

defining indexing information used to find particular characters within the blocks to reconstruct patterns of characters within the data string;

storing the blocks of the B array and the indexing information in a data structure;

examining each block of the B array;

for each block, constructing character jump information to reference where a next character of a particular type occurs in the blocks of the B array;

organizing the data structure to include the blocks of the B array and a separate array containing the character jump information for correlated blocks; and

finding patterns of characters within the data string using the data structure.

12. A method comprising the following steps:

producing a matrix of sorted rotations of the data string, the matrix defining an A array comprising a sorted listing of the characters in the data string and a B array which is a permutation of the data string;

computing a correspondence array C which contains correspondence entries linking the characters in the A array to the same characters in the B array;

computing a reduced A'"'"' array which identifies each unique character in the A array;

computing a reduced C'"'"' array which contains every s^th entry of the C array;

segmenting the B array into blocks of size s;

storing the blocks of the B array, the A'"'"' array, and the C'"'"' array in a data structure; and

finding patterns of characters within the data string using the data structure.

13. A method as recited in claim 12, further comprising the step of compressing the blocks of the B array individually of each other.

14. A method as recited in claim 12, further comprising the following steps:

examining each block of the B array; and

for each associated block, constructing character type information that identifies which types of characters and how many characters of particular types are contained within the associated block.

15. A method as recited in claim 14, further comprising the step of storing in the data structure the character type information as a header to the associated block of the B array.

16. A method as recited in claim 14, further comprising the step of storing in the data structure the character type information as a separate array.

17. A method as recited in claim 12, wherein the defining step comprises the following steps:

examining each block of the B array; and

for each associated block, constructing character jump information to reference where a next character of a particular type occurs in the blocks of the B array.

18. A method as recited in claim 17, further comprising the step of storing in the data structure the character jump information as a header to the associated block of the B array.

19. A method as recited in claim 17, further comprising the step of storing in the data structure the character jump information as a separate array.

20. A method as recited in claim 17, wherein the data string comprises DNA sequences.

21. A storage medium storing a data structure constructed according to the steps in the method as recited in claim 12.

22. A computer programmed to perform the steps of the method as recited in claim 12.

23. A computer-readable memory which directs a computer to perform the steps of the method as recited in claim 12.

24. A computer-readable memory having a data structure, the data structure being derived from a matrix of sorted rotations formed from a data string of characters, the matrix defining an A array comprising a sorted listing of the characters in the data string and a B array which is a permutation of the data string and a C array which contains entries of correspondence information linking the characters in the A array to the same characters in the B array, the data structure comprising:

multiple blocks having substrings of characters segmented from the B array; and

at least one index array used to index the blocks.

25. A computer-readable memory as recited in claim 24, wherein the substrings of each block are compressed.

26. A computer-readable memory as recited in claim 24, further comprising a type header attached to each block, the type header identifying which types of characters and how many characters of particular types are contained within the associated substring.

27. A computer-readable memory as recited in claim 24, further comprising a jump attached to each block, the jump header referencing where a next character of a particular type occurs in the blocks of characters.

28. A computer-readable memory having a data structure, the data structure being derived from a matrix of sorted rotations formed from a data string of characters, the matrix defining an A array comprising a sorted listing of the characters in the data string and a B array which is a permutation of the data string and a C array which contains entries of correspondence information linking the characters in the A array to the same characters in the B array, the data structure comprising:

multiple blocks having substrings of s characters segmented from the B array;

an A'"'"' array which identifies each unique character in the A array;

a C'"'"' array which contains every s^th entry of the C array; and

the A'"'"' and C'"'"' arrays being used to reconstruct the data string of characters from the multiple blocks when searching for a particular pattern of characters within the data string.

29. A computer-readable memory as recited in claim 28, wherein the substrings of each block are compressed.

30. A computer-readable memory as recited in claim 28, wherein the data structure further comprises an array containing character type information that identifies which types of characters and how many characters of particular types are contained within the associated block.

31. A computer-readable memory as recited in claim 28, wherein the data structure further comprises an array containing character jump information which references where a next character of a particular type occurs in the blocks.

32. A computer system comprising:

a processor;

an application executable on the processor to produce a matrix of sorted rotations of a data string of characters, the matrix defining an A array comprising a sorted listing of the characters in the data string and a B array which is a permutation of the data string and a C array which contains entries of correspondence information linking the characters in the A array to the same characters in the B array, the application further directing the processor to segment the B array into blocks and to define indexing information used to find particular characters within the blocks to reconstruct patterns of characters within the data string;

a memory to store a data structure containing the blocks of the B array and the indexing information; and

the processor finding patterns of characters within the data string using the data structure.

33. A computer system as recited in claim 32, wherein the application further directs the processor to compress the blocks of the B array independently of each other.

34. A computer system as recited in claim 32, wherein the application further directs the processor to derive character type information for each block that identifies which types of characters and how many characters of particular types are contained within the associated block.

35. A computer system as recited in claim 32, wherein the application further directs the processor to derive character jump information for each block that references where a next character of a particular type occurs in the blocks.