Recientemente leí este resumen de los problemas relacionados con la diferencia entre los árboles y me interesó aprender cuál es el estado del arte para este problema. Además, suponga que entre sus operaciones de edición permitidas se encuentran el nodo tradicional de agregar / eliminar, edite el...
¿Cuál es la complejidad más conocida para calcular la distancia de edición exacta entre dos cadenas de la misma longitud utilizando un espacio de trabajo que es sublineal en el tamaño de la entrada? Supongo que la entrada se almacena en algún formato de solo lectura. ¿Es este un problema...
Tengo dos particiones de [1…n][1…n][1 \ldots n] y estoy buscando la distancia de edición entre ellas. Con esto, quiero encontrar el número mínimo de transiciones individuales de un nodo en un grupo diferente que son necesarias para pasar de la partición A a la partición B. Por ejemplo, la...
¿Existe una categoría de parches que se ve más o menos así? Los objetos son cadenas en algún alfabeto base Los morfismos son guiones de edición ("diffs" o "parches") entre las cadenas Estoy interesado en estas preguntas: ¿Existe una noción categórica de guión de edición mínima ? ¿Quizás la...
Motivación: un coautor edita un manuscrito y me gustaría ver un resumen claro de las ediciones. Todo "diff" -como herramientas tienden a ser inútil si usted está tanto en el texto desplazando dentro (por ejemplo, la reorganización de la estructura) y haciendo las modificaciones locales. ¿Es...
Si nos dan dos cadenas de tamaño y n 2 , la Levenshtein cálculo de distancia de edición estándar es mediante un algoritmo dinámico con el tiempo complejidad O ( n 1 n 2 ) y el espacio complejidad O ( n 1 n 2 ) . (Se pueden hacer algunas mejoras en función de la distancia de edición d , pero no...
Estoy buscando una estructura de datos y un algoritmo para calcular la cantidad mínima de cambios necesarios para transformar una palabra en otra, dadas las dos palabras como entradas, donde los únicos cambios permitidos son agregue una letra en una de las extremidades (por ejemplo, AB ->...
Motivación : Mientras desarrollamos herramientas para el control de versiones de datos, terminamos buscando algoritmos para "diferenciar" dos conjuntos de enteros, creando una secuencia de transformaciones que llevan un conjunto de enteros al otro. Pudimos reducir ese problema al siguiente problema...
Las frases: El rápido zorro marrón salta sobre el perro perezoso [A] y El zorro marrón de Uick salta sobre el perro perezoso [B] se puede comparar usando el algoritmo de distancia de Levenshtein para determinar la similitud calculando el número mínimo de adiciones, eliminaciones o...
Me gustaría un método eficiente para calcular la cantidad mínima de transposiciones necesarias para ordenar una lista. No necesito saber cuáles son las transposiciones en realidad. Por ejemplo, la lista [1, 1, 2, 0] requiere 2 transposiciones: [1, 1, 2, 0] // Start [1, 1, 0, 2] // Swap index 2...