Method and arrangement for searching for strings

• US 20060179052A1
• Filed: 02/25/2004
• Published: 08/10/2006
• Est. Priority Date: 03/03/2003
• Status: Active Grant

• Current Assignee: Koninklijke Philips N.V.
• Original Assignee: Koninklijke Philips N.V.
• Inventors: Van Vuuren, Marcel, Egner, Sebastian, Pauws, Steffen Clarence, Korst, Johannes Henricus Maria
• Granted Patent: US 7,756,847 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

This invention relates to methods of searching for a final number of result strings (30-33) having a partial or an exact match with a query string (34) in a database (80) comprised of many long strings or a long string, said method includes the steps of partitioning the query string in a first number of input query strings (35, 36, 37); determining a second number of neighboring strings (38-41, 42-45, 44-49, respectively) for each string in said first number of input query strings, wherein each string in said second number of neighboring strings has a predetermined first number of errors; searching the database for a third number of exact matches (50-61, 70-74) for each string in said second number of neighboring strings based on a search method; concatenating said searched exact matched strings from the database into a fourth number of intermediate strings (29, 30, 32, 33, 34) wherein said searched exact matched strings (50-61, 70-74) comprised in each of said intermediate strings are in succession to one another in said database; and determining the final number of result strings (30-33) based in said fourth number of intermediate strings, wherein each string in the final number of result strings has a maximum of predetermined second number of errors compared to said query string (34). This enables for a perfect match or a partial match containing only minor errors with respect to said query string, and for a fast search in larger databases with a relative low use of processing power.

Claims

1. A method of searching for a final number of result strings (30-33), having a partial or an exact match with a query string (34), in a database (80) comprised of many long strings or a long string, said method comprising the steps of:

partitioning (100) the query string in a first number of input query strings (35, 36, 37);

determining (200) a second number of neighboring strings (38-41, 42-45, 44-49, respectively) for each string in said first number of input query strings, wherein each string in said second number of neighboring strings has a predetermined first number of errors;

searching (300) the database for a third number of exact matches (50-61, 70-74) for each string in said second number of neighboring strings based on a search method;

concatenating (400) said searched exact matched strings from the database into a fourth number of intermediate strings (29, 30, 32, 33, 34) wherein said searched exact matched strings (50-61, 70-74) comprised in each of said intermediate strings are in succession to one another in said database; and

determining (500) the final number of result strings (30-33) based on said fourth number of intermediate strings, wherein each string in the final number of result strings has a maximum of a predetermined second number of errors compared to said query string (34).

2. A method according to claim 1 characterized in that said search method is a q-gram index method.

3. A method according to claim 1 characterized in that said search method is a suffix tree method.

4. A method according to claim 1 characterized in that said search method is a hash method.

5. A method according to claim 1 characterized in that said strings and said database each comprises a sequence of letters of the western alphabet.

6. A method according to claim 1 characterized in that said strings and said database each represents the essence of a musical score.

7. A method according to any claim 1 characterized in that said strings and said database each comprises a sequence of binary digits.

8. A method according to claim 1 characterized in that said strings and said database each comprises a sequence of amino acids or a sequence of DNA/RNA bases.

9. A method according to claim 1 characterized in that said strings and said database each comprises a sequence of bits, bytes or words.

10. A search engine comprising calculation means (661) for carrying out the steps of the methods according to claim 1.

11. A tool comprising means for carrying out the steps of the methods according to claim 1.

13. A computer system for performing the method according to claim 1.

14. A computer program product (662) comprising program code means stored on a computer readable medium for performing the method of claim 1 when the computer program is run on a computer.

12. An arrangement (660) comprising:

calculation means for (661) partitioning the query string in a first number of input query strings (35, 36, 37);

calculation means for (661) determining a second number of neighboring strings (38-41, 42-45, 44-49, respectively) for each string in said first number of input query strings, wherein each string in said second number of neighboring strings has a predetermined first number of errors;

calculation means for (661) searching the database for a third number of exact matches (50-61, 70-74) for each string in said second number of neighboring strings based on a search method;

calculation means for (661) concatenating said searched exact matched strings from the database into a fourth number of intermediate strings (29, 30, 32, 33, 34) wherein said searched exact matched strings (50-61, 70-74) comprised in each of said intermediate strings are in succession to one another in said database; and

calculation means for (661) determining the final number of result strings (30-33) based on said fourth number of intermediate strings, wherein each string in the final number of result strings has a maximum of a predetermined second number of errors compared to said query string (34).