Optimizar una lista de adiciones y supresiones de texto

https://stackoverflow.com/questions/2077621

21-09-2019
|

Pregunta

Tengo una lista que contiene las posiciones de adiciones y supresiones de texto, así:

     Type   Position   Text/Length
1.   +      2          ab          // 'ab' was added at position 2
2.   +      1          cde         // 'cde' was added at position 1
3.   -      4          1           // a character was deleted at position 4

Para que quede más claro, esto es lo que estas operaciones van a hacer:

    1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    ---------------------------------
    t | e | x | t |   |   |   |   |  
1.  t | a | b | e | x | t |   |   |  
2.  c | d | e | t | a | b | e | x | t
3.  c | d | e | a | b | e | x | t |

El número de acciones puede reducirse a:

     Type   Position   Text/Length
1.   -      1          1           // 't' was deleted at position 1
2.   +      1          cdeab       // 'cdeab' was added at position 1

     Type   Position   Text/Length
1.   +      1          cdeab       // 'cdeab' was added at position 1
2.   -      6          1           // 't' was deleted at position 6

Estas acciones se van a guardar en mi base de datos y con el fin de optimizar esta: ¿cómo puedo reducir el número de acciones que deben ser realizadas para obtener el mismo resultado? ¿Hay una manera más rápida que O (n * n)?

Tenga en cuenta que estas acciones son cronológico, cambiando el orden de las acciones va a dar otro resultado.

Solución

No es una solución, sólo algunos pensamientos:

Regla 1: Si las dos operaciones consecutivas no tienen intervalos que se solapan, pueden ser intercambiado (con posiciones ajustadas)
Regla 2: dos inserciones o eliminaciones consecutivas en la misma posición se pueden unir
Regla 3: cuando un inserto es seguido por una eliminación que está completamente contenida en el inserto, que se pueden unir

No veo un algoritmo sencillo para la solución más corta. Sin embargo, un enfoque heurístico usando la regla 1 + 2 podría ser:

mover hacia "arriba", a menos
- que le viola la Regla 1
- se movería una inserción antes de una extracción
- la posición es menor que la de que el predecesor
unirse a inserciones consecutivas / remociones en la misma posición

Se aplica a la muestra, esto significaría:

 + 2 ab
 + 1 cde
 - 4 1

Regla 1 (2x):

+ 2 ab
- 1 1   // position adjusted by -3
+ 1 cde

- 1 1  
+ 1 ab  // position adjusted
+ 1 cde

Regla 2:

- 1 1
+ 1 cdeab // watch correct order!

Una aplicación primitiva será O (N * N) - básicamente, una especie de burbuja con las condiciones de parada additonal. No estoy seguro de que la complejidad cayendo a plomo, ya que los algoritmos estándar son de ninguna utilidad aquí, debido a tener que ajustar la posición.

Sin embargo, es posible que pueda mejorar las cosas en particular - por ejemplo, que no es necesario "una especie completa"

Otros consejos

Hacer un árbol binario que representa el documento antes y después de aplicar todos los cambios. Cada nodo representa o bien texto original o texto insertado / suprimido; este último tipo de nodo incluye tanto la cantidad de texto original para borrar (posiblemente 0) y la cadena de texto para insertar (posiblemente vacía).

Inicialmente, el árbol tiene un solo nodo, "0 a extremo: texto original". Aplicar todos los cambios a que la fusión de los cambios sobre la marcha siempre que sea posible. A continuación, recorrer el árbol de principio a fin que emite la serie final de ediciones. Esto está garantizado para producir el resultado óptimo.

La aplicación de una inserción: Encontrar el punto apropiado en el árbol. Si está en el medio de o adyacente al texto insertado, basta con cambiar la cadena de texto a insertar de ese nodo. De lo contrario añadir un nodo.
La aplicación de un borrado: Encontrar los puntos inicial y terminan en el árbol, a diferencia de una inserción, una eliminación puede cubrir toda una serie de nodos existentes. Modificar el inicio y final nodos en consecuencia, y matar a todos los nodos intermedios. Después de que haya terminado, comprobar para ver si tiene "/ borrados de texto insertado" nodos adyacentes. Si es así, unirse a ellos.

El único poco complicado es asegurarse de que se pueden encontrar puntos en el árbol, sin actualizar todo el árbol cada vez que realice un cambio. Esto se hace mediante el almacenamiento en caché, en cada nodo, la cantidad total de texto representado por ese subárbol. Luego, cuando se hace un cambio, es suficiente para actualizar estos valores almacenados en caché en los nodos directamente encima los nodos que haya modificado.

