Compressione dati(compressione dei dati) - una tecnica per ridurre il volume (dimensione) della registrazione dei dati sul loro supporto (disco rigido magnetico, disco floppy, nastro magnetico); implementato con metodi diversi, principalmente utilizzando la codifica (parole ripetute, frasi, simboli). Si possono distinguere due gruppi di modalità di compressione dei dati: statica e dinamica; distinguere anche tra compressione fisica e logica; compressione simmetrica e asimmetrica; codifica adattiva, semiadattativa e non adattiva; compressione lossless, lossy e lossless. Metodi (tipi) di compressione dei dati:

Compressione dati statica: utilizzata per l'archiviazione e l'archiviazione a lungo termine; eseguita utilizzando speciali programmi di archiviazione del servizio, ad esempio ARJ, PKZIP / PKUNZIP. Dopo il ripristino (decompressione), viene ripristinata la registrazione originale.
La compressione dinamica (compressione in tempo reale; compressione dinamica, compressione in tempo reale) è progettata per ridurre l'area occupata della memoria del disco con dati che richiedono un accesso rapido e l'output su dispositivi esterni (incluso lo schermo del monitor). La compressione e il ripristino dinamici dei dati vengono eseguiti automaticamente e "istantaneamente" da speciali strumenti software.
La compressione fisica è una metodologia di compressione in cui i dati vengono riorganizzati in una forma più compatta "formalmente", cioè senza tener conto della natura delle informazioni che contengono.
La compressione logica è una metodologia in cui un insieme di caratteri alfabetici, numerici o binari viene sostituito da un altro. In questo caso, viene preservato il significato semantico dei dati originali. Un esempio è la sostituzione di una frase con la sua abbreviazione. La compressione logica viene eseguita a livello simbolico o superiore e si basa esclusivamente sul contenuto dei dati originali. La compressione logica non viene applicata alle immagini.
La compressione simmetrica è una metodologia di compressione in base alla quale i principi di costruzione di algoritmi per l'impacchettamento e l'estrazione dei dati sono vicini o strettamente correlati. Con la compressione simmetrica, il tempo necessario per comprimere e decomprimere i dati è commisurato. La compressione simmetrica è comunemente usata nei programmi di comunicazione.
La compressione asimmetrica è una metodologia in base alla quale viene impiegato più tempo quando si esegue il lavoro "in una direzione" rispetto a quando si esegue il lavoro nell'altra direzione. La compressione delle immagini di solito richiede molto più tempo e risorse di sistema rispetto alla loro decompressione. L'efficacia di questo approccio è determinata dal fatto che le immagini possono essere compresse solo una volta e decompresse per visualizzarle, molte volte. Algoritmi asimmetrici "nella direzione opposta" (la compressione dei dati richiede meno tempo della decompressione) viene utilizzato durante l'esecuzione di un backup dei dati.
La codifica adattiva è una metodologia di codifica a compressione che non è preconfigurata per un tipo specifico di dati. I programmi che utilizzano la codifica adattiva sono sintonizzati su qualsiasi tipo di dati comprimibili, ottenendo la massima riduzione del loro volume.
Codifica non adattiva: una metodologia di codifica incentrata sulla compressione di un tipo o più tipi di dati specifici. I codificatori basati su questo principio includono dizionari statici di "sottostringhe predefinite" che sono note per apparire frequentemente nei dati da codificare. Un esempio è il metodo di compressione di Huffman.
La codifica semiadattativa è una metodologia di codifica a compressione che utilizza elementi di codifica adattivi e non adattivi. Il principio della codifica semi-adattiva è che il codificatore esegue due gruppi di operazioni: prima, visualizza l'array di dati codificati e crea un dizionario per essi, quindi la codifica effettiva.
La compressione senza perdita di dati è una metodologia di compressione in cui un pezzo di dati precedentemente codificato viene recuperato dopo averlo decompresso completamente senza apportare modifiche.
La compressione con perdita è una metodologia in cui parte dei dati in essa contenuti viene scartata per garantire il massimo rapporto di compressione dell'array originale. Per dati di testo, numerici e tabulari, l'uso di programmi che implementano tali metodi di compressione è inaccettabile. Tuttavia, per i programmi che lavorano con la grafica, questo è spesso utile. La qualità dell'immagine restaurata dipende dalla natura del materiale grafico e dalla correttezza dell'algoritmo di compressione implementato nel programma. Esistono numerosi algoritmi di compressione che tengono conto dei livelli ammissibili di perdita dell'immagine grafica originale in casi d'uso specifici dell'immagine recuperata, ad esempio visualizzandola su un monitor, stampandola con una stampante o stampando . Questi metodi sono indicati collettivamente come compressione che riduce al minimo le perdite.
La compressione delle immagini è una tecnica o un metodo per ridurre il volume (dimensione) della registrazione di immagini grafiche (figure, disegni, diagrammi) sul loro supporto (ad esempio, su un disco magnetico, nastro magnetico). In sostanza, la "compressione dell'immagine" è una forma di compressione dinamica. Per la sua implementazione vengono utilizzati vari metodi di codifica dei dati, che si concentrano sugli elementi grafici che compongono l'immagine, inclusi gli oggetti in movimento. Viene anche utilizzato nella trasmissione di informazioni fax attraverso canali di comunicazione, in sistemi multimediali, videotelefoni.
La compressione del disco è una tecnica basata sulla compressione dinamica nel processo di scrittura sul disco e durante la lettura vengono ripristinati automaticamente alla loro forma originale. La compressione del disco viene utilizzata per aumentare la capacità di un disco. A seconda della natura delle registrazioni, la capacità del disco può essere aumentata da circa 1,5 a 5 volte. La compressione del disco viene eseguita da programmi applicativi speciali, ad esempio DoubleSpace, Stacker, SuperStor.

Metodi e strumenti di compressione dei dati:
Il metodo di compressione Huffman (codifica CCITT) è stato sviluppato nel 1952 da David Huffman. L'International Consultative Committee on Telephony and Telegraphy (CCITT) ha sviluppato sulla sua base una serie di protocolli di comunicazione per la trasmissione fax di immagini in bianco e nero su canali telefonici e reti dati (standard T.4 CCIT e T.6 CCITT, essi sono anche la compressione del gruppo CCITT 3 e la compressione del gruppo CCITT 4).
La compressione frattale è un metodo per comprimere le immagini raster convertendole nei cosiddetti frattali. La memorizzazione delle immagini sotto forma di frattali richiede una memoria su disco quattro volte inferiore rispetto ai pixel.
ART è un metodo per comprimere testo, grafica, audio e video. Il principio di funzionamento dell'algoritmo di compressione si basa sull'analisi dell'immagine e sull'identificazione delle sue caratteristiche chiave (colore, rumore, bordi, caratteristiche ripetitive).
AC3 Dolby è un metodo e formato di compressione che consente di comprimere, archiviare e trasmettere in un file a una velocità da 32 a 640 kbps fino a 6 canali di dati audio.
DJVU (DjVu, djvu, deja vu) è una tecnologia e un formato per la compressione dinamica delle pagine scansionate di pubblicazioni contenenti testo e materiale illustrativo.
DVI (Digital Video Interactive) è un sistema per la compressione dinamica e il ripristino di registrazioni audio e video in formato digitale. Il suo utilizzo consente di registrare un film video completo insieme alla colonna sonora su un CD-ROM.
EAD (Encoded Archival Description) è uno standard di codifica sviluppato dal Network Development and MARC Standards Office della Library of Congress in collaborazione con la Society of American Archivists nel 1998 (aggiornato nel 2002). Lo standard stabilisce i principi per la creazione, lo sviluppo e il mantenimento di schemi di codifica per ausili per la ricerca di archivi e biblioteche.
Image compression manager è un programma di gestione della compressione delle immagini dinamico che offre la possibilità di utilizzare vari metodi di compressione/ripristino per le immagini (MPEG, JPEG).
JBIG (Joint Bi-level Image Experts Group) è un metodo di compressione delle immagini a due livelli (bicolore) senza perdita di dati creato da Joint Bi-level Image Experts ISO e CCIT nel 1988. Il metodo JBIG è stato approvato nel 1993 come standard di codifica dei dati a due livelli invece dei meno efficienti algoritmi di compressione MR (Modified READ) e MMR (Modified Modified READ).
LZW (Lempel-Ziv-Welch) è un metodo di compressione dinamico basato sulla ricerca dell'intero file e sulla memorizzazione delle stesse sequenze di dati nel dizionario (si chiamano frasi). Token più brevi (chiavi) vengono assegnati a ciascuna sequenza di dati univoca.
MP3 (Moving Pictures Experts Group, Layer 3) è un metodo di compressione dinamica (algoritmo) e un formato speciale per la registrazione di file di dati audio. MP3 fornisce un elevato rapporto di compressione per le registrazioni audio e viene utilizzato in applicazioni multimediali come lettori digitali e Internet.
RLE (Run Length Encoding) è un metodo di compressione dinamica di dati grafici, principalmente immagini, basato sulla riduzione della dimensione fisica delle stringhe di caratteri ripetute.

Inviare il tuo buon lavoro nella knowledge base è semplice. Usa il modulo sottostante

Studenti, dottorandi, giovani scienziati che utilizzano la base di conoscenza nei loro studi e nel lavoro ti saranno molto grati.

Pubblicato su http://www.allbest.ru/

Compressione dati

1. Informazione. I suoi tipi e proprietà

In letteratura si possono trovare molte definizioni del termine "informazione", che riflettono diversi approcci all'interpretazione di questo concetto. Il dizionario esplicativo della lingua russa Ozhegov fornisce 2 definizioni della parola "informazione":

Informazioni sul mondo circostante e sui processi che si verificano in esso, percepite da una persona o da un dispositivo speciale.

Messaggi che informano sullo stato delle cose, sullo stato di qualcosa. (Informazione scientifica, tecnica e giornalistica, mass media - stampa, radio, televisione, cinema).

L'informazione e le sue proprietà sono oggetto di studio di numerose discipline scientifiche, come la teoria dell'informazione (la teoria matematica dei sistemi di trasmissione dell'informazione), la cibernetica (la scienza della comunicazione e del controllo nelle macchine e negli animali, nonché nella società e nell'uomo esseri umani), semiotica (scienza dei segni e dei sistemi segnici), teoria della comunicazione di massa (studio dei media e del loro impatto sulla società), informatica (studio dei processi di raccolta, trasformazione, conservazione, protezione, ricerca e trasmissione di tutti tipi di informazioni e mezzi della loro elaborazione automatizzata), fisica e matematica.

Le informazioni hanno un duplice carattere: materiale: possono essere trasmesse, archiviate, ecc .; e immateriale - secondo lo zolfo di trasmissione, può essere reintegrato. L'informazione non può esistere senza il suo supporto materiale, un mezzo per trasferirla nello spazio e nel tempo. L'oggetto fisico stesso o il suo equivalente energetico può fungere da vettore di segnali sonori, luminosi, elettrici e di altro tipo.

Per questo, attualmente, sono stati inventati molti metodi per memorizzare informazioni su portatori esterni (relativi al cervello umano) e trasmetterle a grandi distanze.

I principali tipi di informazioni nella sua forma di presentazione, metodi di codifica e memorizzazione, che è della massima importanza per l'informatica, sono:

· grafico o pittorico - il primo tipo per il quale è stato implementato un metodo di memorizzazione delle informazioni sul mondo circostante sotto forma di pitture rupestri, e successivamente sotto forma di dipinti, fotografie, diagrammi, disegni su carta, tela, marmo e altri materiali raffiguranti immagini del mondo reale;

· suono- il mondo che ci circonda è pieno di suoni e il compito di immagazzinarli e riprodurli è stato risolto con l'invenzione dei dispositivi di registrazione del suono nel 1877; il suo genere è l'informazione musicale - per questo tipo è stato inventato un metodo di codifica utilizzando caratteri speciali, che consente di memorizzarlo allo stesso modo delle informazioni grafiche;

· testo- un metodo per codificare il discorso di una persona con caratteri speciali - lettere e persone diverse hanno lingue diverse e usano diversi set di lettere per visualizzare il discorso; questo metodo divenne particolarmente importante dopo l'invenzione della carta e della stampa di libri;

· numerico- una misura quantitativa degli oggetti e delle loro proprietà nel mondo circostante; acquisì particolare importanza con lo sviluppo del commercio, dell'economia e degli scambi monetari; analogamente alle informazioni di testo, per visualizzarle, viene utilizzato il metodo di codifica con caratteri speciali: i numeri e i sistemi di codifica (numeri) possono essere diversi;

· informazioni video- un modo di preservare le immagini "viventi" del mondo circostante, apparso con l'invenzione del cinema.

Per trasmettere informazioni su lunghe distanze, sono stati originariamente utilizzati segnali luminosi codificati, con l'invenzione dell'elettricità - trasmissione di un segnale codificato su fili e, successivamente - utilizzando onde radio.

Con l'avvento dei computer (o, come furono inizialmente chiamati nel nostro paese, computer - computer elettronici), apparve per la prima volta un mezzo per elaborare le informazioni numeriche. Tuttavia, in futuro, soprattutto dopo l'uso diffuso dei personal computer (PC), i computer hanno iniziato a essere utilizzati per l'archiviazione, l'elaborazione, la trasmissione e la ricerca di informazioni testuali, numeriche, visive, audio e video. Dall'apparizione dei primi personal computer - PC (anni '80 del XX secolo) - fino all'80% del loro tempo di lavoro è dedicato al lavoro con le informazioni di testo.

La memorizzazione delle informazioni durante l'utilizzo dei computer viene eseguita su dischi o nastri magnetici, su dischi laser (CD e DVD), dispositivi di memoria non volatili speciali (memoria flash, ecc.). Questi metodi vengono costantemente migliorati, vengono inventati nuovi dispositivi e supporti di informazioni. L'elaborazione delle informazioni (riproduzione, trasformazione, trasmissione, registrazione su supporti esterni) viene eseguita dal processore del computer. Con l'aiuto di un computer, è possibile creare e memorizzare nuove informazioni di qualsiasi tipo, per le quali vengono utilizzati programmi speciali utilizzati su computer e dispositivi di input di informazioni.

Un tipo speciale di informazioni attualmente può essere considerato informazioni presentate in Internet globale. Utilizza tecniche speciali per l'archiviazione, l'elaborazione, la ricerca e il trasferimento di informazioni distribuite di grandi volumi e metodi speciali per lavorare con vari tipi di informazioni. Il software viene costantemente migliorato, il che garantisce il lavoro collettivo con informazioni di ogni tipo.

Proprietà delle informazioni

Si possono citare molte proprietà differenti delle informazioni. Ogni disciplina scientifica considera quelle che sono più importanti per essa. Dal punto di vista informatico, le seguenti proprietà sembrano essere le più importanti:

1. Oggettività e soggettività dell'informazione. Più oggettiva è considerata l'informazione in cui i metodi introducono un elemento soggettivo minore. Nel corso del processo informativo, il grado di obiettività dell'informazione diminuisce sempre.

2. Completezza delle informazioni. La completezza delle informazioni caratterizza in gran parte la qualità delle informazioni e determina la sufficienza dei dati per prendere decisioni o per creare nuovi dati basati su dati esistenti.

3. Affidabilità delle informazioni. I dati appaiono al momento della registrazione dei segnali, ma non tutti i segnali sono "utili" - c'è sempre un livello di segnali estranei.

5. Disponibilità di informazioni.

6. Rilevanza.

2. Compressione dati

È una regola ben nota nel mondo dei computer che non c'è mai molta capacità del disco rigido. In effetti, è difficile non essere d'accordo con lui: non importa quanto grande possa sembrare il disco rigido quando lo acquisti, viene rapidamente intasato da tutte le informazioni non necessarie. Dal momento che è un peccato eliminare tutto, vale la pena il tempo e il tempo per "memorizzare" tutta questa roba in una sorta di repository, archivio.

CONcompressione dati- la procedura di ricodifica dei dati, effettuata al fine di ridurne il volume. Viene utilizzato per un uso più razionale dei dispositivi di archiviazione e trasmissione dei dati. Se i metodi di compressione delle informazioni vengono applicati ai documenti finiti, il termine "compressione dei dati" viene spesso sostituito dal termine "archiviazione dei dati".

La compressione si basa sull'eliminazione della ridondanza delle informazioni contenute nei dati originali. Un esempio di ridondanza è la ripetizione di frammenti nel testo (ad esempio parole di linguaggio naturale o macchina). Questa ridondanza viene solitamente eliminata sostituendo la sequenza ripetuta con un valore più breve (codice). Un altro tipo di ridondanza è legato al fatto che alcuni valori nei dati compressi si verificano più spesso di altri, mentre è possibile sostituire i dati ricorrenti con codici più brevi, e quelli rari con codici più lunghi (compressione probabilistica). La compressione di dati che non hanno la proprietà di ridondanza (ad esempio, segnale casuale o rumore) è impossibile senza perdita. Inoltre, di solito è impossibile comprimere le informazioni crittografate.

Algoritmi di compressione per testi/file di formato sconosciuto

Esistono 2 approcci principali alla compressione di file di formato sconosciuto.

Ad ogni passaggio dell'algoritmo di compressione, o il carattere successivo viene posizionato così com'è (con un contrassegno speciale che indica che non è compresso), oppure vengono indicati i limiti di parola del blocco precedente, che coincide con i caratteri successivi nel file . Decomprimere i file compressi in questo modo è molto veloce, quindi questi algoritmi vengono utilizzati per creare programmi autoestraenti.

