Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren

Aus Wikibooks
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 10% fertig
5.2.1 LZ77 - Lempel, Ziv (1977) 80% fertig
5.2.2 LZ78 - Lempel, Ziv (1978) 10% fertig
5.2.3 LZSS - Storer, Szymanski (1982) 60% fertig
5.2.4 LZW - Welch (1984) 20% fertig
5.2.5 LZPP - Pylak (2003) 30% fertig
5.2.6 LZFG - Fiala, Green
5.2.7 LZRW - Williams (1989-1991) 10% fertig
5.2.8 LZV - Vogt (1994) 10% fertig
5.2.9 LZMW - Miller, Wegman (1985) 10% fertig
5.2.10 LZC - ?
5.2.11 LZT - Tischer (1987) 40% fertig
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) 20% fertig
5.2.18 LZAP - Storer (1988) 10% fertig
5.2.19 LZY - Yabba
5.2.20


Geplante Kapitelteile[Bearbeiten]

  • 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[Bearbeiten]

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

LZC -[Bearbeiten]

Basis:LZ78

LZJ - Jakobsson[Bearbeiten]

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

LZR - Rodeh, Pratt, Even[Bearbeiten]

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.

  1. Erläutern der SuffixTrees...
  2. Alternativ Weiners Algorithmus
  3. 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[Bearbeiten]

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

LZH - Herd[Bearbeiten]

Bernd Herd - Basis: LZ77 - mit Huffman

LZO - Oberhumer[Bearbeiten]

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.

Basis: Leider Fraglich

LZY - Yabba[Bearbeiten]

Daniel J Bernstein a.k.a Dan Bernstein - LZY is like LZRW5

LZBW - Bender, Wolf[Bearbeiten]

LZJH - Jeff Heath[Bearbeiten]