Esto parece estrictamente O (n log n) a mí por toda la entrada, si se molestan en poner en práctica un enfoque equilibrado cuerdas de árboles y uso para el texto insertado. Si zanja toda la idea de árbol y utilizar vectores y cadenas, que es O (n ²), pero podría funcionar bien en la práctica.

Ejemplo resuelto. Aquí es cómo se aplicaría este algoritmo a su ejemplo, paso a paso. En vez de hacer arte ASCII complicado, Voy a su vez el árbol de lado, muestro los nodos en orden, y mostrar la estructura de árbol de sangría. Espero que sea claro.

Estado inicial:

*: orig

he dicho anteriormente nos caché de la cantidad de texto en cada sub-árbol. Aquí acabo de poner un * para el número de bytes porque este nodo contiene todo el documento, y no sé cuánto tiempo que es. Se podría utilizar cualquier número suficientemente grande, digamos 0x4000000000000000L.

Después de la inserción de "ab" en la posición 2:

    2: orig, 2 bytes
*: insert "ab", delete nothing
    *: orig, all the rest

Después de la inserción de "cde" en la posición 1:

        1: orig, 1 byte
    5: insert "cde", delete nothing
        1: orig, 1 byte
*: insert "ab", delete nothing
    *: orig, all the rest

El siguiente paso es eliminar un carácter en la posición 4. pausa aquí para ver cómo se encuentra la posición 4 en el árbol.

Comience en la raíz. Mira el primer nodo hijo: ese subárbol contiene 5 caracteres. Así posición 4 debe estar ahí. Mover a ese nodo. Mira su primer nodo hijo. Esta vez contiene sólo 1 carácter. No en ese país. Esta edición contiene 3 caracteres, por lo que no hay aquí tampoco; que es inmediatamente después. Pasar al segundo nodo hijo. (Este algoritmo es de aproximadamente 12 líneas de código.)

Después de borrar 1 carácter en la posición 4, se consigue esto ...

    4: orig, 1 byte
        3: insert "cde", delete nothing
*: insert "ab", delete nothing
    *: orig, all the rest

... y luego, al ver dos nodos adyacentes de inserción, que los combina. (Tenga en cuenta que dado dos nodos adyacentes, uno es siempre en alguna parte por encima de la otra en la jerarquía del árbol Combinar los datos en ese nodo superior;.. A continuación, eliminar el inferior y actualizar los tamaños de subárbol en caché en el medio)

    1: orig, 1 byte
*: insert "cdeab", delete nothing
    *: orig, all the rest

Las herramientas de "Diferencias" utilizados en los sistemas de control de código fuente usan algoritmos que producen la edición mínima necesaria para transformar una pieza de código fuente a otro - podría valer la pena investigarlos. Creo que la mayoría de ellos se basan (con el tiempo) en este algoritmo, pero es un tiempo desde que hice cualquier lectura sobre este tema.

Creo que esto se puede hacer considerablemente más rápido que O (N ²) en promedio (es probable que de entrada puede estar diseñado para no permitir el análisis rápido). Se puede considerar adiciones o supresiones consecutivas como conjuntos. Puede analizar una operación a la vez, y usted tendrá que hacer algunas transformaciones condicionales:

