Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren

Wiki Bookwizard - ThePacker

Clear page cache

Edit current page

Create or Edit page TOC
include TOC with

{{:Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren:_TOC}}

zurück

5 Verlustfreie_Verfahren

5.2 Wörterbuchbasierte Verfahren

5.2.1 LZ77 - Lempel, Ziv (1977)

5.2.2 LZ78 - Lempel, Ziv (1978)

5.2.3 LZSS - Storer, Szymanski (1982)

5.2.4 LZW - Welch (1984)

5.2.5 LZPP - Pylak (2003)

5.2.6 LZFG - Fiala, Green

5.2.7 LZRW - Williams (1989-1991)

5.2.8 LZV - Vogt (1994)

5.2.9 LZMW - Miller, Wegman (1985)

5.2.10 LZC - ?

5.2.11 LZT - Tischer (1987)

5.2.12 LZJ - Jakobsson

5.2.13 LZR - Rodeh, Pratt, Even

5.2.14 LZB - Bell

5.2.15 LZH - Herd

5.2.16 LZO - Oberhumer

5.2.17 LZP/LZCB - Bloom (1996)

5.2.18 LZAP - Storer (1988)

5.2.19 LZY - Yabba

5.2.20

Geplante Kapitelteile

Problem der statistischen Verfahren erläutern-Statistik muss zuvor berechnet werden um optimal zu arbeiten.
bzip, bzip2, zip, gzip, pkzip
arc, arj, lha, lharc

LZFG - Fiala, Green

Edward R Fiala, Daniel H Green, - "Data compression with finite windows", Basis:LZ77,LZ78

LZC -

Basis:LZ78

LZJ - Jakobsson

Matti Jacobsson, "Compression of character strings by an adaptive Dictionary" Basis: LZ78

LZR - Rodeh, Pratt, Even

Michael Rodeh, Vaughan R. Pratt, Shimon Even, stellten in ihrer Arbeit "Linear Algorithm for Data Compression via String Matching" JACM 28(1) Jan.1981 eine schnellere Variante des LZ77 Verfahrens vor. Das ursprüngliche Verfahren von Lempel und Ziv hat eine Komplexität von O(n^2). Dies ist für ein derart übersichtliches Verfahren jedoch unangemessen, wenn man auf besonders hohe Geschwindigkeiten bei der Codierung angewiesen ist. Mit dem LZR-Verfahren wird ein Verfahren vorgestellt, welches eine Zeitliche Komplexität von O(n) sowie eine Speicheranforderung von O(n) besitzt.

Erläutern der SuffixTrees...
Alternativ Weiners Algorithmus
Alternativ Repetitionfinder

Diese Variante der LZ77 Codierung ist also auf eine höhere Codier-Geschwindigkeit ausgelegt und stellt keine Verbesserung im Sinne einer Speicher-effizienteren Codierung dar.

Weblink auf den Artitel

http://www.enseignement.polytechnique.fr/profs/informatique/Frederic.Magniez/03-04/INF_431/rpe81.pdf

LZB - Bell

T.C.Bell - "An unifying theory and improvements for existing approaches to text compression" Basis: LZ77

LZH - Herd

Bernd Herd - Basis: LZ77 - mit Huffman

LZO - Oberhumer

Markus Franz Xaver Johannes Oberhumer veröffentlicht in unregelmäßigen Abständen eine neue Version seiner LZO-Bibliothek "a real-time data compression library". Die verwendete Basis LZ77/LZ78 und die vorgenommenen Optimierungen ist nicht dokumentiert. Das einzige was klar ersichtlich ist, ist dass die verwendete Fenstergröße eingestellt werden kann. Damit bleibt zu vermuten, dass es sich um ein LZ77 Verfahren handeln muss. Diese Aussage kann aber nicht als gesichert angesehen werden.