Struttura dati più efficiente per aggiungere stili al testo

Question

Sto cercando la migliore struttura dati per aggiungere stili a un testo (ad esempio in un editor di testo). La struttura dovrebbe consentire le seguenti operazioni:

1. ricerca veloce di tutti gli stili a posizione assoluta X
2. inserimento rapido del testo in qualsiasi posizione (stili dopo quella posizione devono essere spostati).
3. Ogni posizione del testo deve supportare un numero arbitrario di stili (sovrapposti).

Ho considerato liste/matrici che contengono intervalli di testo ma non consentono l'inserimento rapido senza ricalcolare le posizioni di tutti gli stili dopo il punto di inserimento.

Una struttura ad albero con offset relativo supporta # 2 ma l'albero degenererà rapidamente quando aggiungo molti stili al testo.

Altre opzioni?

Answer 1

ho mai sviluppato un editore, ma come su questo:

Credo che sarebbe stato possibile ampliare lo schema che viene utilizzata per memorizzare i caratteri di testo themeselves, a seconda ovviamente i dettagli della tua applicazione (lingua, toolkit ecc.) e i requisiti di utilizzo delle risorse e delle prestazioni.

Anziché utilizzare una struttura dati separata per gli stili, preferirei avere un riferimento che accompagnasse ogni carattere e indicasse una matrice o un elenco con i caratteri applicabili. I personaggi con lo stesso set di stili potrebbero puntare allo stesso array o elenco, in modo che uno possa essere condiviso.

Gli inserimenti e le eliminazioni di caratteri non influiscono sugli stili in questione, oltre a modificare il numero di riferimenti ad essi, che potrebbero essere gestiti con un po 'di conteggio dei riferimenti.

A seconda del linguaggio di programmazione, è possibile comprimere le cose un po 'di più puntando a metà strada in un elenco, anche se la contabilità aggiuntiva potrebbe in effetti renderla più inefficiente.

Il problema principale con questo suggerimento è l'utilizzo della memoria. In un editor ASCII scritto in C, il raggruppamento di un puntatore con ciascun char aumenterebbe l'utilizzo della memoria effettiva da 1 byte a 12 byte su un sistema a 64 bit, a causa del riempimento dell'allineamento della struttura.

Vorrei analizzare il testo in blocchi di dimensioni variabili che consentissero di comprimere in modo efficiente i puntatori. Per esempio. un blocco di 32 caratteri potrebbe apparire come questo in C:

struct _BLK_ { 
    unsigned char size; 
    unsigned int styles; 
    char content[]; 
} 

La parte interessante è l'elaborazione dei metadati sulla parte variabile della struct, che contiene sia il testo memorizzato e tutti gli indicatori di stile. L'elemento dimensione indica il numero di caratteri. Il numero intero di stili (da cui il limite di 32 caratteri) verrebbe visto come un insieme di 32 campi a 1 bit, ognuno dei quali indica se un personaggio ha il proprio puntatore di stile o se deve utilizzare lo stesso stile del carattere precedente. In questo modo un blocco a 32 caratteri con un solo stile avrebbe solo il sovraccarico aggiuntivo della dimensione char, la maschera di stili e un singolo puntatore, insieme a qualsiasi byte di riempimento. Inserire e cancellare caratteri in un piccolo array come questo dovrebbe essere abbastanza veloce.

Per quanto riguarda l'archiviazione del testo, un albero sembra una buona idea.Forse un albero binario in cui ogni valore di nodo sarebbe la somma dei valori figli, con i nodi foglia che alla fine puntano a blocchi di testo con le loro dimensioni come valore del loro nodo? Il valore del nodo radice sarebbe la dimensione totale del testo, con ogni sottotree che contiene idealmente metà del testo. Dovresti comunque bilanciarlo automaticamente, con a volte dover unire blocchi di testo semivuoti.

E nel caso ve lo siete perso, non sono un esperto in alberi :-)

EDIT:

A quanto pare quello che ho suggerito è una versione modificata di questa struttura dati:

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

come riferimento in questo post:

Data structure for text editor

EDIT 2:

La cancellazione nella struttura dati proposta dovrebbe essere relativamente veloce, in quanto si verificherebbe lo spostamento dei byte in una matrice e alcune operazioni bit a bit sulla maschera degli stili. L'inserimento è praticamente lo stesso, a meno che non si riempia un blocco. Potrebbe avere senso riservare uno spazio (cioè alcuni bit nella maschera degli stili) all'interno di ciascun blocco per consentire inserimenti futuri direttamente nei blocchi, senza dover modificare l'albero stesso per quantità relativamente piccole di nuovo testo.

Un altro vantaggio di raggruppare caratteri e stili in blocchi di questo tipo è che la relativa località di dati dovrebbe consentire un uso più efficiente della cache della CPU rispetto ad altre alternative, migliorando in tal modo la velocità di elaborazione.

Analogamente a qualsiasi struttura di dati complessa, tuttavia, probabilmente sarà necessario eseguire il profiling con casi di test rappresentativi o un algoritmo adattivo per determinare i parametri ottimali per il suo funzionamento (dimensione del blocco, spazio riservato, ecc.).