Si una adición sigue una adición, o un conjunto de adiciones, podría
- táctil (uno o más de) la adición previo (s): a continuación, se puede unir a estas adiciones
- No toque: se pueden hacer pedidos (que tendrá que ajustar las posiciones)
Si una deleción sigue una adición, o un conjunto de adiciones, podría
- Sólo borrar los caracteres de la adición: a continuación, puede modificar la adición (a menos que le iba a partir una adición)
- Sólo borrar los caracteres no del conjunto de adiciones: a continuación, puede mover la supresión de una posición antes de que el conjunto de adiciones, y tal vez unir adiciones; después de eso, el conjunto de deleciones antes de la actual serie de adiciones podría tener que ser aplicado a las adiciones antes de que
- hacer las dos cosas: a continuación, primero puede dividir en dos (o más) supresiones y aplicar el método respectivo
Si una deleción sigue una deleción, o un conjunto de deleciones, se puede:
- táctil (uno o más de) la eliminación previa (s): a continuación, se puede unir a estas eliminaciones
- No se toca: se pueden hacer pedidos (que tendrá que ajustar las posiciones
- En cualquier caso, usted entonces tiene que aplicar el análisis de las deleciones de nueva formación en las adiciones anteriores
Si una adición sigue una deleción, no se necesita ninguna transformación en este punto

Esto es sólo un primer borrador. Algunas cosas pueden tener que ser hecho de manera diferente, por ejemplo, podría ser más fácil o más eficiente de aplicar siempre todas las deleciones, por lo que el resultado es siempre sólo un conjunto de deleciones seguido por una serie de adiciones.

Supongamos para simplificar que sólo letras a-z aparecen en sus textos.

Inicializar una lista A con valores de a [i] = i para i = 1 a N (se darán cuenta de lo grande que usted mismo debe ser N).

Realizar (simular) todas sus operaciones en A. Después de este análisis de la A a encontrar operaciones requeridas:

Puño hallazgo requiere operaciones de borrado mediante la búsqueda de los números que faltan en A (que se formarán grupos de valores consecutivos, un grupo significa una operación de eliminación).

Después de esto se puede encontrar operaciones de inserción requeridos por la búsqueda de secuencias de consecutivo cartas (una secuencia es una operación de inserción).

En el ejemplo:

init A:

1 2 3 4 5 6 7 8 9 10

Paso 1 (+: 2: ab):

1 a b 2 3 4 5 6 7 8 9 10

Paso 2 (+: 1: cde):

c d e 1 a b 2 3 4 5 6 7 8 9 10

Paso 3 (-: 4: 1):

c d e a b 2 3 4 5 6 7 8 9 10

Ahora que la búsqueda de los números que faltan para encontrar eliminaciones. En nuestro ejemplo sólo un número (es decir, el número 1) no está presente, por lo que sólo 1 de eliminación se ha requerido, por lo que tenemos una operación de eliminación: -: 1: 1 (En general puede haber más números que faltan, cada secuencia de números que faltan es una operación de eliminación. Por ejemplo, si 1, 2, 3, 5, 6, 10 son todos los números que faltan, a continuación, hay 3 operaciones de borrado: -: 1: 3, -: 2: 2, -: 5: 1. Recuerde que después de cada operación de borrado de todos los índices se reducen, lo que tiene que almacenar suma total de las antiguas operaciones de borrado para calcular el índice de operación de eliminación actual.)

Ahora que la búsqueda de secuencias de caracteres para encontrar las operaciones de inserción. En nuestro ejemplo sólo hay una secuencia: cdeab en el índice 1, por lo que tenemos una operación de inserción: +: 1: cdeab

Espero que esto es bastante claro.

¿Cómo reducir el número de acciones: una aproximación algorítmica podría tratar de ordenar las acciones. Creo que después de clasificar:

La posibilidad de que las acciones vecinos se pueden unir (en la forma y Svante Peterchen mostró), se elevará.
Esto puede conducir a un número mínimo de acciones que tienen que llevarse a cabo?

En el siguiente "número-posición" significa la posición de inserción de texto o eliminación.

Si se asume que es posible intercambiar dos acciones vecinos (mediante el ajuste de posición y números texto / propiedad de longitud de estas dos acciones), que puede traer la lista de acciones a cualquier orden que me gusta. Sugiero traer las acciones de eliminación al frente de la lista de acciones con ascendente posición números. Después de que las acciones de eliminación de la adición-acciones están ordenados con ascendente posición números.

Los siguientes ejemplos deben demostrar, por lo que creo que es posible intercambiar cualquier acción vecinos.

swaping siguientes acciones:

  1. + 2 aaa -> taaaext
  2. - 3 1   -> taaext

rendimientos a una acción:

  1. + 2 aa  -> taaext

swaping siguientes acciones:

  1. + 3 aaa -> teaaaxt
  2. + 1 bb  -> bbteaaaxt

rendimientos a:

  1. + 1 bb  -> bbtext
  2. + 5 aaa -> bbteaaaxt

swaping siguientes acciones:

  1. + 1 bb  -> bbtext
  2. - 2 2   -> bext

rendimientos a:

  1. - 1 1   -> ext
  2. + 1 b   -> bext

A medida que el primer ejemplo muestra, en algunos casos un intercambio provoca la eliminación de una deleción. Esto es un beneficiando efecto secundario. Esta es también la cuestión por la que sugiero para mover todas las supresiones del frente.

Espero que no me olvido algo y cuenta todas las circunstancias.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow