Editar distancia con operaciones de movimiento

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 realmente tan difícil hacerlo bien?

Definiciones: Me gustaría encontrar la distancia mínima de edición, donde las operaciones permitidas son:

• operaciones "baratas": agregar / cambiar / eliminar un solo carácter (las operaciones habituales de Levenshtein),

• "costoso": operaciones: mueve una subcadena a una nueva ubicación ( $abcd \mapsto acbd$ para cualquier cadena $a$ , $b$ , $c$ , $d$ ).

Dadas dos cadenas $x$ e $y$ y enteros $k$ y $K$ , me gustaría resolver el siguiente problema:

• ¿puedes transformar $x$ en $y$ usando como máximo $k$ operaciones baratas y como máximo $K$ operaciones costosas?

Preguntas:

1. ¿Este problema tiene un nombre? (Suena como una pregunta muy estándar en el contexto de la alineación de secuencias).

2. ¿Es difícil?

3. Si es difícil, ¿es un parámetro fijo manejable con como parámetro?$K$

4. ¿Existen algoritmos de aproximación eficientes? (Por ejemplo, encuentre una solución con a lo sumo operaciones baratas y 2 K costosas si existe una solución con k operaciones baratas y K costosas).$2k$$2K$$k$$K$

Traté de echar un vistazo a las métricas de cadena enumeradas en Wikipedia , pero ninguna de ellas parecía correcta.

Como comentó Serge Gaspers, para el problema es Ordenar por transposiciones , y fue introducido por Bafna y Pevzner en 1995. Su dureza NP se demostró solo en 2010; ver Laurent Bulteau, Guillaume Fertin e Irena Rusu, "Ordenar por transposiciones es difícil" .$k=0$

El problema se vuelve más fácil si consideramos las eliminaciones largas y la copia de subcadenas en lugar de las transposiciones. Supongamos que estamos utilizando el algoritmo de programación dinámica estándar para el cálculo de la distancia de edición, y que una operación costosa de longitud aumenta la distancia en a k + b , para algunas constantes a , b ≥ 0 . Estas constantes pueden ser diferentes para eliminaciones largas y copia de subcadenas.$k$$ak+b$$a,b \ge 0$

Una eliminación larga es la eliminación de una subcadena arbitraria de . Es fácil apoyarlos si los dividimos en dos tipos de operaciones simples: eliminar el primer carácter (costo a + b ) y extender la eliminación en un carácter (costo a ). Además de la matriz estándar A , donde A [ i , j ] es la distancia de edición entre los prefijos x [ 1 ... i ] e y [ 1 ... j ] , utilizamos otra matriz A $x$$a+b$$a$$A$$A[i,j]$$x[1 \dots i]$$y[1 \dots j]$$A_{d}$para almacenar la distancia de edición, cuando la última operación utilizada fue una eliminación larga. Con esta matriz, solo tenemos que mirar , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] y A d [ i - 1 , j ] al calcular A [ i , j ] y A d [ $A[i-1,j]$$A[i-1,j-1]$$A[i,j-1]$$A_{d}[i-1,j]$$A[i,j]$ , lo que nos permite hacerlo en O ( 1 ) tiempo.$A_{d}[i,j]$$O(1)$

Copia de subcadena significa la inserción de una subcadena arbitraria de en la cadena editada. Al igual que con las eliminaciones largas, dividimos la operación en dos operaciones simples: insertar el primer carácter y extender la inserción en un carácter. También utilizamos la matriz A s para almacenar la distancia de edición entre prefijos, siempre que la última operación utilizada fue la copia de subcadenas.$x$$A_{s}$

Hacer esto de manera eficiente es más complicado que con las eliminaciones largas, y no estoy seguro de si podemos llegar al tiempo amortizado por celda. Construimos un árbol de sufijos para x , que toma tiempo O ( | x | ) , suponiendo un alfabeto de tamaño constante. Almacenamos un puntero al nodo del árbol de sufijos actual en A s [ i , j - 1 ] , lo que nos permite verificar en tiempo constante si podemos extender la inserción por el carácter y [ j ] . Si eso es cierto, podemos calcular A [ $O(1)$$x$$O(|x|)$$A_{s}[i,j-1]$$y[j]$ y A s [ i , j ] en tiempo constante.$A[i,j]$$A_{s}[i,j]$

De lo contrario, , donde z es la subcadena insertada que se utilizó para calcular A s [ i , j - 1 ] , no es una subcadena de x . Usamos el árbol de sufijos para encontrar el sufijo más largo z ′ de z , para el cual z ′ y [ j ] es una subcadena de x , en el tiempo O ( | z | - | z ′ | ) . Computar$zy[j]$$z$$A_{s}[i,j-1]$$x$$z'$$z$$z'y[j]$$x$$O(|z|-|z'|)$ , ahora necesitamos mirar las celdas A [ i , j - | z ′ | - 1 ] a A [ i , j - 1 ] . Encontrar el sufijo z ' requiere solo el tiempo O ( 1 ) amortizadopor celda, pero calcular A s [ i , j ] con un enfoque de fuerza bruta requiere O ( | $A_{s}[i,j]$$A[i, j-|z'|-1]$$A[i,j-1]$$z'$$O(1)$$A_{s}[i,j]$ tiempo. Probablemente haya alguna forma de hacer esto de manera más eficiente, pero no puedo encontrarlo en este momento.$O(|z'|)$

En el peor de los casos, el algoritmo tarda tiempo, pero debería ser posible un mejor análisis. La distancia de edición resultante con eliminaciones largas y copia de subcadenas no es simétrica, pero eso no debería ser un problema. Después de todo, generalmente es más fácil alcanzar la cadena vacía desde una que no está vacía que al revés.$O(\min(|x| \cdot |y|^{2}, |x|^{2} \cdot |y|))$