Distancia de edición · programación dinámica

Halla una secuencia de edición mínima y sigue su tabla de distancias de prefijo celda a celda.

Acerca de esta herramienta

Convertir un texto en otro

Introduce un origen y un objetivo, cada uno con 0…20 puntos de código Unicode bien formados. Los textos vacíos son válidos. Calcular muestra primero la distancia mínima y una secuencia de edición óptima. Abre Distancias de prefijos para ver la matriz completa; Paso la abre automáticamente. Los códigos Unicode bajo los textos intermedios son desplegables. Paso arranca una tabla nueva cuando hace falta y revela exactamente una celda, fila a fila. Revelar la última celda completa el resultado de inmediato. Borrar resultado conserva los textos de entrada; editar un texto o cambiar el ejemplo borra el resultado anterior. Las entradas y los detalles abiertos se guardan localmente, incluso los borradores incompletos o no válidos. Recargar los restaura sin calcular; la navegación interna conserva el resultado o el paso actual.

Cómo funciona la tabla

La fila i significa los primeros i puntos de código del origen; la columna j los primeros j puntos de código del objetivo. Los índices de cabecera muestran la longitud del prefijo, seguida del último punto de código de ese prefijo. ∅ es el prefijo vacío. D[0,j] = j inserciones y D[i,0] = i borrados. Una celda interior elige el mínimo del valor diagonal más 0 por coincidencia o 1 por sustitución, el valor de arriba más 1 por borrado, y el valor de la izquierda más 1 por inserción.

La celda actual lista los candidatos y marca su predecesor elegido. Los empates prefieren la diagonal, luego el borrado, luego la inserción. El camino final resaltado une (0,0) con la celda inferior derecha. Selecciona una secuencia óptima determinista; pueden existir otras óptimas. Intercambiar dos caracteres vecinos no es una operación aparte: ab → ba tiene distancia 2 aquí.

Leer la secuencia de edición

Cada cambio listado cuesta 1. Las coincidencias cuestan 0 y aparecen en Alineación completa. Las posiciones empiezan en 0 en el texto inmediatamente anterior a esa operación, medidas en puntos de código. El texto posterior muestra el texto actual entero, no solo el carácter cambiado. Para kitten → sitting la distancia mínima es 3: sustituir k por s en la posición 0 para obtener sitten, sustituir e por i en la posición 4 para obtener sittin, luego insertar g en la posición 6 para obtener sitting.

Los huecos de alineación se etiquetan Hueco. Un guion literal sigue siendo un carácter, mostrado con U+002D, y nunca se usa para representar un hueco. Los números de paso en Alineación completa también cuentan coincidencias.

Unicode y texto exacto

El cálculo usa puntos de código, no unidades de código UTF-16 ni clústeres grafémicos visuales. 😀 → vacío tiene distancia 1, mientras que 👩‍💻 contiene tres puntos de código. é compuesto y e seguido de U+0301 son entradas distintas. No hay normalización, recorte, conversión de mayúsculas ni truncado silencioso. Se rechazan los subrogados UTF-16 no emparejados.

Cada carácter no alfanumérico tiene una etiqueta de código U+… en la matriz o la alineación. □ representa un carácter de espacio o invisible; su código identifica cuál. Un círculo punteado sostiene una marca combinante y no forma parte del texto origen. Los textos intermedios conservan su espacio en blanco real; sus notas de código usan posiciones de base cero. El aislamiento bidireccional evita que caracteres de derecha a izquierda y controles de dirección reordenen las etiquetas de alrededor.

Fuentes