Menor número de movimientos de edición entre dos palabras.

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 -> ABC),
• duplicar y concatenar la palabra completa (por ejemplo, ABC -> ABCABC),
• cortar una palabra en dos (el doble del movimiento de duplicación, ABCABC -> ABC + ABC),
• elimine una de las letras (por ejemplo, ABC -> AC) y
• repita una de las letras (por ejemplo, ABC -> ABBC).

Por ejemplo, una secuencia mínima de movimientos de ABC a BCBC es ABC -> BC (eliminar A) -> BCBC (duplicación).

No tengo experiencia en informática. Quizás este es un problema bien conocido, pero mi búsqueda en Google no me dio nada.

¿Conoces algún problema relacionado y bien definido?

Editar : Como se sugiere en la respuesta de Anthony Labarre, leí algunos documentos sobre el problema de permutación / disposición poset que es similar al problema descrito anteriormente. ¿Alguien sabe más sobre este problema? ¿Es esto relevante?

No sé si este problema exacto ha sido estudiado, pero Chaudhuri et al. estudió el problema relacionado con la pérdida aleatoria de duplicación en tándem : se le da una permutación y desea transformarla en la permutación de identidad al (1) duplicar un segmento de cualquier longitud y agregar la copia justo después del original, luego (2) eliminar elementos para que obtenga una nueva permutación en lugar de una cadena. Tenga en cuenta que aplicar (1) luego (2) representa una operación.

Se pueden definir diferentes variantes de acuerdo con el peso dado a cada operación, que en su papel depende del ancho de los segmentos duplicados. También estudian un problema similar con toda la duplicación del genoma , que es exactamente el tipo de duplicación que permite. No recuerdo haber leído sobre el trabajo en este problema en el contexto de las cadenas, pero espero que al menos pueda darle un punto de partida para sus búsquedas.

Como se ha señalado, este problema es similar al problema de distancia de edición más comúnmente conocido (subyacente a la distancia de Levenshtein ). También tiene puntos en común con, por ejemplo, la distancia Dynamic Time Warping (la duplicación o "tartamudeo" en su último requisito).

Pasos hacia la programación dinámica.

$x=x_1\ldots x_n$$y=y_1\ldots y_m$$d(x,y)$

$$\min \begin{cases} d(x,y_1\ldots y_{m-1})+1 & &\text{▻ Add letter at end}\\ d(x,y_2\ldots y_m)+1 & & \text{▻ Add letter at beginning}\\ d(x,y_1\ldots y_{m/2})+1 & \text{if $y=y_1\ldots y_{m/2}y_1\ldots y_{m/2}$} & \text{▻ Doubling}\\ d(x_1\ldots x_{n/2},y)+1 & \text{if $x=x_1\ldots x_{n/2}x_1\ldots x_{n/2}$} & \text{▻ Halving}\\ d(x_1\ldots x_n,y) + 1 && \text{▻ Deletion}\\ d(x_1\ldots x_{n-1},y_1\ldots y_{m-1}) & \text{if $y_n = y_m$} & \text{▻ Ignoring last elt.}\\ \end{cases}$$

Aquí, la última opción básicamente dice que convertir FOOX a BARX es equivalente a convertir FOOX a BAR. Esto significa que puede usar la opción "agregar letra al final" para lograr el efecto de tartamudeo (duplicación) y la eliminación en un punto. El problema es que automáticamente le permite agregar un arbitraria de caracteres en el medio de la cadena , así , algo que probablemente no desea. (Este "ignorar los últimos elementos idénticos" es la forma estándar de lograr la eliminación y la tartamudez en posiciones arbitrarias. Sin embargo, prohibir las inserciones arbitrarias, al tiempo que permite adiciones en cualquier extremo, es un poco complicado ...)

He incluido este desglose a pesar de que no hace el trabajo por completo, en caso de que alguien más pueda "rescatarlo", de alguna manera, y porque lo uso en mi solución heurística, a continuación.

(Por supuesto, si pudiera obtener un desglose como este que realmente definiera su distancia, solo necesitaría agregar una memorización y tendría una solución. Sin embargo, debido a que no solo está trabajando con prefijos, no lo hago ' piense que podría usar solo índices para su memorización; es posible que tenga que almacenar las cadenas modificadas reales para cada llamada, lo que se volvería enorme si sus cadenas son de un tamaño considerable).

Pasos hacia una solución heurística

Otro enfoque, que podría ser más fácil de entender y que podría usar un poco menos de espacio, es buscar la "ruta de edición" más corta desde su primera cadena hasta la segunda, utilizando el algoritmo (básicamente, mejor- primero ramificado y atado). El espacio de búsqueda se definiría directamente por sus operaciones de edición. Ahora, para una cadena grande, que lo haría$A^\ast$obtenga un vecindario grande, ya que podría eliminar cualquier carácter (dándole un vecino para cada eliminación potencial), o duplicar cualquier carácter (nuevamente, dándole un número lineal de vecinos), así como agregar cualquier carácter en cualquier extremo, lo que darle un número de vecinos igual al doble del tamaño del alfabeto. (Solo espero que no estés usando Unicode completo ;-) Con un fanout tan grande, podrías lograr una aceleración bastante sustancial usando un bidireccional , o algún pariente$A^*$ .

Para que funcione, necesitaría un límite inferior para la distancia restante a su objetivo. No estoy seguro de si hay una opción obvia aquí, pero lo que podría hacer es implementar una solución de programación dinámica basada en la descomposición recursiva que di anteriormente (nuevamente con posibles problemas de espacio si sus cadenas son muy largas). Mientras que la descomposición no calcula exactamente la distancia, que se garantiza que sea una cota inferior (porque es más permisiva), lo que significa que va a funcionar como una heurística en . (Lo apretado que será, no lo sé, pero sería correcto). Por supuesto, la memorización de su función enlazada podría compartirse en todos los cálculos del enlace durante su$A^*$$A^*$$A^*$correr. (Una compensación tiempo / espacio allí).

Entonces…

La eficiencia de mi solución propuesta parece depender bastante de (1) la longitud de sus cadenas y (2) el tamaño de su alfabeto. Si ninguno de los dos es enorme, podría funcionar. Es decir:

• Implemente el límite inferior a su distancia usando mi descomposición recursiva y programación dinámica (por ejemplo, usando una función recursiva y memorable).
• Implemente (o bidireccional ) con sus operaciones de edición como "movimientos" en el espacio de estado y el límite inferior basado en programación dinámica.$A^*$$A^*$

Realmente no puedo dar ninguna garantía de cuán eficiente sería, pero debería ser correcto, y probablemente sería mucho mejor que una solución de fuerza bruta.

Por lo menos, espero que esto te dé algunas ideas para futuras investigaciones.

Algún problema relacionado y bien definido sería el problema de la alineación de secuencias . Es diferente porque no utiliza la operación de duplicación. Las operaciones definidas son: inserción de caracteres, eliminación de caracteres, transformación de caracteres. Algoritmo popular para resolver este problema es Needleman-Wunsch .

A excepción de la duplicación, la distancia de Levenstein podría valer la pena: http://en.wikipedia.org/wiki/Levenshtein_distance