Algoritmo per trovare corrispondenze di stringhe in una finestra scorrevole

Question

Uno dei passaggi fondamentali nella compressione dei file come ZIP è usare il testo decodificato precedente come fonte di riferimento. Ad esempio, il flusso codificato potrebbe dire "i successivi 219 caratteri di output sono gli stessi dei caratteri del flusso decodificato 5161 byte fa." Ciò consente di rappresentare 219 caratteri con solo 3 byte circa. (C'è di più in ZIP di quello, come la compressione di Huffman, ma sto solo parlando della corrispondenza di riferimento.)

La mia domanda è quale sia la strategia per l'algoritmo di abbinamento delle stringhe. Anche guardando il codice sorgente da zlib e simili non sembrano dare una buona descrizione dell'algoritmo di corrispondenza della compressione.

Il problema potrebbe essere indicato come: dato un blocco di testo, diciamo 30K di esso, e una stringa di input, trova il riferimento più lungo nei 30K di testo che corrisponde esattamente alla parte anteriore dell'input . stringa " L'algoritmo deve essere efficiente quando viene ripetuto, ovvero il blocco di testo da 30 KB verrà aggiornato eliminando alcuni byte dalla parte anteriore e aggiungendone di nuovi alla parte posteriore e una nuova corrispondenza eseguita.

Sono molto più interessato alle discussioni sugli algoritmi per farlo, sul non codice sorgente o sulle librerie. (zlib ha un'ottima fonte!) Ho il sospetto che potrebbero esserci diversi approcci con diversi compromessi.

Answer 1

Potresti guardare i dettagli dell ' LZMA Algorithm usato da 7-zip . L'autore di 7-zip afferma di aver migliorato l'algoritmo utilizzato da zlib et al.

Answer 2

Bene, noto che vai nei dettagli del problema ma non menzioni le informazioni fornite nella sezione 4 di RFC 1951 (la specifica per DEFLATE Compressed Data Format, ovvero il formato utilizzato in ZIP) che mi porta a credere che potresti aver perso questa risorsa.

Il loro approccio di base è una tabella hash concatenata che utilizza sequenze di tre byte come chiavi. Fintanto che la catena non è vuota, tutte le voci lungo di essa vengono scansionate per a) eliminare false collisioni, b) eliminare corrispondenze troppo vecchie ec) selezionare la corrispondenza più lunga tra quelle rimanenti.

(Nota che la loro raccomandazione è modellata dal fattore dei brevetti; può darsi che conoscessero una tecnica più efficace ma non potessero essere sicuri che non fosse coperta dal brevetto di qualcuno. Personalmente, mi sono sempre chiesto perché uno non è stato possibile trovare le corrispondenze più lunghe esaminando le corrispondenze per le sequenze a tre byte che iniziano con il secondo byte dei dati in entrata, il terzo byte, ecc. e eliminando le corrispondenze che non corrispondono. Ad esempio, se si riceve i dati sono "ABCDEFG ..." e hai corrispondenze hash per "ABC" agli offset 100, 302 e 416 ma la tua unica corrispondenza hash per "BCD" è all'offset 301, sai che a meno che tu non abbia due partite di hash sovrapposte del tutto coincidenti - improbabile - quindi 302 è la partita più lunga.)

Nota anche la loro raccomandazione di "corrispondenza pigra" facoltativa " (che ironicamente fa più lavoro): invece di prendere automaticamente la corrispondenza più lunga che inizia al primo byte dei dati in arrivo, il compressore verifica una corrispondenza ancora più lunga a partire dal byte successivo. Se i tuoi dati in arrivo sono " ABCDE ... " e le tue uniche corrispondenze nella finestra scorrevole sono per " ABC " e per "BCDE", è meglio codificare la "A" come byte letterale e il "BCDE" come una partita.

Answer 3

Penso che stai descrivendo una versione modificata del Problema di sottostring comune più lungo .