Convert Levenshtein Distance to Error Rate
Pregunta
Is their a way to convert levenstein distances to error rates?
With the error rate being the fraction of the sequence that is not exactly the same.
Solución
You mean you want to normalize Levenshtein distance to [0, 1]? That's
d(a,b) / max(len(a), len(b))
The denominator is an upper bound on Levenshtein distance, so this gives a figure between zero and one. Proof: assume (without loss of generality) that len(a) > len(b)
, then you can always transform a
into b
by substituting len(b)
characters and deleting len(a) - len(b)
of them, for a total of len(a) - len(b) + len(b) = len(a)
operations.
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow