Ottimizzare un elenco di aggiunte e soppressioni di testo

https://stackoverflow.com/questions/2077621

21-09-2019
|

Domanda

Ho una lista che contiene le posizioni di aggiunte di testo ed eliminazioni, come questo:

     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

Per renderlo più chiaro, questo è ciò che queste operazioni faranno:

    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 |

Il numero di azioni può essere ridotto 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

Queste azioni devono essere salvati nel mio database e al fine di ottimizzare questo: come posso ridurre il numero di azioni che devono essere fatto per ottenere lo stesso risultato? Esiste un modo più veloce di O (n * n)?

Si noti che queste azioni sono cronologico, cambiando l'ordine delle azioni darà un altro risultato.

Soluzione

Non è una soluzione, solo alcuni pensieri:

Regola 1: se due operazioni consecutive non hanno sovrapposizione intervalli, possono essere scambiati (con posizioni regolate)
Regola 2: due inserti consecutivi o rimozioni nella stessa posizione possono essere uniti
Regola 3: quando un inserto è seguita da una rimozione che è completamente contenuto nell'inserto, essi possono essere uniti

Non vedo un algoritmo semplice per la soluzione più breve. Tuttavia, un approccio euristico utilizzando Regola 1 + 2 potrebbe essere:

move "fino" a meno che
- che ci si violano Regola 1
- che ci si sposta un inserto prima di una rimozione
- la posizione è inferiore a quella del modello precedente che
aderire inserti consecutivi / rimozioni nella stessa posizione

applicata al campione, questo significherebbe:

 + 2 ab
 + 1 cde
 - 4 1

Regola 1 (2x):

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

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

Regola 2:

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

Un'implementazione primitiva sarà O (N * N) - fondamentalmente, una bolla sorta con condizioni di arresto interventi. Non sono sicuro di battere verso il basso che la complessità, dal momento che gli algoritmi standard sono di alcuna utilità qui a causa di dover regolare la posizione.

Tuttavia, si potrebbe essere in grado di migliorare le cose in particolare - per esempio non hai bisogno di una "full sorta"

Altri suggerimenti

Fare un albero binario che rappresenta il documento prima e dopo l'applicazione di tutte le modifiche. Ogni nodo rappresenta o testo originale o testo inserito / cancellato; quest'ultimo tipo di nodo include sia la quantità di testo originale per eliminare (possibilmente 0) e la stringa di testo da inserire (eventualmente vuoto).

Inizialmente l'albero ha un solo nodo, "0 fino alla fine: il testo originale". Applicare tutte le modifiche ad esso la fusione modifiche, come si va ovunque sia possibile. Poi a piedi l'albero dall'inizio alla fine emette il set finale di modifiche. Ciò è garantito per produrre il risultato ottimale.

L'applicazione di un inserto: Trova il punto appropriato nella struttura. Se è in mezzo o adiacente a testo inserito, basta cambiare quel nodo text-to-insert stringa. In caso contrario, aggiungere un nodo.
L'applicazione di una cancellazione: Trovare il punto iniziale e finale nella struttura-a differenza di un inserto, una cancellazione può coprire tutta una serie di nodi esistenti. Modificare l'inizio e la fine nodi di conseguenza, e uccidere tutti i nodi in mezzo. Dopo il gioco è fatto, controllare per vedere se avete adiacenti "inserita / testo cancellato" nodi. Se è così, unirsi a loro.

L'unica po 'complicato è fare in modo che si possono trovare punti nel albero, senza aggiornare l'intero albero ogni volta che si apporta una modifica. Questo viene fatto cache, ad ogni nodo, la quantità totale di testo rappresentato da tale sottostruttura. Poi, quando si apporta una modifica, è sufficiente aggiornare questi valori memorizzati nella cache su nodi direttamente sopra i nodi modificati.

