High speed data searching for information in a computer system

• US 6,012,057 A
• Filed: 07/30/1997
• Issued: 01/04/2000
• Est. Priority Date: 07/30/1997
• Status: Expired due to Term

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Quarterdeck Corp. (Gen Digital Inc.)
• Inventors: Spear, Daniel S., Mayer, Laurance W.
• Primary Examiner(s): Lintz, Paul R.
• Assistant Examiner(s): Colbert, Ella
• Application Number:
  US08/902,664
• Time in Patent Office: 888 Days
• Field of Search: 707/2, 707/5, 707/6, 707/203, 707/530, 341/51
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Efficiencies in searching and matching information in a computer system are achieved using embodiments of the invention. The invention can be used, for example, to build and utilize a dictionary of data for string replication compression. The data matching mechanism can also be applied to other situations where it is necessary to find a sequence of data in a data buffer (e.g. looking for a particular series of words, letters, or numbers in an online document). As a result of processing a current string using the data dictionary, it is possible to find a previously-processed dictionary string that has the greatest number of initial characters in common with the current string, and a location at which the current string can be inserted into the dictionary tree. A count field is used to improve the speed of searching for matched strings.

Claims

1. A method of searching information in a computer system comprising the steps of:

identifying a parent string and a child string from data input, and a first value that represents the number of initial characters that said parent string and said child string have in common;

comparing a subsequent string with said parent string to generate a second value that represents the number of initial characters that said parent and said subsequent string have in common;

examining said first and second values to identify the extent of the comparison between said subsequent string and said child string;

identifying a next string for comparison with said subsequent string when said first value is not equal to said second value;

selecting a grandchild string using a first branch of a dictionary tree associated with said child string when said first value is greater than said second value.

3. The method of claim 1 wherein a pointer to said child string in said data input is stored in an entry of an array accessible using the position of said parent string in said data input.

2. A method of searching information in a computer system comprising the steps of:

identifying a parent string and a child string from data input, and a first value that represents the number of initial characters that said parent string and said child string have in common;

comparing a subsequent string with said parent string to generate a second value that represents the number of initial characters that said parent and said subsequent string have in common;

examining said first and second values to identify the extent of the comparison between said subsequent string and said child string;

identifying a next string for comparison with said subsequent string when said first value is not equal to said second value;

selecting a grandchild string using a second branch of a dictionary tree associated with said child string when said first value is less than said second value.

4. An article of manufacture comprising:

a computer usable medium having computer readable program code embodied therein for searching information in a computer system comprising;

computer readable program code configured to cause a computer to identify a parent string and a child string from data input, and a first value that represents the number of initial characters that said parent string and said child string have in common;

computer readable program code configured to cause a computer to compare a subsequent string with said parent string to generate a second value that represents the number of initial characters that said parent and said subsequent string have in common;

computer readable program code configured to cause a computer to examine said first and second values to identify the extent of the comparison between said subsequent string and said child string;

computer readable program code configured to cause a computer to identify a next string for comparison with said subsequent string when said first value is not equal to said second value;

computer readable program code configured to cause a computer to select a grandchild string using a first branch of a dictionary tree when said first value is greater than said second value.

6. The article of manufacture of claim 4 wherein a pointer to said child string in said data input is stored in an entry of an array accessible using the position of said parent string in said data input.

5. An article of manufacture comprising:

a computer usable medium having computer readable program code embodied therein for searching information in a computer system comprising;

computer readable program code configured to cause a computer to identify a parent string and a child string from data input, and a first value that represents the number of initial characters that said parent string and said child string have in common;

computer readable program code configured to cause a computer to compare a subsequent string with said parent string to generate a second value that represents the number of initial characters that said parent and said subsequent string have in common;

computer readable program code configured to cause a computer to examine said first and second values to identify the extent of the comparison between said subsequent string and said child string;

computer readable program code configured to cause a computer to identify a next string for comparison with said subsequent string when said first value is not equal to said second value;

computer readable program code configured to cause a computer to select a grandchild string using a second branch of said dictionary tree when said first value is less than said second value.

7. A method of searching information in a computer system comprising the steps of:

creating a first array of pointers to strings contained in an input buffer;

creating a second array of pointers to strings that include a high occurrence sequence;

said step comprising the steps of;

determining whether a first sequence of bits of one of said strings matches said high occurrence sequence;

accessing an entry in said second array using a second sequence of bits of said one of said strings;

determining whether a pointer exists in said entry of said second array; and

storing in said entry a pointer to said one of said strings, if a pointer does not exist in said entry;

accessing said first array of pointers to identify a previous string, if a current string does not contain said high occurrence sequence;

accessing said second array of pointers to identify said previous string, if said current string does contain said high occurrence sequence;

comparing said previous string and said current string to determine whether a match exists; and

generating a compressed representation that includes a pointer to said previous string, if a match does exist.

8. The method of claim 7 further comprising the steps of:

identifying another previous string;

comparing said another previous string and said current string to determine the number of initial characters in said another previous string and said current string that match.

9. The method of claim 8 wherein said step of identifying further comprises the steps of:

creating a "lower" array, an entry in said lower array is capable of storing a pointer to a lower-value string, said lower-value string being lower in value than said previous string;

creating a "higher" array, an entry in said higher array is capable of storing a pointer to a higher-value string, said higher-value string being higher in value than said previous string;

retrieving said another previous string using said pointer to said higher-value string in said higher array, if said current string is higher in value than said previous string; and

retrieving said another previous string using said pointer to said lower-value string in said lower array, if said current string is lower in value than said previous string.

10. The method of claim 9 wherein said entry in said lower array and said entry in said higher array include a count, said count in said lower array entry identifying the number of initial bits in common between said previous string and said lower-value string and said count in said higher array entry identifying the number of initial bits in common between said previous string and said higher-value string.

11. An article of manufacturing comprising:

a computer usable medium having computer readable program code embodied therein for searching information comprising;

computer readable program code configured to cause a computer to create a first array of pointers to strings contained in an input buffer;

computer readable program code configured to cause a computer to create a second array of pointers to strings that include a high occurrence sequence;

computer readable program code configured to cause a computer to access said first array of pointers to identify a previous string, if a current string does not contain said high occurrence sequence;

computer readable program code configured to cause a computer to access said second array of pointers to identify said previous string, if said current string does contain said high occurrence sequence;

computer readable program code configured to cause a computer to compare said previous string and said current string to determine whether a match exists;

computer readable program code configured to cause a computer to generate a compressed representation that includes a pointer to said previous string, if a match does exist;

computer readable program code configured to cause a computer to determine whether a first sequence of bits of said current string matches said high occurrence sequence;

computer readable program code configured to cause a computer to access an entry in said second array using a second sequence of bits of said current string; and

computer readable program code configured to cause a computer to retrieve from said entry a pointer to said previous string.

12. An article of manufacturing comprising:

a computer usable medium having computer readable program code embodied therein for searching information comprising;

computer readable program code configured to cause a computer to create a first array of pointers to strings contained in an input buffer;

computer readable program code configured to cause a computer to create a second array of pointers to strings that include a high occurrence sequence;

computer readable program code configured to cause a computer to access said first array of pointers to identify a previous string, if a current string does not contain said high occurrence sequence;

computer readable program code configured to cause a computer to access said second array of pointers to identify said previous string, if said current string does contain said high occurrence sequence;

computer readable program code configured to cause a computer to compare said previous string and said current string to determine whether a match exists;

computer readable program code configured to cause a computer to generate a compressed representation that includes a pointer to said previous string, if a match does exist;

computer readable program code configured to cause a computer to identify another previous string; and

computer readable program code configured to cause a computer to compare said another previous string and said current string to determine the number of initial characters in said another previous string and said current string.

13. The article of manufacture of claim 12 wherein said computer readable program code configured to cause a computer to identify further comprises:

computer readable program code configured to cause a computer to create a "lower" array, an entry in said lower array is capable of storing a pointer to a lower-value string, said lower-value string being lower in value than said previous string;

computer readable program code configured to cause a computer to create a "higher" array, an entry in said higher array is capable of storing a pointer to a higher-value string, said higher-value string being higher in value than said previous string;

computer readable program code configured to cause a computer to retrieve said another previous string using said pointer to said higher-value string in said higher array, if said current string is higher in value than said previous string; and

computer readable program code configured to cause a computer to retrieve said another previous string using said pointer to said lower-value string in said lower array, if said current string is lower in value than said previous string.

14. The article of manufacture of claim 13 wherein said entry in said lower array and said entry in said higher array includes a count, said count in said lower array entry identifying the number of initial bits in common between said previous string and said lower-value string and said count in said higher array entry identifying the number of initial bits in common between said previous string and said higher-value string.

15. The article of manufacture of claim 12 wherein said computer readable program code configured to cause a computer to compare further comprises computer readable program code configured to cause a computer to compare the bits in said current string and said another previous string excluding the bits represented by said count.

16. An article of manufacturing comprising:

a computer usable medium having computer readable program code embodied therein for searching information comprising;

computer readable program code configured to cause a computer to create a first array of pointers to strings contained in an input buffer;

computer readable program code configured to cause a computer to create a second array of pointers to strings that include a high occurrence sequence;

computer readable program code configured to cause a computer to access said first array of pointers to identify a previous string, if a current string does not contain said high occurrence sequence;

computer readable program code configured to cause a computer to access said second array of pointers to identify said previous string, if said current string does contain said high occurrence sequence;

computer readable program code configured to cause a computer to compare said previous string and said current string to determine whether a match exists; and

computer readable program code configured to cause a computer to generate a compressed representation that includes a pointer to said previous string, if a match does exist, wherein said compressed representation includes a header field, said header field having a variable length and identifying the type for an associated content field.