A new distance metric on strings computable in linear time (Q1102764)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A new distance metric on strings computable in linear time |
scientific article; zbMATH DE number 4051043
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new distance metric on strings computable in linear time |
scientific article; zbMATH DE number 4051043 |
Statements
A new distance metric on strings computable in linear time (English)
0 references
1988
0 references
We describe a new metric for sequence comparison that emphasizes global similarity over sequential matching at the local level. It has the advantage over the Levenshtein metric that strings of lengths n and m can be compared in time proportional to \(n+m\) instead of nm. Various mathematical properties of the metric are established.
0 references
string matching
0 references
partial match
0 references
distance metric
0 references
clustering
0 references
text processing
0 references
editing
0 references
spelling correction
0 references
sequence comparison
0 references
sequential matching
0 references
0.8896215
0 references
0.87032104
0 references
0.8688839
0 references
0.86548394
0 references