Questo sembra strettamente O (n log n) a me per tutti gli input, se si preoccupano di implementare un albero e uso equilibrato corde per il testo inserito. Se fosso l'intera idea albero e utilizzare vettori e stringhe, è O (n ²), ma potrebbe funzionare bene in pratica.

esempio pratico. Ecco come questo algoritmo si applicherebbe al tuo esempio, passo dopo passo. Invece di fare ascii art complicato, mi trasformerò l'albero su un lato, mostrare i nodi in ordine, e mostrare la struttura ad albero con rientro. Spero che sia chiaro.

Stato iniziale:

*: orig

ho detto sopra che avremmo in cache la quantità di testo in ogni sotto-albero. Qui ho appena messo a * per il numero di byte perché questo nodo contiene l'intero documento, e non so quanto tempo che è. È possibile utilizzare qualsiasi numero di grandi abbastanza, diciamo 0x4000000000000000L.

Dopo aver inserito "ab" in posizione 2:

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

Dopo aver inserito "cde" alla posizione 1:

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

Il passo successivo è quello di eliminare un carattere alla posizione 4. Pausa qui per vedere come troviamo posizione 4 nella struttura.

Inizia alla radice. Guardate il primo nodo figlio: che sottoalbero contiene 5 caratteri. Così posizione 4 deve essere lì. Spostare a quel nodo. Guardate il suo primo nodo figlio. Questa volta contiene solo 1 carattere. Non in là. Questa modifica contiene 3 caratteri, quindi non è qui sia; è subito dopo. Passare al secondo nodo figlio. (Questo algoritmo è di circa 12 righe di codice.)

Dopo l'eliminazione 1 carattere alla posizione 4, si ottiene questo ...

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