Per ogni sequenza, vengono raccolte le statistiche della sua occorrenza nel file in ogni momento. Sulla base di queste statistiche, viene calcolata la probabilità dei valori per il simbolo successivo. Successivamente, è possibile applicare uno o un altro tipo di codifica entropica, ad esempio la codifica aritmetica o la codifica di Huffman per sostituire le sequenze frequenti con quelle più corte e quelle che si verificano raramente con quelle più lunghe.

La compressione è lossless (quando è possibile recuperare i dati originali senza distorsione) o lossy (il recupero è possibile con distorsioni insignificanti dal punto di vista dell'ulteriore utilizzo dei dati recuperati). La compressione senza perdite viene solitamente utilizzata nell'elaborazione di programmi e dati per computer, meno spesso, per ridurre il volume di informazioni audio, foto e video. La compressione con perdita viene utilizzata per ridurre il volume delle informazioni audio, foto e video, è molto più efficiente della compressione senza perdita.

3. Software di compressione dati

Se i metodi di compressione delle informazioni vengono applicati ai documenti finiti. Cioè spesso il termine "compressione dati" viene sostituito dal termine "archiviazione dati", e il software che esegue queste operazioni viene chiamato archiviatori.

Gli archivi sono progettati per comprimere i file, ad es. per ridurre lo spazio su disco che occupano. Consentono, grazie a metodi speciali di impacchettamento delle informazioni, di comprimere le informazioni sui dischi, creando copie dei file in un unico file di archivio. Nonostante il fatto che la quantità di memoria del computer sia in costante crescita, la necessità di archiviazione non diminuisce.

Quindi, l'archiviazione può tornare utile:

1) Quando si memorizzano copie di file e dischi floppy, perché il disco floppy ha dimensioni limitate;

2) Per liberare spazio sul disco rigido;

3) Quando si trasferiscono informazioni in rete.

L'archiviazione delle informazioni è una tale trasformazione dell'informazione in cui il suo volume non diminuisce, ma la quantità di informazioni rimane la stessa.

Il file compresso è chiamato archivio. Un file di archivio è un file appositamente organizzato contenente uno o più file in formato compresso e non compresso e informazioni di servizio sui loro nomi.

Il livello di compressione delle informazioni dipende dal tipo di file sorgente, dal programma utilizzato e dal metodo di compressione selezionato. I file di oggetti grafici, file di testo e file di dati per i quali il rapporto di compressione può raggiungere il 5-40% sono compressi meglio, i file di programmi eseguibili e moduli di caricamento sono compressi meno -60-90%.

Vari sviluppatori hanno creato molti programmi di archiviazione. Tra questi, i più comuni per Windows sono WINRAR, WINZIP.

Per la sua popolarità, l'archiviatore WinRAR , senza dubbio, è al primo posto in Russia e uno dei primi in tutto il mondo. L'archiviatore è stato sviluppato da Evgeny Roshal nel 2003. Il programma prevede la gestione completa dei file negli archivi, il ripristino degli archivi danneggiati, la crittografia, la creazione di archivi autoestraenti e multivolume.

WinZip è uno dei programmi più popolari su Internet, che raccoglie un numero significativo di premi da varie pubblicazioni informatiche in tutto il mondo.

Zip stesso: l'algoritmo è utilizzato liberamente in dozzine di programmi, tuttavia, per molti utenti Windows, è WinZip il programma standard per lavorare con gli archivi. Gli strumenti di elaborazione dell'archivio WinZIP integrati consentono di comprimere, visualizzare ed estrarre file da formati di archivio ampiamente utilizzati come ZIP, CAB, Microsoft Compress, GZIP, TAR, ecc. WinZip è molto semplice e facile da usare.

Tuttavia, non è sempre giustificato utilizzare archivi separati con le proprie shell grafiche. La shell più conveniente per gli archiviatori è un normale file manager, ad esempio Windows Commander, che ha la capacità di visualizzare e decomprimere i file di archivio nei formati ZTP, ARJ, RAR, TAR, GZ, CAB, ACE. Tuttavia, la maggior parte delle operazioni con i file, inclusi gli archivi, vengono eseguite in tali gestori.

4. Compressione dati con perdita

Compressione dati con perditaè un metodo di compressione dei dati in cui il file decompresso è diverso dall'originale, ma "abbastanza vicino" per essere utile in qualche modo. Questo tipo di compressione è comunemente usato su Internet, specialmente nello streaming di dati e telefonia. Questi metodi sono spesso indicati come codec in questo contesto. Un'alternativa è la compressione senza perdite.

Tipi di compressione con perdita

Esistono due principali schemi di compressione con perdita di dati:

Nei codec di trasformazione, vengono presi fotogrammi di immagini o suoni, tagliati in piccoli segmenti, trasformati in un nuovo spazio di base e quantizzati. Il risultato viene quindi compresso con metodi entropici.

Nei codec predittivi, i dati precedenti e/o successivi vengono utilizzati per prevedere il fotogramma corrente di un'immagine o di un suono. L'errore tra i dati previsti e i dati reali, insieme alle informazioni aggiuntive necessarie per produrre la previsione, viene quindi quantizzato e codificato.

In alcuni sistemi, queste due tecniche vengono combinate utilizzando codec di trasformazione per comprimere i segnali errati generati durante la fase di previsione.

Compressione con perdita o senza perdita

Il vantaggio dei metodi di compressione con perdita rispetto ai metodi di compressione senza perdita è che i primi sono significativamente superiori nel rapporto di compressione, pur continuando a soddisfare i requisiti specificati.

Le tecniche di compressione con perdita sono spesso utilizzate per comprimere audio o immagini.

In tali casi, il file decompresso può essere molto diverso dall'originale a livello di confronto bit per bit, ma praticamente indistinguibile dall'orecchio o dall'occhio umano nella maggior parte delle applicazioni pratiche.

Molti metodi si concentrano sulle caratteristiche strutturali degli organi di senso umani. Il modello psicoacustico determina la forza con cui il suono può essere compresso senza degradare la qualità del suono percepito. Gli svantaggi causati dalla compressione con perdita visibili all'orecchio o all'occhio umano sono noti come artefatti da compressione.

I dati audio compressi con perdita di dati non sono accettati dai tribunali come prova (e non vengono nemmeno presi in considerazione) a causa del fatto che le informazioni compresse acquisiscono artefatti di compressione e perdono il rumore naturale dell'ambiente da cui è stata effettuata la registrazione. A questo proposito, è impossibile stabilire se la registrazione sia genuina o sintetizzata. Pertanto, si consiglia di effettuare registrazioni importanti in formato PCM o utilizzare un registratore.

Le foto registrate in formato JPEG possono essere accettate dal tribunale (anche se i dati sono compressi con perdita di dati). Ma allo stesso tempo va fornita la fotocamera con cui sono stati realizzati, o la corrispondente fototabella di resa cromatica.

Tecniche di compressione dei dati con perdita

v Compressione dell'immagine:

· Diminuzione della profondità del colore;

· Metodologia dei componenti principali;

· Compressione frattale;

v Compressione video:

· Flash (supporta anche immagini JPEG in movimento);

MPEG-1 Parte 2;

MPEG-2 Parte 2;

MPEG-4 Parte 2;

v Compressione audio:

MP3 - Definito dalla specifica MPEG-1;

· Ogg Vorbis (nessuna restrizione di brevetto e qualità superiore);

· AAC, AAC+ - esiste in diverse varianti definite dalle specifiche MPEG-2 e MPEG-4, utilizzate, ad esempio, in Apple Computer;

· EAAC + - un formato offerto da Sony, in alternativa ad AAC e AAC +;

WMA è di proprietà di Microsoft;

perdita dell'archiviatore di compressione delle informazioni

5. Compressione dei dati senza perdita di dati

Compressione senza perdite(Compressione dei dati senza perdita di dati in inglese) è un metodo di compressione delle informazioni, quando si utilizza il quale le informazioni codificate possono essere ripristinate con precisione in bit. In questo caso, i dati originali vengono completamente ripristinati dallo stato compresso. Questo tipo di compressione è fondamentalmente diverso dalla compressione dei dati con perdita. Per ogni tipo di informazione digitale, di norma, esistono algoritmi di compressione lossless ottimali.

La compressione dei dati senza perdite viene utilizzata in molte applicazioni. Ad esempio, viene utilizzato nel popolare formato di file ZIP e nell'utility Unix Gzip. Viene anche utilizzato come componente nella compressione con perdita.

La compressione senza perdita di dati viene utilizzata quando è importante che i dati compressi siano identici all'originale. Esempi comuni sono gli eseguibili e il codice sorgente. Alcuni formati di file grafici, come PNG o GIF, utilizzano solo la compressione senza perdita di dati; mentre altri (TIFF, MNG) possono utilizzare la compressione con perdita o con perdita.

Tecnica di compressione senza perdite

Dalla combinatoria segue che non esiste un algoritmo di compressione senza perdita di dati in grado di ridurre qualsiasi file di almeno un byte. Tuttavia, questo non è un segno della qualità dell'algoritmo di compressione: l'algoritmo dovrebbe funzionare in modo efficace sui dati per cui è progettato.

Gli algoritmi di compressione multiuso si differenziano per il fatto che sono in grado di ridurre un'ampia gamma di dati: file eseguibili, file di dati, testi, grafici, ecc. e sono utilizzati negli archivi. Algoritmi specializzati sono progettati per un certo tipo di file (testo, grafica, suono, ecc.), ma comprimono tali file in modo molto più forte. Ad esempio: gli archiviatori comprimono l'audio di circa un terzo (1,5 volte), mentre FLAC - 2,5 volte. La maggior parte degli algoritmi specializzati sono di scarsa utilità per i file di tipo "straniero": ad esempio, i dati audio sono scarsamente compressi da un algoritmo progettato per i testi.

La maggior parte degli algoritmi di compressione lossless funziona in due fasi: la prima genera un modello statistico per i dati in entrata, la seconda visualizza i dati in entrata in rappresentazione a bit, utilizzando il modello per ottenere dati "probabilistici" (cioè comuni) che vengono utilizzati più spesso che "improbabile"...

I modelli statistici di algoritmi per testo (o dati binari testuali come gli eseguibili) includono:

Trasformazione di Burrows-Wheeler (pre-elaborazione di ordinamento dei blocchi che rende la compressione più efficiente)

LZ77 e LZ78 (usato da DEFLATE)

Algoritmi di codifica attraverso la generazione di sequenze di bit:

Algoritmo di Huffman (usato anche da DEFLATE)

Codifica aritmetica

Tecniche di compressione senza perdite

Multiuso

Codifica run-length: uno schema semplice che offre una buona compressione dei dati che contengono molti valori ripetitivi

· LZW - utilizzato in gif e molti altri.

· Deflate — Utilizzato in gzip, una versione migliorata di zip, e come parte del processo di compressione PNG.

· LZMA - Usato in 7-zip.

v Compressione audio:

Apple Lossless - ALAC (Codec audio Apple Lossless);

· Codifica Audio Lossless - nota anche come MPEG-4 ALS;

Trasferimento diretto in streaming - DST;

Codec audio senza perdita gratuito - FLAC;

v Compressione della grafica

ABO - Ottimizzazione binaria adattiva;

· GIF - (senza perdita di dati solo per immagini contenenti meno di 256 colori);

JBIG2 - (con o senza immagini B/N con perdita);

· JPEG-LS - (standard di compressione lossless/quasi lossless);

· JPEG 2000 - (include compressione senza perdita di dati; testato anche da Sunil Kumar, professore alla San Diego State University);

· PGF - File Grafici Progressivi (compressione con/senza perdita);

PNG - Grafica di rete portatile;

· WMPhoto - (incluso il metodo di compressione senza perdita di dati);

v Compressione video

Codec di animazione

· Codec video CamStudio;

6. Archiviazione delle informazioni (testo, grafica, suono)

L'archiviazione delle informazioni avviene con l'aiuto di determinati supporti di informazioni. Una persona memorizza la sua conoscenza nella propria memoria o su un supporto esterno.

All'inizio, una persona usava la sua memoria per archiviare e accumulare informazioni: ricordava semplicemente le informazioni ricevute e le ricordava per qualche tempo. A poco a poco, le persone sono giunte alla conclusione che questo modo di memorizzare le informazioni presenta una serie di svantaggi. Rendendosi conto di tutta l'inaffidabilità di questo metodo di memorizzazione e accumulo di informazioni, una persona iniziò a scrivere informazioni sotto forma di disegni, con l'invenzione della scrittura - sui papiri e successivamente sui libri. Poi sono apparse lastre fotografiche e dispositivi di registrazione del suono, come elementi di memoria esterna per informazioni video e audio, quaderni, libri di consultazione, enciclopedie, ecc., Che chiamiamo archiviazione esterna dei dati. A metà del XX secolo è stato inventato il computer. Immediatamente sorse la domanda su come avrebbe archiviato le informazioni.

Il supporto delle informazioni può essere di diversa natura: cartacea. Meccanico, magnetico, elettrico. Le informazioni registrate sui supporti possono essere sotto forma di simbolo leggibile dall'uomo o codificate. Informazioni per registratore, videoregistratore, cinepresa - suono memorizzati su appositi dispositivi: audiocassette, videocassette, film. Con l'aiuto di un microfono e altri dispositivi, le informazioni sonore vengono registrate su nastro magnetico.

Nei computer, sono stati utilizzati i seguenti dispositivi come dispositivi per la registrazione e la lettura di informazioni: lettori di schede perforate; unità a nastro magnetico, unità floppy (unità disco) e dischi rigidi (dischi rigidi) dischi magnetici; unità compact disc (CD-ROM) e altri dispositivi di archiviazione e archiviazione delle informazioni più moderni.

Elenco bibliografico

1. Legge federale della Federazione Russa "Sull'informazione, l'informatizzazione e la protezione delle informazioni" del 27 luglio 2006 n. 149-FZ.

2. Levin A.S. Un manuale di autoistruzione per lavorare su un computer. - SPb.: Pietro, 2006 .-- 655 p.

3. Romanova N.I. Fondamenti di informatica. - SPb.: Politecnico, 2004.224 p.

4. Simonovich S.V. Informatica. Corso base. - SPb.: Pietro, 2008 -640 p.

Pubblicato su Allbest.ru

Documenti simili

Tipi di compressione dei dati: lossy e lossless. Compressione con ridondanza minima. Codifica Shannon-Fano. Controllo del lavoro del programma per la compressione di file in formato bmp e xls. Implementazione Delphi dell'algoritmo di compressione di Shannon e Huffman.

tesina, aggiunta il 26/01/2011


Classificazione e principali caratteristiche del metodo di compressione dei dati. Calcolo dei rapporti di compressione e valutazione della loro efficacia. Algoritmi per metodi di compressione polinomiale, estrapolazione e interpolazione e loro confronto. Predizione lineare ottimale.

tesina aggiunta il 17/03/2011


Archiviazione e compressione come metodi di compressione delle immagini. Algoritmi di compressione dei dati. Strumenti ausiliari che vengono utilizzati per ridurre le dimensioni dei file: modifica del modello di colore dell'immagine, modifica della risoluzione del file raster, ricampionamento.

presentazione aggiunta 01/06/2014


Ricerca delle principali tipologie di programmi di archiviazione. Compressione dei file durante l'archiviazione. Rapporto di compressione dei file. Valutazione delle funzionalità dei packer più diffusi. Caratteristiche tecniche dei processi di compressione. Metodi di archiviazione senza perdite.

abstract aggiunto il 12/05/2013


Divulgazione dello scopo della compressione dei file e caratterizzazione dello scopo degli archiviatori come programmi che comprimono e decomprimono i file in un archivio per facilitarne il trasferimento e l'archiviazione. I principali tipi di archiviatori: file, software, disco. Metodo di compressione senza perdite.

presentazione aggiunta il 04/05/2011


Concetti di base e metodi di compressione dei dati. Conversione delle informazioni memorizzate in un file in un modulo che riduce la ridondanza nella sua presentazione. Metodi di compressione statistica e del vocabolario. Programmi di archiviazione, caratteristiche principali di WinRAR.

test, aggiunto il 03/12/2011


Una breve panoramica delle principali teorie della compressione. Idee concettuali e loro realizzazione. Compressione dei dati utilizzando la trasformata di Burrows-Wheeler. Algoritmo statico di Huffman. Algoritmo di compressione adattivo locale. Algoritmo di Ziv-Lempel (Welch) e metodo di Shannon-Fano.

lavoro pratico, aggiunto il 24.04.2014


Entropia e quantità di informazioni. Stima combinatoria, probabilistica e algoritmica della quantità di informazioni. Modellazione e codifica. Alcuni algoritmi di compressione dei dati. Algoritmo di codifica aritmetica. Invio e ricezione incrementali.

tesina, aggiunta il 28/07/2009


L'uso di algoritmi che forniscono un alto grado di compressione per aumentare la velocità di trasmissione dei dati sui canali di comunicazione. Caratteristiche e metodi per trovare la scomposizione in valori singolari. Sviluppo di un programma che implementa la compressione delle immagini utilizzando la compressione SVD.

tesi, aggiunta il 13/10/2015


Programmi per creare archivi. L'efficienza della compressione dei dati come caratteristica più importante degli archivi. I principali metodi di compressione dei dati. Caratteristiche del programma per impacchettare testi e programmi WinRar. Decomprimere file, comprimere file e cartelle in un archivio condiviso.

"Compressione dati"

Una caratteristica della maggior parte dei tipi di dati è la loro ridondanza. La quantità di ridondanza dei dati dipende dal tipo di dati. Ad esempio, per i dati video, il grado di ridondanza è parecchie volte maggiore rispetto ai dati grafici e il grado di ridondanza dei dati grafici, a sua volta, è maggiore del grado di ridondanza dei dati di testo. Un altro fattore che influenza il grado di ridondanza è il sistema di codifica adottato. Un esempio di sistemi di codifica possono essere i normali linguaggi di comunicazione, che altro non sono che sistemi per codificare concetti e idee per esprimere pensieri. Pertanto, è stato stabilito che la codifica di dati testuali utilizzando i mezzi della lingua russa fornisce in media una ridondanza del 20-25% in più rispetto alla codifica di dati simili tramite la lingua inglese.

Per una persona, la ridondanza dei dati è spesso associata alla qualità delle informazioni, poiché la ridondanza, di regola, migliora la comprensibilità e la percezione delle informazioni. Tuttavia, quando si tratta di archiviare e trasferire informazioni mediante la tecnologia informatica, la ridondanza gioca un ruolo negativo, poiché comporta un aumento dei costi di archiviazione e trasferimento delle informazioni. Questo problema diventa particolarmente urgente nel caso di elaborazione di enormi volumi di informazioni con piccoli volumi di supporti dati. A questo proposito si pone costantemente il problema della riduzione della ridondanza o della compressione dei dati. Se i metodi di compressione dei dati vengono applicati ai file finiti, spesso invece del termine "compressione dei dati" usano il termine "archiviazione dei dati", viene chiamata la versione compressa dei dati archivio e vengono chiamati strumenti software che implementano metodi di compressione archiviatori.

A seconda dell'oggetto in cui si trovano i dati, si distinguono i dati da comprimere:

Compressione (archiviazione) di file: utilizzata per ridurre le dimensioni dei file durante la preparazione per la trasmissione tramite canali di comunicazione o per il trasporto su supporti esterni di piccola capacità;

Compressione (archiviazione) di cartelle: utilizzata come mezzo per ridurre il volume delle cartelle prima dell'archiviazione a lungo termine, ad esempio durante il backup;

Compressione (compattazione) dei dischi: utilizzata per aumentare l'efficienza dell'utilizzo di un disco spazioso comprimendo i dati durante la scrittura su un supporto di memorizzazione (di solito tramite il sistema operativo).

Esistono molti algoritmi pratici di compressione dei dati, ma tutti si basano su tre modi teorici per ridurre la ridondanza dei dati. Il primo modo è modificare il contenuto dei dati, il secondo è modificare la struttura dei dati e il terzo è modificare contemporaneamente sia la struttura che il contenuto dei dati.

Se il contenuto dei dati cambia durante la compressione dei dati, viene chiamato il metodo di compressione irreversibile, ovvero quando si ripristinano (decomprimono) i dati dall'archivio, le informazioni non vengono ripristinate completamente. Tali tecniche sono spesso indicate come tecniche di compressione a perdita controllata. È chiaro che questi metodi possono essere utilizzati solo per tipi di dati per i quali la perdita di parte del contenuto non comporta una distorsione significativa delle informazioni. Questi tipi di dati includono video, audio e grafica. Le tecniche di compressione con controllo della perdita forniscono tassi di compressione significativamente più elevati, ma non possono essere applicate ai dati di testo. Esempi di formati di compressione con perdita includono:

JPEG - per dati grafici;

MPG - per dati video;

MP3 è per i dati audio.

Se durante la compressione dei dati si verifica solo una modifica nella struttura dei dati, viene chiamato il metodo di compressione reversibile... In questo caso, è possibile ripristinare completamente le informazioni dall'archivio. I metodi di compressione reversibile possono essere applicati a qualsiasi tipo di dati, ma producono una compressione inferiore rispetto ai metodi di compressione irreversibile. Esempi di formati di compressione senza perdita di dati:

GIF, TIFF - per dati grafici;

AVI - per dati video;

ZIP, ARJ, RAR, CAB, LH - per tipi di dati arbitrari.

Esistono molte pratiche di compressione senza perdita di dati che generalmente hanno un'efficienza diversa per i diversi tipi di dati e per le diverse dimensioni. Tuttavia, questi metodi si basano su tre algoritmi teorici:

Algoritmo RLE (Run Length Encoding);

algoritmi del gruppo KWE (KeyWord Encoding);

Algoritmo di Huffman.

Algoritmo RLE

L'algoritmo RLE si basa sull'idea di rilevare sequenze di dati ripetute e di sostituirle con una struttura più semplice, che specifica il codice dei dati e la velocità di ripetizione. Ad esempio, supponiamo che ti venga fornita una sequenza di dati soggetta a compressione:

1 1 1 1 2 2 3 4 4 4

L'algoritmo RLE propone di sostituirlo con la seguente struttura: 1 4 2 2 3 1 4 3, dove il primo numero di ciascuna coppia di numeri è il codice dati, e il secondo è il fattore di ripetizione. Se viene allocato 1 byte per memorizzare ogni elemento di dati della sequenza di input, l'intera sequenza occuperà 10 byte di memoria, mentre la sequenza di output (versione compressa) occuperà 8 byte di memoria. Il rapporto di compressione, che caratterizza il rapporto di compressione, può essere calcolato utilizzando la formula:

dove Vx è la quantità di memoria richiesta per memorizzare la sequenza di dati di output (risultante), Vn è la sequenza di dati di input.

Più basso è il valore del rapporto di compressione, più efficiente è il metodo di compressione. È chiaro che l'algoritmo RLE fornirà un migliore effetto di compressione quando la lunghezza della sequenza di dati ripetitiva è maggiore. Nel caso dell'esempio precedente, se la sequenza di input è simile a questa: 1 1 1 1 1 1 3 4 4 4, il rapporto di compressione sarà del 60%. A questo proposito, la maggiore efficienza dell'algoritmo RLE si ottiene durante la compressione dei dati grafici (soprattutto per le immagini monocromatiche).

Algoritmi del gruppo KWE

L'algoritmo di compressione delle parole chiave si basa sul principio della codifica delle unità lessicali in gruppi di byte di lunghezza fissa. Un esempio di unità lessicale sarebbe una parola normale. In pratica, vengono selezionate sequenze ripetute di caratteri per il ruolo di unità lessicali, che sono codificate con una catena di caratteri (codice) di lunghezza inferiore. Il risultato della codifica viene inserito nella tabella, formando un cosiddetto dizionario.

Esistono alcune implementazioni di questo algoritmo, tra le quali le più comuni sono l'algoritmo Lempel-Ziva (algoritmo LZ) e la sua modifica, l'algoritmo Lempel-Ziva-Welch (algoritmo LZW). Il dizionario in questo algoritmo è un elenco potenzialmente infinito di frasi. L'algoritmo parte da un dizionario quasi vuoto che contiene una sola stringa codificata, la cosiddetta stringa NULL. Quando si legge il carattere successivo della sequenza di dati di input, viene aggiunto alla riga corrente. Il processo continua finché la riga corrente corrisponde a qualsiasi frase del dizionario. Ma prima o poi, la riga corrente smette di corrispondere a qualsiasi frase nel dizionario. Nel momento in cui la riga corrente è l'ultima corrispondenza con il dizionario più il carattere del messaggio appena letto, l'encoder emette un codice che consiste nell'indice della corrispondenza seguito dal carattere che ha interrotto la corrispondenza delle righe. Viene aggiunta al dizionario una nuova frase, costituita dall'indice della corrispondenza seguito dal carattere. La prossima volta che questa frase appare in un messaggio, può essere usata per costruire una frase più lunga, che aumenta il grado di compressione delle informazioni.

L'algoritmo LZW è costruito attorno a una tabella delle frasi (dizionario) che sostituisce le stringhe di caratteri del messaggio compresso in codici a lunghezza fissa. La tabella ha la cosiddetta proprietà di anticipo, cioè per ogni frase del dizionario, costituita da qualche frase w e dal simbolo K, viene inserita nel dizionario anche la frase w. Se tutte le parti del dizionario sono completamente riempite, la codifica cessa di essere adattiva (la codifica si basa su frasi già esistenti nel dizionario).

Gli algoritmi di compressione in questo gruppo sono più efficaci per dati di testo di grandi dimensioni e inefficaci per file di piccole dimensioni (a causa della necessità di preservare il dizionario).

Algoritmo di Huffman

L'algoritmo di Huffman si basa sull'idea della codifica in gruppi di bit. Innanzitutto, viene eseguita un'analisi di frequenza della sequenza di dati di input, ovvero viene impostata la frequenza di occorrenza di ciascun simbolo trovato in essa. Successivamente, i simboli vengono ordinati in base alla frequenza decrescente di occorrenza.

L'idea di base è la seguente: più spesso un carattere si verifica, meno bit è codificato. Il risultato della codifica viene inserito nel dizionario richiesto per la decodifica. Diamo un'occhiata a un semplice esempio per illustrare come funziona l'algoritmo di Huffman.

Lascia che sia dato il testo, in cui il trapano "A" appare 10 volte, la lettera "B" - 8 volte, "C" - 6 volte, "D" - 5 volte, "E" e "F" - 4 volte . Quindi una delle possibili opzioni di codifica per l'algoritmo di Huffman è mostrata nella Tabella 1.

Tabella 1.

	Frequenza dell'evento	Codice bit

Come si può vedere dalla Tabella 1, la dimensione del testo di input prima della compressione è di 37 byte, mentre dopo la compressione è di 93 bit, cioè circa 12 byte (esclusa la lunghezza del dizionario). Il rapporto di compressione è del 32%. L'algoritmo di Huffman è universale, può essere utilizzato per comprimere dati di qualsiasi tipo, ma è inefficace per file di piccole dimensioni (a causa della necessità di salvare un dizionario).

In pratica, i software di compressione dei dati sintetizzano questi tre algoritmi "puri", poiché la loro efficienza dipende dal tipo e dalla quantità di dati. La tabella 2 mostra i formati di compressione comuni e i programmi e gli archivi di archiviazione corrispondenti utilizzati nella pratica.

Tavolo 2.

Formato di compressione	Sistema operativo MS DOS		Sistema operativo Windows
	Programma di archiviazione	Decomprimere il programma	Programma di archiviazione	Decomprimere il programma

Inoltre, i moderni archiviatori forniscono all'utente una gamma completa di servizi per lavorare con gli archivi, i principali dei quali sono:

creazione di un nuovo archivio;

aggiungere file a un archivio esistente;

decomprimere i file dall'archivio;

creazione di archivi autoestraenti (archivio autoestraente);

creazione di archivi distribuiti di dimensione fissa per piccoli media;

protezione degli archivi con password da accessi non autorizzati;

visualizzare il contenuto di file di formati diversi senza prima scompattare;

ricerca di file e dati all'interno dell'archivio;

controlla la presenza di virus nell'archivio per la decompressione;

selezione e regolazione del rapporto di compressione.

Domande di controllo

1. Quali fattori influenzano il grado di ridondanza dei dati? 2. Che cos'è un archivio? Quali strumenti software sono chiamati archiviatori? 3. Perché i metodi di compressione che modificano il contenuto dei dati sono definiti irreversibili? 4. Fornire esempi di formati di compressione con perdita. 5. Qual è il vantaggio dei metodi di compressione reversibili rispetto a quelli irreversibili? E lo svantaggio? 6. Qual è la relazione tra il rapporto di compressione e l'efficienza del metodo di compressione? 7. Qual è l'idea principale dell'algoritmo RLE? 8. Qual è l'idea principale degli algoritmi del gruppo KWE? 9. Qual è l'idea principale dell'algoritmo di Huffman? 10. Quali programmi di archiviazione conosci? Descrivili brevemente.

Informatica. Corso base. / Ed. S.V. Simonovich. - SPb., 2000

A.P. Miklyaev, Manuale per l'utente del PC IBM 3a edizione M .:, "Solon-R", 2000, 720 p.

Simonovich S.V., Evseev G.A., Murakhovsky V.I. Hai comprato il tuo computer: la guida completa per principianti a domande e risposte. - M.: LIBRO AST-PRESS; Inforkom-Press, 2001.- 544 p.: ill. (1000 consigli).

Yu.S. Kovtanyuk, S.V. Solovyan Un manuale di autoistruzione per lavorare su un personal computer - K.: Junior, 2001.- 560s., Ill.

Io e il mio consulente scientifico stiamo preparando una piccola monografia sull'elaborazione delle immagini. Ho deciso di sottoporre al giudizio di HabraSociety un capitolo sugli algoritmi di compressione delle immagini. Dato che è difficile inserire un intero capitolo all'interno di un post, ho deciso di dividerlo in tre post:
1. Metodi di compressione dei dati;
2. Compressione senza perdita di immagini;
3. Compressione di immagini con perdita.
Di seguito potete leggere il primo post della serie.

Al momento, esiste un gran numero di algoritmi di compressione senza perdita di dati, che possono essere suddivisi condizionatamente in due grandi gruppi:
1. Algoritmi di flusso e dizionario. Questo gruppo include algoritmi delle famiglie RLE (codifica run-length), LZ *, ecc.. Una caratteristica di tutti gli algoritmi di questo gruppo è che la codifica non utilizza informazioni sulle frequenze dei caratteri nel messaggio, ma informazioni sulle sequenze che si sono incontrati in precedenza.
2. Algoritmi per la compressione statistica (entropia). Questo gruppo di algoritmi comprime le informazioni sfruttando l'irregolarità delle frequenze con cui si presentano caratteri diversi nel messaggio. Gli algoritmi in questo gruppo includono algoritmi aritmetici e di codifica dei prefissi (usando Shannon-Fanno, Huffman, alberi secante).
Gli algoritmi di trasformazione delle informazioni possono essere distinti in un gruppo separato. Gli algoritmi di questo gruppo non comprimono direttamente le informazioni, ma la loro applicazione semplifica notevolmente l'ulteriore compressione utilizzando algoritmi di flusso, dizionario e entropia.

Algoritmi di streaming e dizionario

Codifica della lunghezza della corsa

Run-Length Encoding (RLE) è uno degli algoritmi di compressione dei dati più semplici e comuni. In questo algoritmo, una sequenza di caratteri ripetuti viene sostituita da un carattere e dal numero di volte che viene ripetuta.
Ad esempio, la stringa "AAAA", che richiede 5 byte per essere archiviata (assumendo che un byte sia allocato per memorizzare un carattere), può essere sostituita con "5A", composta da due byte. Ovviamente, più lunga è la serie di ripetizioni, più efficiente è questo algoritmo.

Il principale svantaggio di questo algoritmo è la sua efficienza estremamente bassa su sequenze di caratteri non ripetuti. Ad esempio, se consideriamo la sequenza "ABABAB" (6 byte), dopo aver applicato l'algoritmo RLE si trasformerà in "1A1B1A1B1A1B" (12 byte). Esistono vari metodi per affrontare il problema dei caratteri non ripetuti.

Il metodo più semplice è la seguente modifica: il byte che codifica il numero di ripetizioni deve memorizzare informazioni non solo sul numero di ripetizioni, ma anche sulla loro presenza. Se il primo bit è 1, i successivi 7 bit indicano il numero di ripetizioni del carattere corrispondente e se il primo bit è 0, i successivi 7 bit indicano il numero di caratteri che devono essere presi senza ripetizione. Se codifichi "ABABAB" usando questa modifica, otteniamo "-6ABABAB" (7 byte). Ovviamente, la tecnica proposta può migliorare significativamente l'efficienza dell'algoritmo RLE su sequenze di caratteri non ripetitive. L'implementazione dell'approccio proposto è mostrata nel Listato 1:

1. genere
2. funzione RLEEncode (InMsg: ShortString): TRLEEncodedString;
3. MatchFl: booleano;
4. MatchCount: shortint;
5. EncodedString: TRLEEncodedString;
6. N, io: byte;
7. inizio
8. N: = 0;
9. SetLength (EncodedString, 2 * lunghezza (InMsg));
10. mentre lunghezza (InMsg)> = 1 do
11. inizio
12. MatchFl: = (lunghezza (InMsg)> 1) e (InMsg [1] = InMsg [2]);
13. MatchCount: = 1;
14. mentre (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount: = MatchCount + 1;
16. se MatchFl allora
17. inizio
18. N: = N + 2;
19. EncodedString [N - 2]: = MatchCount + 128;
20. EncodedString [N - 1]: = ord (InMsg [1]);
21. altro
22. inizio
23. se MatchCount<>lunghezza (InMsg) quindi
24. MatchCount: = MatchCount - 1;
25. N: = N + 1 + Conteggio partite;
26. EncodedString [N - 1 - MatchCount]: = - MatchCount + 128;
27. for i: = 1 per MatchCount do
28. EncodedString [N - 1 - MatchCount + i]: = ord (InMsg [i]);
29. fine;
30. elimina (InMsg, 1, MatchCount);
31. fine;
32. SetLength (Stringa Codificata, N);
33. RLEEncode: = EncodedString;
34. fine;

La decodifica di un messaggio compresso è molto semplice e si riduce a un singolo passaggio sul messaggio compresso, vedere Listato 2:

1. genere
2. TRLEEncodedString = array di byte;
3. funzione RLEDecode (InMsg: TRLEEncodedString): ShortString;
4. RepeatCount: shortint;
5. io, j: parola;
6. OutMsg: ShortString;
7. inizio
8. OutMsg: = "";
9. io: = 0;
10. mentre io< length(InMsg) do
11. inizio
12. Numero ripetizioni: = InMsg [i] - 128;
13. io: = io + 1;
14. if RepeatCount< 0 then
15. inizio
16. RepeatCount: = abs (RepeatCount);
17. per j: = da i a i + RepeatCount - 1 do
18. OutMsg: = OutMsg + chr (InMsg [j]);
19. i: = i + Conteggio ripetizioni;
20. altro
21. inizio
22. per j: = 1 a RepeatCount do
23. OutMsg: = OutMsg + chr (InMsg [i]);
24. io: = io + 1;
25. fine;
26. fine;
27. RLDecode: = OutMsg;
28. fine;

Il secondo metodo per aumentare l'efficienza dell'algoritmo RLE è l'uso di algoritmi di trasformazione delle informazioni che non comprimono direttamente i dati, ma li portano in una forma più conveniente per la compressione. Come esempio di tale algoritmo, considereremo una permutazione BWT che prende il nome dagli inventori della trasformata di Burrows-Wheeler. Questa permutazione non cambia i caratteri stessi, ma cambia solo il loro ordine nella stringa, mentre le sottostringhe ripetute dopo aver applicato la permutazione vengono raccolte in gruppi densi, che vengono compressi molto meglio utilizzando l'algoritmo RLE. La conversione BWT diretta si riduce alla sequenza dei seguenti passaggi:
1. Aggiunta di un carattere speciale di fine riga alla stringa originale, che non si trova da nessun'altra parte;
2. Ottenere tutte le permutazioni cicliche della stringa originale;
3. Ordinamento lessicografico delle righe ricevute;
4. Restituzione dell'ultima colonna della matrice risultante.
L'implementazione di questo algoritmo è mostrata nel Listato 3.

1. cost
2. EOMsg = "|" ;
3. funzione BWTEncode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. UltimoCar: ANSICar;
6. N, io: parola;
7. inizio
8. InMsg: = InMsg + EOMsg;
9. N: = lunghezza (InMsg);
10. ShiftTable [1]: = InMsg;
11. per i: = da 2 a N do
12. inizio
13. LastChar: = InMsg [N];
14. InMsg: = LastChar + copia (InMsg, 1, N - 1);
15. ShiftTable [i]: = InMsg;
16. fine;
17. Ordina (ShiftTable);
18. OutMsg: = "";
19. per i: = da 1 a N do
20. OutMsg: = OutMsg + ShiftTable [i] [N];
21. BWTEncode: = OutMsg;
22. fine;

Il modo più semplice per spiegare questa trasformazione è con un esempio specifico. Prendiamo la stringa "ANANAS" e concordiamo che il carattere di fine riga sarà il simbolo "|". Tutte le permutazioni cicliche di questa linea e il risultato del loro ordinamento lessicografico sono mostrati nella tabella. uno.

Quelli. il risultato della conversione diretta sarà la stringa "| ННААС". È facile vedere che questa stringa è molto migliore di quella originale; è compressa dall'algoritmo RLE, poiché contiene lunghe sottosequenze di lettere ripetute.
Un effetto simile può essere ottenuto con l'aiuto di altre trasformazioni, ma il vantaggio della trasformata BWT è che è reversibile, tuttavia la trasformata inversa è più difficile di quella diretta. Per ripristinare la stringa originale, è necessario effettuare le seguenti operazioni:
Creare una matrice n * n vuota, dove n è il numero di caratteri nel messaggio codificato;
Riempi la colonna vuota più a destra con il messaggio codificato;
Ordina le righe della tabella in ordine lessicografico;
Ripeti i passaggi 2-3 finché non ci sono colonne vuote;
Restituisce la riga che termina con il carattere di fine riga.

A prima vista, la trasformazione inversa è semplice e una delle opzioni è mostrata nel Listato 4.

1. cost
2. EOMsg = "|" ;
3. funzione BWTDecode (InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. ShiftTable: array di ShortString;
6. N, i, j: parola;
7. inizio
8. OutMsg: = "";
9. N: = lunghezza (InMsg);
10. SetLength (ShiftTable, N + 1);
11. per i: = da 0 a N do
12. ShiftTable [i]: = "";
13. per i: = da 1 a N do
14. inizio
15. per j: = da 1 a N do
16. ShiftTable [j]: = InMsg [j] + ShiftTable [j];
17. Ordina (ShiftTable);
18. fine;
19. per i: = da 1 a N do
20. se ShiftTable [i] [N] = EOMsg allora
21. OutMsg: = ShiftTable [i];
22. cancella (OutMsg, N, 1);
23. BWTDecode: = OutMsg;
24. fine;

Ma in pratica, l'efficienza dipende dall'algoritmo di ordinamento selezionato. Algoritmi banali con complessità quadratica avranno ovviamente un impatto estremamente negativo sulle prestazioni, quindi si consiglia di utilizzare algoritmi efficienti.

Dopo aver ordinato la tabella ottenuta nel settimo passaggio, è necessario selezionare dalla tabella una riga che termini con il carattere "|". È facile vedere che questa è l'unica linea. Quella. abbiamo esaminato la trasformazione BWT utilizzando un esempio specifico.

Riassumendo, possiamo dire che il principale vantaggio del gruppo di algoritmi RLE è la semplicità e la velocità di funzionamento (compresa la velocità di decodifica) e il principale svantaggio è l'inefficienza sui set di caratteri non ripetuti. L'uso di permutazioni speciali aumenta l'efficienza dell'algoritmo, ma aumenta anche notevolmente il tempo di esecuzione (in particolare la decodifica).

Compressione del dizionario (algoritmi LZ)

Il gruppo di algoritmi del dizionario, a differenza degli algoritmi del gruppo RLE, codifica non il numero di ripetizioni di caratteri, ma le sequenze di caratteri incontrate in precedenza. Durante il funzionamento degli algoritmi in esame, viene creata dinamicamente una tabella con un elenco di sequenze precedentemente incontrate e dei relativi codici. Questa tabella è spesso chiamata dizionario e il gruppo di algoritmi corrispondente è chiamato dizionario.

La versione più semplice dell'algoritmo del dizionario è descritta di seguito:
Inizializza il dizionario con tutti i caratteri che compaiono nella stringa di input;
Trova nel dizionario la sequenza più lunga (S) che corrisponde all'inizio del messaggio codificato;
Emettere il codice della sequenza trovata e rimuoverlo dall'inizio del messaggio codificato;
Se non si raggiunge la fine del messaggio, leggere il carattere successivo e aggiungere Sc al dizionario, passare al punto 2. Altrimenti, uscire.

Ad esempio, il vocabolario appena inizializzato per la frase "CUCKOOKUCHONKUPILACAPUCHON" è mostrato nella Tabella. 3:

Durante il processo di compressione, il dizionario sarà integrato con le sequenze trovate nel messaggio. Il processo di rifornimento del dizionario è mostrato nella tabella. 4.

Quando si descrive l'algoritmo, la descrizione della situazione in cui il dizionario è completamente riempito è stata deliberatamente omessa. A seconda della variante dell'algoritmo, è possibile un comportamento diverso: svuotamento totale o parziale del dizionario, arresto del riempimento del dizionario o espansione del dizionario con un corrispondente aumento della larghezza del codice. Ciascuno di questi approcci presenta alcuni svantaggi. Ad esempio, l'interruzione del completamento del dizionario può portare a una situazione in cui il dizionario memorizza le sequenze che si verificano all'inizio della stringa compressa, ma non si verificano in seguito. Allo stesso tempo, la cancellazione del dizionario può rimuovere le sequenze frequenti. La maggior parte delle implementazioni utilizzate, durante la compilazione del dizionario, inizia a tenere traccia del rapporto di compressione e quando scende al di sotto di un certo livello, il dizionario viene ricostruito. Successivamente, considereremo l'implementazione più semplice che interrompe il rifornimento del dizionario quando è pieno.

Innanzitutto, definiamo un dizionario come un record che memorizza non solo le sottostringhe trovate, ma anche il numero di sottostringhe memorizzate nel dizionario:

Le sottosequenze incontrate in precedenza sono memorizzate nell'array Words e i loro codici sono i numeri delle sottosequenze in questo array.
Definiamo anche le funzioni per la ricerca nel dizionario e l'aggiunta al dizionario:

1. cost
2. MAX_DICT_LENGTH = 256;
3. funzione FindInDict (D: TDictionary; str: ShortString): intero;
4. r: intero;
5. io: intero;
6. fl: booleano;
7. inizio
8. r: = - 1;
9. se D. WordCount> 0 allora
10. inizio
11. i: = D. ConteggioParole;
12. fl: = falso;
13. mentre (non fl) e (i> = 0) do
14. inizio
15. io: = io - 1;
16. fl: = D. Parole [i] = str;
17. fine;
18. fine;
19. se fl allora
20. r: = io;
21. TrovaInDitto: = r;
22. fine;
23. procedura AddToDict (var D: TDictionary; str: ShortString);
24. inizio
25. se D. ConteggioParole< MAX_DICT_LENGTH then
26. inizio
27. D. ConteggioParole: = D. ConteggioParole + 1;
28. SetLength (D. Words, D. WordCount);
29. D. Parole [D. ConteggioParole - 1]: = str;
30. fine;
31. fine;

Utilizzando queste funzioni, il processo di codifica secondo l'algoritmo descritto può essere implementato come segue:

1. funzione LZWEncode (InMsg: ShortString): TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: Dizionario TD;
5. io, N: byte;
6. inizio
7. SetLength (OutMsg, lunghezza (InMsg));
8. N: = 0;
9. InitDict (D);
10. mentre lunghezza (InMsg)> 0 do
11. inizio
12. tmpstr: = InMsg [1];
13. while (FindInDict (D, tmpstr)> = 0) e (length (InMsg)> length (tmpstr)) do
14. tmpstr: = tmpstr + InMsg [lunghezza (tmpstr) + 1];
15. if FindInDict (D, tmpstr)< 0 then
16. elimina (tmpstr, lunghezza (tmpstr), 1);
17. OutMsg [N]: = FindInDict (D, tmpstr);
18. N: = N + 1;
19. elimina (InMsg, 1, lunghezza (tmpstr));
20. se lunghezza (InMsg)> 0 allora
21. AddToDict (D, tmpstr + InMsg [1]);
22. fine;
23. SetLength (OutMsg, N);
24. LZWEncode: = OutMsg;
25. fine;

Il risultato della codifica saranno i numeri delle parole nel dizionario.
Il processo di decodifica si riduce alla decodifica diretta dei codici, mentre non è necessario trasferire il dizionario creato, è sufficiente che durante la decodifica il dizionario venga inizializzato allo stesso modo della codifica. Quindi il dizionario verrà completamente ripristinato direttamente durante il processo di decodifica concatenando la sottosequenza precedente e il simbolo corrente.

L'unico problema è possibile nella seguente situazione: quando è necessario decodificare una sottosequenza che non è ancora nel dizionario. È facile vedere che ciò è possibile solo quando è necessario estrarre una sottostringa da aggiungere al passaggio corrente. Ciò significa che la sottostringa corrisponde al modello cSc, ad es. inizia e finisce con lo stesso carattere. Inoltre, cS è la sottostringa aggiunta nel passaggio precedente. La situazione considerata è l'unica quando è necessario decodificare una linea che non è stata ancora aggiunta. Considerando quanto sopra, possiamo suggerire la seguente opzione per decodificare una stringa compressa:

1. funzione LZWDecode (InMsg: TEncodedString): ShortString;
2. D: Dizionario TD;
3. OutMsg, tmpstr: ShortString;
4. io: byte;
5. inizio
6. OutMsg: = "";
7. tmpstr: = "";
8. InitDict (D);
9. per i: = 0 alla lunghezza (InMsg) - 1 do
10. inizio
11. if InMsg [i]> = D. WordCount allora
12. tmpstr: = D. Parole [InMsg [i - 1]] + D. Parole [InMsg [i - 1]] [1]
13. altro
14. tmpstr: = D. Parole [InMsg [i]];
15. OutMsg: = OutMsg + tmpstr;
16. se io> 0 allora
17. AddToDict (D, D. Words [InMsg [i - 1]] + tmpstr [1]);
18. fine;
19. LZWDecode: = OutMsg;
20. fine;

I vantaggi degli algoritmi del dizionario includono la loro maggiore efficienza di compressione rispetto a RLE. Tuttavia, si dovrebbe comprendere che l'uso reale di questi algoritmi è associato ad alcune difficoltà di implementazione.

codifica entropia

Codifica con alberi di Shannon-Fano

L'algoritmo di Shannon-Fano è uno dei primi algoritmi di compressione sviluppati. L'algoritmo si basa sull'idea di rappresentare caratteri più frequenti utilizzando codici più brevi. Inoltre, i codici ottenuti utilizzando l'algoritmo di Shannon-Fano hanno la proprietà del prefisso: i.e. nessun codice è l'inizio di un altro codice. La proprietà prefix garantisce che la codifica sia uno a uno. L'algoritmo per la costruzione dei codici Shannon-Fano è presentato di seguito:
1. Dividi l'alfabeto in due parti, le probabilità totali dei simboli in cui sono il più vicino possibile l'uno all'altro.
2. Aggiungere 0 al codice prefisso della prima parte di caratteri, aggiungere 1 al codice prefisso della seconda parte di caratteri.
3. Per ogni parte (in cui sono presenti almeno due caratteri), eseguire ricorsivamente i passaggi 1-3.
Nonostante la sua relativa semplicità, l'algoritmo di Shannon-Fano non è privo di inconvenienti, il più significativo dei quali è la codifica non ottimale. Sebbene il partizionamento ad ogni passaggio sia ottimale, l'algoritmo non garantisce un risultato ottimale nel suo insieme. Si consideri, ad esempio, la seguente riga: "AAAABVGDEZH". Il corrispondente albero di Shannon-Fano e i codici da esso derivati ​​sono mostrati in Fig. uno:

Senza codifica, il messaggio occuperà 40 bit (assumendo che ogni carattere sia codificato con 4 bit), e utilizzando l'algoritmo di Shannon-Fano 4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 = 27 bit. Il volume dei messaggi è diminuito del 32,5%, ma verrà mostrato di seguito che questo risultato può essere notevolmente migliorato.

Codifica con Huffman Trees

L'algoritmo di codifica di Huffman, sviluppato qualche anno dopo l'algoritmo di Shannon-Fano, possiede anche la proprietà del prefisso, e, inoltre, la comprovata ridondanza minima, proprio per questo è estremamente diffuso. Per ottenere i codici di Huffman, viene utilizzato il seguente algoritmo:
1. Tutti i simboli dell'alfabeto sono rappresentati come nodi liberi, mentre il peso del nodo è proporzionale alla frequenza del simbolo nel messaggio;
2. Dall'insieme dei nodi liberi vengono selezionati due nodi con il peso minimo e viene creato un nuovo nodo (genitore) con un peso pari alla somma dei pesi dei nodi selezionati;
3. I nodi selezionati vengono rimossi dall'elenco libero e il nodo padre creato sulla base di essi viene aggiunto a questo elenco;
4. I passaggi 2-3 vengono ripetuti finché non c'è più di un nodo nell'elenco libero;
5. In base all'albero costruito, ad ogni carattere dell'alfabeto viene assegnato un codice prefisso;
6. Il messaggio viene codificato con i codici ricevuti.

Considera lo stesso esempio dell'algoritmo di Shannon-Fano. L'albero di Huffman e i codici ottenuti per il messaggio "AAAABVGDEZH" sono mostrati in Fig. 2:

È facile calcolare che la dimensione del messaggio codificato sarà di 26 bit, che è inferiore a quella dell'algoritmo Shannon-Fano. Separatamente, va notato che a causa della popolarità dell'algoritmo di Huffman, al momento ci sono molte opzioni per la codifica di Huffman, inclusa la codifica adattiva, che non richiede la trasmissione di frequenze di simboli.
Tra gli svantaggi dell'algoritmo di Huffman, una parte significativa sono i problemi associati alla complessità dell'implementazione. L'utilizzo di variabili reali per la memorizzazione delle frequenze dei simboli è associato ad una perdita di precisione; quindi, in pratica, vengono spesso utilizzate variabili intere, ma poiché il peso dei nodi genitori è in costante crescita, prima o poi si verifica un overflow. Pertanto, nonostante la semplicità dell'algoritmo, la sua corretta implementazione può ancora causare alcune difficoltà, soprattutto per alfabeti di grandi dimensioni.

Codifica con alberi di funzioni secanti

La codifica tramite funzioni secante è un algoritmo sviluppato dagli autori che consente di ottenere codici di prefisso. L'algoritmo si basa sull'idea di costruire un albero, ogni nodo del quale contiene una funzione secante. Per descrivere l'algoritmo in modo più dettagliato, è necessario introdurre diverse definizioni.
Una parola è una sequenza ordinata di m bit (il numero m è chiamato lunghezza della parola).
Il letterale secante è una coppia del tipo di cifra-valore della cifra. Ad esempio, letterale (4,1) significa che i 4 bit della parola devono essere 1. Se la condizione letterale è soddisfatta, allora il letterale è considerato vero, altrimenti è falso.
Una secante a k bit è un insieme di k letterali. Se tutti i letterali sono veri, allora la stessa funzione secante è vera, altrimenti è falsa.

L'albero è costruito in modo che ogni nodo divida l'alfabeto nelle parti più vicine possibili. Nella fig. 3 mostra un esempio di albero secante:

L'albero delle funzioni secanti nel caso generale non garantisce una codifica ottimale, ma fornisce una velocità di lavoro estremamente elevata grazie alla semplicità dell'operazione nei nodi.

Codifica aritmetica

La codifica aritmetica è uno dei modi più efficienti per comprimere le informazioni. A differenza dell'algoritmo di Huffman, la codifica aritmetica consente di codificare messaggi con un'entropia inferiore a 1 bit per simbolo. Perché la maggior parte degli algoritmi di codifica aritmetica sono protetti da brevetti, di seguito verranno descritte solo le idee di base.
Supponiamo che nell'alfabeto utilizzato vi siano N simboli a_1, ..., a_N, con frequenze p_1, ..., p_N, rispettivamente. Quindi l'algoritmo di codifica aritmetica sarà simile a questo:
Prendi come mezzo intervallo di lavoro)