Distància de Damerau-Levenshtein

En la teoria de l'informació i en la ciència de computadors, es diu distància de Damerau-Levenshtein o distància d'edició al número mínim d'operacions requerides per a transformar una cadena de caràcters en una atra. S'entén per operació, be una inserció, eliminació, substitució o transposició de dos caràcters. Lo que la distinguix de la distància de Levenshtein és que este últim conte com una sola operació d'edició a qualsevol de les tres primeres, pero conta la transposició com dos operacions d'edició.

Vejam un eixemple senzill, calculem la distància Damerau-Levenshtein entre la paraula DAR i la paraula DAS. Observem que els dos primers caràcters són iguals, i que simplement hem de transformar el tercer caracter, és dir, hem de fer una única transformació, que consistirà en substituir la lletra R per la lletra S. ya que hem fet una transformació, la distància Damerau-Levenshtein entre les paraules DAR i DAS és 1.

Les distància Damerau-Levenshtein es distinguix de la distància Damerau en que la primera considera que l'operació de trasposición és una única operació. Un eixemple de l'operació de trasposición seria la que es donaria entre les cadena de text POTRO i PORTO. La distància Damerau-Levenshtein entre estes dos paraules és 1 perque hem fet una operació per a passar d'una a una atra, l'operació de trasposición.

La distància Damerau-Levenshtein s'ampra, per eixemple, en motors de busca de cadenes de text. Un dels motors de busca més coneguts que ampra esta distància d'edició és Lucene. Ho ampra, per eixemple, per a corregir errors de tecleig: imaginem que estic buscant les obres del director de cine "Hitchcock", i ho teclege de forma incorrecta, tecleig "Hichcock". Este motor de busca, i els motors de busca que es basen en ell tals com Solr, nos donen les coincidències en la paraula teclejada en una distància de fins a 2, de manera que, pese a teclejàrem mal el nom del director, apareixerien els resultats corresponents al nom correcte del director, ya que entre "Hitchcock" i "Hichcock" la distància és d'1.

Hem pres com a eixemple varis casos senzills, per a cadenes de caràcters més llargues i complexes s'utilisa una matriu que es va completant de forma algorítmica d'acort en una série de condicions.

Les condicions llògiques per a reblir la matriu són les següents:

Condicions llògiques de la matriu de distància