... e poi, notando due nodi di inserimento adiacenti, li uniscono. (Si noti che dati due nodi adiacenti, uno è sempre da qualche parte sopra l'altra nella gerarchia ad albero unire i dati in tale nodo superiore;.. Quindi eliminare quella inferiore e aggiornare le dimensioni di sottostruttura cache in mezzo)

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

Gli strumenti "diff" utilizzati nei sistemi di controllo del codice sorgente utilizzano algoritmi che producono la modifica minimo necessario per trasformare un pezzo di codice sorgente ad un altro - forse vale la pena di loro indagare. Credo che la maggior parte di essi sono basati (eventualmente) sul questo algoritmo , ma è un po 'che ho fatto qualsiasi lettura su questo argomento.

Credo che questo può essere fatto molto più veloce di O (n²) in media (è probabile che l'ingresso può essere progettato per non permettere l'analisi veloce). È possibile considerare le aggiunte o le cancellazioni consecutivi come set. È possibile analizzare una sola operazione alla volta, e si dovrà fare alcune trasformazioni condizionali:

Se un'aggiunta segue un'aggiunta o una serie di aggiunte, potrebbe
- touch (uno o più) del precedente aggiunta (s): allora, è possibile unire queste aggiunte
- non toccare: è possibile ordinare (si dovrà regolare le posizioni)
Se una delezione segue un'aggiunta o una serie di aggiunte, potrebbe
- Elimina solo i caratteri dalla più: allora, è possibile modificare l'aggiunta (a meno che non avrebbe diviso un'aggiunta)
- eliminare solo i caratteri non dal set di aggiunte: allora, è possibile spostare la cancellazione di una posizione prima che il set di aggiunte, e forse si uniscono integrazioni; dopo che l'insieme di delezioni prima della attuale serie di aggiunte potrebbe dover essere applicate alle aggiunte prima che
- fare entrambe le cose: allora, è possibile prima dividerlo in due (o più) delezioni e applicare il relativo metodo
Se una delezione segue una cancellazione, o di una serie di eliminazioni, si può:
- touch (uno o più) la cancellazione precedente (s): allora, è possibile unire queste delezioni
- non toccare: è possibile ordinare (si dovrà regolare le posizioni
- , in ogni caso, è quindi necessario applicare l'analisi delle eliminazioni di nuova formazione sulle integrazioni precedenti
Se un'aggiunta segue una delezione, non è necessaria alcuna trasformazione a questo punto

Questa è solo una prima bozza. Alcune cose possono essere fatto in modo diverso, ad esempio, potrebbe essere più facile o più efficace applicare sempre tutte le delezioni, in modo che il risultato è sempre una sola serie di delezioni seguita da una serie di aggiunte.

Supponiamo per semplicità che solo le lettere a-z appaiono in vostri testi.

inizializzare una lista A con valori a [i] = i per i = 1 a N (si capirà persona come grande N dovrebbe essere).

Esegui (simulare) tutte le operazioni su A. Dopo questa analizzare una per trovare operazioni necessarie:

Fist trovare richiesto operazioni di eliminazione trovando i numeri mancanti in A (formeranno gruppi di valori consecutivi, un gruppo si distingue per un'operazione di eliminazione).

Dopo questo si possono trovare le operazioni di inserimento richiesti trovando le sequenze di consecutiva lettere (una sequenza è un'operazione di inserimento).

Nel tuo esempio:

init A:

1 2 3 4 5 6 7 8 9 10

Fase 1 (+: 2: ab):

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

Step2 (+ 1: CDE):

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

Fase 3 (-: 4: 1):

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

Ora cerchiamo numeri mancanti per trovare le eliminazioni. Nel nostro esempio manca solo un numero (cioè numero 1), in modo che solo 1 di cancellazione è necessario, quindi abbiamo un'operazione di eliminazione: -: 1: 1 (In generale, ci possono essere più numeri mancanti, ogni sequenza di numeri mancanti è un'operazione di eliminazione. Ad esempio, se 1, 2, 3, 5, 6, 10 sono tutti numeri mancanti, quindi ci sono 3 operazioni di eliminazione: -: 1: 3, -: 2: 2, -: 5: 1. Ricordate che dopo ogni operazione di cancellazione tutti gli indici sono diminuiti, è necessario memorizzare somma totale di ex operazioni di eliminazione per calcolare l'indice di operazione di eliminazione in corso.)

Ora cerchiamo sequenze di caratteri per trovare le operazioni di inserimento. Nel nostro esempio v'è una sola sequenza: cdeab a indice 1, quindi abbiamo un'operazione di inserimento: +: 1: cdeab

Spero che questo è abbastanza chiaro.

Come ridurre il numero di azioni: un approccio algoritmico potrebbe tentare di ordinare le azioni. Penso, che dopo la cernita:

La possibilità che le azioni limitrofi possono essere uniti (nel modo Svante e Peterchen mostrato), salirà.
Questo può portare al numero minimo di azioni che devono essere eseguite?

Nel seguente "numero-posizione" sta per la posizione di inserimento o la cancellazione di testo.

Supponendo che è possibile scambiare due azioni confinanti (regolando posizione numeri e text / proprietà length di queste due azioni), siamo in grado di portare l'azione-list per qualsiasi ordine che piace. Suggerisco di portare le azioni di eliminazione per la parte anteriore della lista di azioni con ascendente posizione-numeri. Dopo le azioni di eliminazione l'aggiunta-azioni sono ordinati con ascendente posizione-numeri.

I seguenti esempi dovrebbero dimostrare, perché penso che sia possibile scambiare qualunque azione limitrofi.

swaping seguenti azioni:

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

cede a una sola azione:

  1. + 2 aa  -> taaext

swaping seguenti azioni:

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

cede a:

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

swaping seguenti azioni:

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

cede a:

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

Come primo esempio mostra, in alcuni casi uno scambio provoca la rimozione di una delezione. Questo è un beneficiando effetto collaterale. Questo è anche il motivo per cui la materia vi suggerisco di spostare tutte le eliminazioni alla anteriore.

Mi auguro che non ho dimenticato qualcosa e considerate tutte le circostanze.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow