Patent US5761538A successfully refreshed from Google Patents.
US5761538A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for performing string matching
Assignee: Hewlett Packard Development Co LP
•
Filing: 1995-07-10
•
Granted: 1998-06-02
•
Expires: 2015-07-10
Abstract
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.
Inventors
- 👤 Richard Hull
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 23:29
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/903; G06F16/90335; G06F16/90344
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
82 words
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.
Claim 2
Independent Claim
82 words
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.
Claim 3
Dependent Claim
128 words
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.
Claim 4
Dependent Claim
128 words
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.
Claim 5
Dependent Claim
39 words
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.
Claim 6
Dependent Claim
36 words
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.
Claim 7
Dependent Claim
99 words
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.
Claim 8
Dependent Claim
99 words
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.
Claim 9
Dependent Claim
130 words
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.
Claim 10
Dependent Claim
39 words
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.
Claim 11
Dependent Claim
35 words
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.
Claim 12
Independent Claim
190 words
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.
Claim 13
Independent Claim
190 words
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.
Claim 14
Dependent Claim
19 words
A method according to claim 9, wherein each of said graphical data samples is a sample of electronic ink.
Claim 15
Dependent Claim
124 words
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.
Claim 16
Dependent Claim
19 words
A method according to claim 11, wherein each of said graphical data samples is a sample of electronic ink.
Claim 17
Dependent Claim
41 words
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.
Claim 18
Dependent Claim
19 words
A method according to claim 13, wherein each of said graphical data samples is a sample of electronic ink.
Claim 19
Dependent Claim
36 words
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.
Claim 20
Dependent Claim
19 words
A method according to claim 15, wherein each of said graphical data samples is a sample of electronic ink.
Claim 21
Dependent Claim
160 words
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.
Claim 22
Dependent Claim
160 words
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.
Claim 23
Dependent Claim
145 words
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.
Claim 24
Dependent Claim
63 words
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.
References Cited (Backward Citations)
US3108254A
Cited
US3127588A
Cited
US3111646A
Cited
US3133266A
Cited
US3200373A
Cited
EP0031493A1
Cited
US5148541A
Cited
US5313527A
Cited
US5467407A
Cited
US5459739A
Cited
US5434932A
Cited
US5553272A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-01 | 2001-12-01 | 2002-06-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-01 | 2005-12-01 | 2006-06-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-01 | 2009-12-01 | 2010-06-02 | $7700.00 | Window Closed / Lapsed |