A new distance metric on strings computable in linear time

DOI10.1016/0166-218X(88)90076-5zbMath0644.68114OpenAlexW1995552834MaRDI QIDQ1102764

David Haussler, Andrzej Ehrenfeucht

Publication date: 1988

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(88)90076-5

zbMATH Keywords

clusteringstring matchingsequence comparisondistance metriceditingtext processingpartial matchsequential matchingspelling correction

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Pattern recognition, speech recognition (68T10) Prefix, length-variable, comma-free codes (94A45)

Related Items

Multiple filtration and approximate pattern matching ⋮ On the string matching with \(k\) mismatches ⋮ Approximate string-matching with \(q\)-grams and maximal matches

Cites Work

• The smallest automaton recognizing the subwords of a text
• A faster algorithm computing string edit distances
• A Space-Economical Suffix Tree Construction Algorithm
• A technique for isolating differences between files
• Unnamed Item