Risultati sovrapposte lookahead su LZ77/LZSS con alberi suffisso

Question

Priorità: Ho un'implementazione di un back-end LZSS generico C++ (disponibile here L'algoritmo di confronto utilizzato in questa versione è estremamente semplice, in quanto inizialmente doveva. comprimere file relativamente piccoli (al massimo 64kB) per hardware relativamente antico (in particolare, Mega Drive/Sega Genesis, dove 64kB è l'intera RAM principale)

Tuttavia, alcuni file impiegano troppo tempo per comprimersi sulla mia implementazione , nell'ordine dei minuti, il motivo è duplice: l'algoritmo di corrispondenza ingenuo impiega la maggior parte del tempo, ma ciò accade in particolare perché costruisco un grafico di compressione dal file per ottenere un calcolo ottimale sione. Guardando al profiler, la maggior parte del tempo viene speso alla ricerca di corrispondenze, sminuendo anche le dimensioni quadratiche del grafico risultante.

Da un po 'di tempo ho studiato diverse potenziali sostituzioni; uno che ha attirato la mia attenzione era dictionary-symbolwise flexible parsing using multilayer suffix trees. La parte multistrato è importante perché una delle varianti di LZSS che mi interessa utilizza codifiche di dimensione variabile per (posizione, lunghezza).

mio attuale implementazione permette partite nella finestra scorrevole di sovrapporre il buffer look-ahead, in modo che questo input:

aaaaaaaaaaaaaaaa 

possono essere codificati direttamente come

(0,'a')(1,0,15) 

invece di

(0,'a')(1,0,1)(1,0,2)(1,0,4)(1,0,8) 

Qui, (0, 'a') significa codificare il carattere 'a' come letterale, mentre (1, n, m) significa 'copia m caratteri dalla posizione n '.

La domanda: Detto questo, ecco il mio problema: Ogni risorsa che ho trovato su alberi suffisso sembra implicare che non possono gestire il caso di sovrapposizione, e invece consente solo di trovare le partite che non si sovrappongono . Quando sono stati coinvolti gli alberi di suffisso, documenti di ricerca, libri e persino alcune implementazioni hanno fornito esempi di compressione senza sovrapposizione come se fossero una compressione perfetta (collegherei ad alcuni di questi ma la mia reputazione non lo consente). Alcuni hanno anche detto che le sovrapposizioni potrebbero essere utili quando si descrivono gli schemi di compressione di base, ma erano stranamente silenziosi sull'argomento quando si discutevano gli alberi dei suffissi.

Poiché l'albero del suffisso deve essere aumentato per archiviare comunque le informazioni di offset, sembra una proprietà che può essere verificata durante la ricerca di una corrispondenza: si eliminano le corrispondenze che iniziano nel buffer di previsione. E il modo in cui l'albero viene costruito/aggiornato significherebbe che se un fronte ti porta a un nodo che corrisponde a una partita che inizia con il look-ahead, restituisci il nodo precedente invece come qualsiasi altro discendente sarà anche sul look-ahead buffer.

Il mio approccio è errato o errato? Esiste un'implementazione o una discussione di LZ77/LZSS con alberi di suffisso che menzionano le corrispondenze che si sovrappongono al buffer look-ahead?

Answer 1

quanto ho capito, dato un albero di suffissi, siamo interessati (circa) nel settore informatico, per ogni suffisso S, che ha più il suffisso più lungo prefisso comune con S.

Aggiungere un riferimento da ogni nodo della struttura alla foglia discendente con il suffisso più lungo (tempo lineare con DFS). Da ogni foglia, cammina verso il basso, esaminando i nuovi riferimenti, fermandosi se viene trovato un suffisso più lungo. Il tempo di esecuzione di quest'ultima fase è lineare, poiché ciascun bordo dell'albero viene esaminato esattamente una volta.

La vita con una finestra limitata è purtroppo più difficile. Invece di propagare un riferimento, ne propagiamo diversi. Per calcolare il set di suffissi cui fa riferimento un nodo, li uniamo in ordine per lunghezza. Quindi ogni volta che abbiamo suffissi di lunghezze x> y> z, se x - z < 8192 (ad esempio), allora possiamo eliminare y, perché tutti e tre sono ugualmente buoni per tutti i suffissi con i quali il nodo corrente è l'antenato più fogliare e se y è in una finestra, allora x o z è. Poiché la finestra è una grande frazione del file totale, ogni nodo avrà al massimo una manciata di riferimenti.

Se si desidera controllare la distanza più breve possibile, esiste un algoritmo di tempo O (n log^2 n) (probabilmente migliorabile a O (n log n) con varie magie difficili da implementare). Nel corso dell'algoritmo, costruiamo, per ciascun nodo, un albero di ricerca binario dei suffissi discendenti per lunghezza, quindi eseguiamo le ricerche più lunghe del prossimo. Per costruire l'albero del nodo dai suoi childrens, inizia con l'albero figlio più grande e inserisci gli elementi dagli altri. Con un argomento heavy path, ogni lunghezza è inserita O (log n) volte.