A new distance metric on strings computable in linear time (Q1102764): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: author (P16): Item:Q294724 |
||
| Property / author | |||
| Property / author: Andrzej Ehrenfeucht / rank | |||
Revision as of 11:55, 12 February 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A new distance metric on strings computable in linear time |
scientific article |
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
