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 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

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