Method for performing string matching

• US 5,761,538 A
• Filed: 07/10/1995
• Issued: 06/02/1998
• Est. Priority Date: 10/28/1994
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Hull, Richard
• Primary Examiner(s): Cosimano, Edward R.
• Application Number:
  US08/499,967
• Time in Patent Office: 1,058 Days
• Field of Search: 364/400, 382/185, 382/186, 382/187, 382/217, 382/218, 382/219, 382/229, 395/603, 395/899
• US Class Current: 712/300
• CPC Class Codes: G06F 16/90344 by using string matching techniques

Abstract

An improved method of matching a query string against a plurality of candidate strings replaces a highly computationally intensive string edit distance calculation with a less computationally intensive lower bound estimate. The lower bound estimate of the string edit distance between the two strings is calculated by equalising the lengths of the two strings by adding padding elements to the shorter one. The elements of the strings are then sorted and the substitution costs between corresponding elements are summed.

Claims

1. A method for calculating a lower bound estimate of string edit distance between query string and a candidate string, the method comprising:

equalising lengths of the strings by adding padding elements to a shorter one of the strings;

sorting the query string and the candidate string according to their element values;

calculating a sum of substitution costs of the elements in corresponding positions in the sorted strings, the sum of the substitution costs being the lower bound estimate of string edit distance.

2. A string matching method comprising steps of:

calculating a string edit distance between a query string and one of a plurality of candidate strings and storing said candidate string as a current best match string;

calculating a lower bound estimate distance for each remaining candidate string and evaluating each result such that;

if a lower bound estimate distance is greater than a current best match distance the candidate string from which the estimate was calculated is discarded;

otherwise calculating the string edit distance between the query string and the current candidate string and replacing the current best match string with whichever of the current candidate string and the current best match string has a lower string edit distance from the query string;

storing a final best match string.

3. A method according to claim 2 further comprising an initial step of calculating the lower bound estimate distance from the query string for each candidate string in turn and ordering said candidate strings according to lower bound estimate distance.

4. A method according to claim 3 comprising a further step of discarding all of said candidate strings having lower bound estimate distances greater than a predefined threshold distance before performing a first string edit distance calculation.

5. A scribble matching apparatus in which a query string is matched against a candidate string, the apparatus calculating a lower bound estimate of string edit distance between the strings and comprising:

means for equalizing lengths of the strings by adding padding elements to a shorter one of the strings;

means for sorting the query string and the candidate string according to a value of their elements; and

means for calculating a sum of substitution costs of elements in corresponding positions in the sorted strings, the sum of the substitution costs being the lower bound estimate of string edit distance.

6. An apparatus according to claim 5, further comprising:

means for calculating string edit distance between a query string and one of a plurality of candidate strings and for storing said candidate string as a current best match string;

means for calculating said lower bound estimate distance for each remaining candidate string and evaluating results such that;

if a lower bound estimate distance is greater than a current best match distance the candidate string is discarded;

otherwise calculating the string edit distance between the query string and the current candidate string and retaining the current candidate string or the current best match string, whichever has the lower string edit distance from the query string, as the current best match candidate string; and

means for storing the final best match candidate string.

7. An apparatus according to claim 6, further comprising:

means for calculating a lower bound estimate distance from the query string for each candidate string in turn; and

means for ordering said candidate strings according to lower bound estimate distance.

8. An apparatus according to claim 7, further comprising means for discarding all of said candidate strings having lower bound estimate distances greater than a predefined threshold distance before performing a first string edit distance calculation.

9. A method for matching a query graphical data sample against one or more candidate graphical data samples comprising steps of:

providing each of one or more candidate graphical data samples as a candidate string;

providing the query graphical data sample as a query string; and

matching the query string against the one or more candidate strings, wherein this matching comprises sorting of the strings according to their internal element values;

characterised in that the step of matching the query string against the one or more candidate strings comprises a step of calculating a lower bound estimate of a string edit distance between the query string and at least one of the candidate strings, wherein the step of calculating the lower bound estimate of the string edit distance between the query string and a candidate string comprises;

equalising string lengths by adding padding elements to a shorter one of the strings;

sorting the strings according to their internal element values;

calculating a sum of substitution costs for elements in corresponding positions in the sorted strings, the sum of the substitution costs being the lower bound estimate of the string edit distance.

10. A method according to claim 9, wherein each of said graphical data samples is a sample of electronic ink.

11. A method according to claim 9, further comprising the steps of:

calculating a string edit distance between said query string and one of said candidate strings and storing said candidate string as a current best match string;

calculating a lower bound estimate distance for each remaining candidate string and evaluating each result such that;

if the lower bound estimate distance is greater than the current best match string edit distance the candidate string is discarded;

otherwise calculating string edit distance between the query string and the current candidate string and replacing the current best match string with the current candidate string or the current best match string, whichever has a lower string edit distance from the query string;

storing a final best match string.

12. A method according to claim 11, wherein each of said graphical data samples is a sample of electronic ink.

13. A method according to claim 11 further comprising an initial step of calculating the lower bound estimate distance from the query string for each of the candidate strings in turn and sorting said candidate strings according to lower bound estimate distance.

14. A method according to claim 13, wherein each of said graphical data samples is a sample of electronic ink.

15. A method according to claim 13 comprising a further step of discarding all of said candidate strings having lower bound estimate distances greater than a predefined threshold distance before performing a first string edit distance calculation.

16. A method according to claim 15, wherein each of said graphical data samples is a sample of electronic ink.

17. A scribble matching device, comprising:

means to enter a query sample of electronic ink;

means to encode an entered query sample of electronic ink as a query string;

means to store candidate electronic ink samples as candidate strings; and

a matcher adapted for matching the query string against the one or more candidate strings by a method which comprises a step of calculating a lower bound estimate of string edit distance between the query string and at least one of the candidate strings, wherein the step of calculating the lower bound estimate of string edit distance between the query string and a candidate string comprises;

equalising the string lengths by adding padding elements to a shorter one of the strings;

sorting the strings according to their internal element values;

calculating a sum of substitution costs of elements in corresponding positions in the sorted strings, the sum of the substitution costs being the lower bound estimate of the string edit distance.

18. A scribble matching device as claimed in claim 17, wherein the matcher is adapted for matching the query string against the one or more candidate strings by a method comprising steps of:

calculating a string edit distance between said query string and one of said candidate strings and storing said candidate string as a current best match string;

calculating a lower bound estimate distance for each remaining candidate string and evaluating each result such that;

if the lower bound estimate distance is greater than a current best match distance the candidate string is discarded;

otherwise calculating the string edit distance between the query string and the current candidate string and replacing the current best match string with

whichever of the current candidate string and the current best match string has a lower string edit distance from the query string;

storing a final best match string.

19. A device as claimed in claim 18, wherein the matcher is adapted for matching the query string against the one or more candidate strings by a method which further comprises an initial step of calculating the lower bound estimate distance from the query string for each of the candidate strings in turn and sorting said candidate strings acording to lower bound estimate distance.