- Llenándose
- Leída
- Respuesta
Distancia de edición (distancia de Levenshtein)
¿Cuántos cambios de una sola letra convierten kitten en sitting? Tres: sustituir k por s, sustituir e por i y añadir una g. Ese número es la distancia de edición, y así ordenan los correctores ortográficos sus sugerencias y comparan los biólogos los genes. Escribe dos palabras y mira cómo una tabla la encuentra. Pulsa Reproducir para ver cómo se llena la tabla, o Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto. Escribe dos palabras: la primera va por el lado izquierdo de la tabla y la segunda por arriba. Cada celda guarda el menor número de operaciones que convierten las letras hasta su fila en las letras hasta su columna. Al final, las operaciones se leen hacia atrás desde la celda inferior derecha. Nuevo ejemplo elige otro par de palabras. Con el tablero seleccionado, las flechas avanzan o retroceden un paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Escribe dos palabras: la primera va por el lado izquierdo de la tabla y la segunda por arriba.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar paso a paso. Arrastra el control de pasos para saltar a cualquier punto.
- Mira cómo cada celda toma el más barato de sus tres vecinos y luego cómo se leen hacia atrás las operaciones en naranja.
Cómo funciona la tabla
Una celda guarda el menor número de operaciones que convierten las letras de la primera palabra hasta su fila en las letras de la segunda palabra hasta su columna. La primera fila cuenta inserciones, que construyen la segunda palabra desde cero, y la primera columna cuenta borrados. Si las dos letras de una celda son iguales, copia la celda de arriba a la izquierda: no hace falta ninguna operación. Si no, vale uno más que el menor de tres vecinos: arriba a la izquierda para una sustitución, arriba para un borrado y a la izquierda para una inserción.
Leer las operaciones hacia atrás
La celda inferior derecha es la distancia de edición. Desde ahí, la aplicación busca de qué vecino viene el valor de la celda y pasa a él: en diagonal para una letra conservada o sustituida, hacia arriba para una borrada y hacia la izquierda para una insertada. Leídos desde la esquina superior izquierda, los pasos forman una lista de operaciones lo más corta posible, que aparece bajo la tabla: una letra sola se conserva, k→s es una sustitución, −e un borrado y +g una inserción.
Preguntas frecuentes
¿Qué es la distancia de Levenshtein?
Es otro nombre de esta distancia de edición: el menor número de inserciones, borrados y sustituciones de una sola letra que convierten una cadena en otra. Lleva el nombre de Vladimir Levenshtein, que la describió en 1965.
¿Cuál es la distancia de edición entre kitten y sitting?
3: sustituir k por s, sustituir e por i e insertar g al final. La tabla muestra que no existe ninguna lista de operaciones más corta.
¿Cuánto tarda el algoritmo de la distancia de edición?
Para palabras de longitudes m y n, la tabla tiene (m + 1)·(n + 1) celdas, y cada una se llena en un paso, así que tarda un tiempo O(m·n). Si solo se necesita la distancia, bastan dos filas de la tabla.
¿Qué otras distancias de edición hay?
La distancia de Damerau–Levenshtein también cuenta como una operación el intercambio de dos letras vecinas, lo que encaja con los errores de tecleo. La distancia de Hamming solo permite sustituciones y sirve para cadenas de la misma longitud. La distancia LCS solo permite inserciones y borrados.
¿Se envía algo a algún sitio?
No. Todo se calcula en tu navegador, y tus últimos ajustes se guardan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor