Archiv verlassen und diese Seite im Standarddesign anzeigen : Wörterbuch-Komprimierverfahren vs. Entropiekodierung
Was bringt bei a) langen Textdateien b) normalen Dateien mehr?
- Wörterbuchverfahren wie LZW, LZ77, LZ78, ...
- Burrows-Wheeler mit Move-to-front und dann Entropieoptimierung (Huffman)?
Wie kann man überhaupt beide Ansätze sinnvoll kombinieren? Entropieoptimerung sind ja die Ansätze beider Verfahren, einmal werden Zeichenketten betrachtet, das andere mal einzelne Zeichen wobei bestimmte Zeichenketten durch Burrows-Wheeler auch besser komprimiert werden.
was sind denn bei dir "normale" Dateien?
Pinoccio
2010-01-03, 18:26:09
Was bringt bei a) langen Textdateien b) normalen Dateien mehr?
- Wörterbuchverfahren wie LZW, LZ77, LZ78, ...
- Burrows-Wheeler mit Move-to-front und dann Entropieoptimierung (Huffman)?
Wie kann man überhaupt beide Ansätze sinnvoll kombinieren? Entropieoptimerung sind ja die Ansätze beider Verfahren, einmal werden Zeichenketten betrachtet, das andere mal einzelne Zeichen wobei bestimmte Zeichenketten durch Burrows-Wheeler auch besser komprimiert werden.Übersichtstest zahlreicher Verfahren (http://www.squeezechart.com/main.html), so als Ausgangspunkt.
mfg
Das sind massig Packprogramme in einer Riesenliste, die mir nichts nützt.
was sind denn bei dir "normale" Dateien?Ausführbare Programme.
Pinoccio
2010-01-03, 19:39:26
Das sind massig Packprogramme in einer Riesenliste, die mir nichts nützt.:confused:
In der letzten Spalte steht, womit komprimiert wird. Mit STRG+F findet man, daß über alles Huffman hinter LZ und Konsorten liegt, bei Sourcen (Textdateien!) sogar sehr deutlich.
Deutlich besser sind praktisch alle Entropie-Kodierer.
mfg
ich habe beim Thread-Titel fasst nen Orgasmus bekommen
LZ77 ist i.A. besser bei ausführbaren Programmen, solange es sich um "einfache" Algorithmen handelt
über die Theorie der einzelnen Verfahren kann ich gern eine kleine Abhandlung schreiben, aber nicht jetzt
-LZ77 ist kein Wörterbuchverfahren, grob lassen sich die LZ-Verfahren in LZ77-Klassen und LZW-Klassen einteilen
-es werden indirekt immer Zeichenketten betrachtet (BWT besitzt dabei sowas wie einen unlimited Context)
-du musst zwischen Modellierung und Codierung unterscheiden
Eine andere Seite mit großen Vergleichstests:
http://www.maximumcompression.com/index.html
NanoZip ist ziemlich gut und basiert auf BWT.
NanoZip ist ziemlich gut und basiert auf BWT.
ich verwette meinen Schlüpfer darauf das die besseren Verfahren von NanoZip nicht auf BWT basieren. BWT ist auch nur der Modellierungsteil.
-LZ77 ist kein Wörterbuchverfahren, grob lassen sich die LZ-Verfahren in LZ77-Klassen und LZW-Klassen einteilendas ist eher ansichtssache. es gibt zwar kein explizites woerterbuch, aber man benutzt die vorherigen zeichen im sliding window als woerterbuch indem man index+groesse angibt. lzw erspart einem die groessenangabe indem man jede moeglichkeit (mehr oder weniger) ueber einen index addressiert, aber ich sehe keinen grund lz77 als nicht woerterbuchverfahren zu bezeichnen.
ein gutes beispiel ist LZMA, so wie es in 7z implementiert ist, nutzt es wohl die ganze detei als woerterbuch, entsprechend verlangt es auch unmengen an ram zur dekompression.
das ist eher ansichtssache.
sicher
es gibt zwar kein explizites woerterbuch, aber man benutzt die vorherigen zeichen im sliding window als woerterbuch indem man index+groesse angibt.
es ist bei LZ77-Verfahren kein Index, sondern einen relative Positionsangabe+Länge. Bei LZW verwendet man den absoluten Index im Wörterbuch.
Es ist also schon ein wichtiger Unterschied imo.
lzw erspart einem die groessenangabe indem man jede moeglichkeit (mehr oder weniger) ueber einen index addressiert, aber ich sehe keinen grund lz77 als nicht woerterbuchverfahren zu bezeichnen.
lzw wird doch garnicht mehr verwendet, weil zu schlecht. Der Index besitzt an sich keine wirkliche für den Codierungsvorgang verwertbare Struktur mehr.
hast du einen langen String wie z.B. "aaaaaaa" baut LZW bei jedem neuen Zeichen einen längeren String zusammen. LZ77 kann mit einem Greedy-Lookahead den gesammten String sofort ersetzen.
ein gutes beispiel ist LZMA, so wie es in 7z implementiert ist, nutzt es wohl
die ganze detei als woerterbuch, entsprechend verlangt es auch unmengen an ram zur dekompression.
so einfach ist das nicht. hast du alle 5MB in der Datei ein "hallo" wird LZMA nen Teufel tun und es ersetzen. Theoretisch können lange Strings über eine große Distanz ersetzt werden, das ist alles.
- Burrows-Wheeler mit Move-to-front und dann Entropieoptimierung (Huffman)?
MTF ist auch die einfachste Variante. Moderne Verfahren benutzen deshalb eine strukturierte Kodierung. Da kommt man schon nah an einfache PPM-Verfahren ran.
Wie kann man überhaupt beide Ansätze sinnvoll kombinieren?
wenn du vom Modellierungsaspekt redest gibt es da unterschiedliche Möglichkeiten
ich beschreibe mal ein anderes Verfahren, da BWT etwas exotisch ist
Derzeit verwendete Programme benutzen entweder LZ77-Verfahren als Basis oder PPM Verfahren
Mit LZ77 meine ich ein Verfahren was in einem gleitenden Fenster einen String an der aktuellen Position mit einem n-Tupel aus der Vergangenheit ersetzt.
Das Original LZ77 speichert dabei ein 3-Tupel (Distanz,Anzahl,nächstes Zeichen), was aber problematisch ist, wenn die Datei schlecht zu kodieren ist,
da man dann jedes Literal-Byte als (0,0,Zeichen) kodieren müsste. Die heutigen Verfahren basieren dabei auf LZSS, bei dem ein 1-Bit Marker angibt ob es sich um ein Literal-Byte oder um einen String handelt.
Das heißt bei fester Fenstergröße von 64kb, und maximaler String-Länge von 256, benötigt man 1+16+8=25 Bit um einen String der max. Länge zu ersetzen, und 9Bit um ein Zeichen zu speichern.
Erste Verbesserungen stellen VariableLengthCodes für die Stringlängen dar (z.B. Golomb).
Frühe Zip-Varianten verwendeten dann statisches Shannon-Fano-Coding oder Huffman-Coding für Literal-Bytes und String-Längen,
d.h. der entstandene Codebaum wird mitgespeichert, und zur Codegenerierung nur die jeweils absoluten Häufigkeiten herangezogen.
ARJ, PkZip und RAR arbeiten so.
Weitere Verbesserungen benötigen das Verständniss eines zusätzlichen Verfahrens: PPM (Prediction by Partial Match).
PPM entsteht wenn wir zur Modellierung der Wahrscheinlichkeiten nicht nur (wie oben) die absoluten Häufigkeiten nehmen,
sondern diese Häufigkeiten in Abhängigkeit von den vorangegangenen n Zeichen (Kontext,bedingte Wahrscheinlichkeit) ausdrücken.
Das Problem ist jetzt, das ein Huffman-Baum der Ordnung 1 schon relativ viel Speicherplatz einnehmen würde, obwohl die statistische Modellierung i.A. genauer ist.
Adaptive Huffmancodierung ist aber zu langsam weswegen man die modellierten Wahrscheinlichkeiten durch arithmetische oder Bereichs-Codierung speichert, und dabei eine adaptive Kontextstruktur aufbaut.
Die Idee besteht also darin, das die Auftritts-Wahrscheinlichkeit eines Zeichens höher ist, wenn wir dessen Kontext betrachten.
Z.B. ist die Wahrscheinlichkeit nach "hell" ein "o" zu bekommen höher, als ein "z", wenn wir englischen Text betrachten.
Da die Struktur dynamisch ist, kann sich das Verfahren der Gegenwart anpassen, um die Wahrscheinlichkeit zu maximieren das nächste Zeichen richtig zu "erraten".
Bei PPM-Modellen enstehen viele Schwierigkeiten, z.B. die optimale Behandlung von Zeichen die neu sind, oder die Frage wie die optimale Kontextlänge (1-n Zeichen) zu wählen sind.
PPM Verfahren sind LZ-Verfahren bei Texten haushoch überlegen, schwächeln aber bei Binärdaten (Verständlich da diese auf Bytebene eine geringere Kontextabhängigkeit aufweisen).
Ein auf Geschwindigkeit optimiertes PPM Verfahren wird in 7-Zip und den neueren WinRAR Versionen verwendet.
Zurück zu LZ77. Stellt man sich ein PPM-Verfahren simplifiziert als Kontext+Zählprozess vor,
kann man das Prinzip auch auf das LZ-Verfahren anwenden. Erstens können wir die Markierbits ersetzen (arithmetische Codierung erlaubt die Speicherung der exakten Wahrscheinlichkeit),
und diese zusätzlich mit einem Kontext ausstatten z.B. die letzten n-Markerbits also einen Kontext der Größe 2^n.
Die Literal-Bytes nun durch eine direkte PPM-Methode (z.B. Ordnung 1 wie bei LZMA) ersetzen usw. Der Phantasie sind bei der Kontextmodellierung keine Grenzen gesetzt und da existieren unterschiedliche Hybride Ansätze. Vor allem das effiziente Speichern der Distanzen ist aufwendig, aber wichtig, da sie am meisten Platz verwenden und die Schwachstelle der LZ-Verfahren darstellen.
Eine Möglichkeit stellen dabei die LZP Verfahren da (WinRK basiert auf diesen Ideen). Dabei wird nicht die Distanz gespeichert sondern der Kontext (die Vergangenheit) ist die eindeutige Markierung für die Distanz. Man speichert dann nur noch Literal-Bytes und Längen. Problem: optimale Kontextlänge und Updatestrategien für die Kontextstruktur um maximales Matching zu erreichen. Natürlich sind auch Mischansätze denkbar.
Die derzeit besten Verfahren nutzen die PPM-Idee auf Bitebene.
Zusätzlich werden z.B. mehrere PPM-Modelle unterschiedlicher Kontextlänge miteinader gewichtet um das nächste Bit so gut wie möglich vorhersagen zu können, aber auch andere Modelle wie LZ77, oder auf Bilder/Audio optimierte Verfahren können in den Gewichtungsprozess eingebracht werden. PAQ ist solch ein Verfahren.
edit:
etwas Wichtiges, was ich noch vergessen habe, ist die Verwendung von Postfiltern.
Die oben diskutierten Verfahren lassen sich für bestimmte Datentypen verbessern.
Bei Binär-Dateien kann man absolute durch relative Sprungadressen ersetzen, oder Bilder/Audio-Dateien mittel umfangreichen DPCM-Predikatoren filtern.
Anschließend verwendet man auf den gefilterten Daten den ursprünglichen Kompressionsalgorithmus.
Natürlich kommt das nicht an speziell auf diese Datentypen angepasste Algorithmen heran, ist aber trotzdem oft eine gute Verbesserung.
ich hoffe ich konnte dir irgendwie helfen, wenn du Verständnissfragen hast frag,
denn ich habe das alles auch schon programmiert :freak:
Ungenauigkeiten sind allerdings meinem Gedächtniss geschuldet
looking glass
2010-01-04, 22:52:59
Och von mir aus kannst Du ruhig weiter machen, hört sich alles sehr interessant an (Nein das ist nicht ironisch gemeint, ich finde das wirklich interessant, solang nicht zu viele Insiderbegriffe verwendet werden).
naja, ich denke, das sollten dann schon konkrete Fragen sein.
Ich weiß, kaum einer hier weiß was ein Greedy-Lookahead ist, aber das ist auch nicht wichtig fürs Verständniss. Das mit der Kontextstruktur ist allerdings schwieriger zu verstehen,
aber wenn man es mal programmiert hat, sieht man aber wie einfach es eigentlich ist, auch wenn die mathematische Theorie dahinter komplex ist.
Nachfolgend die schematische Darstellung des PPM-Verfahrens
Teil 1)
Kurz zur Erinnerung: wir suchen ein dynamisches Verfahren, welches die Wahrscheinlichkeit maximiert, das nächste Zeichen im Datenstrom richtig zu erraten.
Grundlegendes Prinzip ist dabei die Annahme, das diese Wahrscheinlichkeit größer wird, wenn der Kontext (Vergangenheit) länger ist (*).
Im PPM-Verfahren wird dabei (als Grundlage) die Häufigkeit gezählt mit der jedes Zeichen in Abhängigkeit von dessen Kontext vorkommt.
Hierfür werden bei verschiedenen Verfahren unterschiedliche Datenstrukturen verwendet. Bei einem Kontext der Ordnung-1 Byte, reicht ein Array mit 2^16 Einträgen.
Höherwertige Verfahren verwenden spezielle (platzsparende) Baumstrukturen, die man bequem entlang des Kontextes von oben nach unten oder umgekehrt durchlaufen kann.
Was schneller ist, hängt von der jeweiligen Situation und dessen Zielen ab.
Gehen wir nun also davon aus, dass wir eine Datenstruktur besitzen bei der wir an der aktuellen Datenstromposition, alle relativen Häufigkeiten der schon verarbeiteten Zeichen kennen.
Die Frage ist, was passiert wenn wir ein Zeichen bekommen was noch nicht in unserer Kontextstruktur enthalten ist, was auch automatisch immer dann passiert wenn wir einen Kontext haben,
den wir noch nicht gesehen haben. Eine Möglichkeit nach (*) zu verfahren, wäre bei einem Zeichen das im aktuellen Kontext noch nicht erschienen ist,
ein Escape-Symbol im n-Byte Kontext zu verwenden und das Zeichen mit einer fixen Wahrscheinlichkeit zu speichern, d.h. bei 1-Byte Zeichen mit z.B. 1/256.
Anschließend wird das Zeichen mit dem neuen Zähler 1 in die Kontextstruktur übernommen. Problem hierbei ist, das Kontexte der höheren Ordnung zwar gute Vorhersagen sind,
diese jedoch oft dünn besiedelt sind. Das heißt, man erzeugt einen codierten Strom mit vielen Escape-Sequenzen+komplette Literalbytes, weil der aktuelle Kontext neu ist.
In der Zeichenkette "abcada" existieren z.B. allein 4 unterschiedliche Kontexte der Ordnung-1.
Es hindert uns allerdings niemand daran, Informationen aus Kontexten niederer Ordnung mitzuzählen und auszuwerten.
Das heißt man startet im Kontext höchster Ordnung. Ist der Kontext unbekannt, schickt man ein Escape-Symbol und schaut ob der Kontext der Ordnung n-1 existiert,
bis zu Ordnung -1 bei der jedem Zeichen eine fixe Wahrscheinlichkeit zugewiesen wird.
Beispiel (Ordnung-1):
Anfangskontext=leerer Kontext
Ausgabewahrscheinlichkeiten des aktuellen Zeichens
+ Zähler der Kontextstruktur, dabei werden Zähler der unteren Kontexte auch bei vorhandenem höherem Kontext mit erneuert.
"ababba" bei 8-Bit Zeichen, Häufigkeit für esc ist in jedem Kontext 1
ausgabe wkt. der zeichen update
1. esc,esc,"a" 1/1, 1/1, 1/256 " |a"=1,"a"=1
2. esc,esc,"b" 1/1, 1/2, 1/256 " |a"=1,"a|b"=1,"a"=1,"b"=1
3. esc,"a" 1/1, 1/3 " |a"=1,"a|b"=1,"b|a"=1,"a"=2,"b"=1
4. "b" 1/2 " |a"=1,"a|b"=2,"b|a"=1,"a"=2,"b"=2
5. esc,"b" 1/2, 2/5 " |a"=1,"a|b"=2,"b|a"=1,"b|b"=1,"a"=2,"b"=3
6. "a" 1/2 " |a"=1,"a|b"=2,"b|a"=2,"b|b"=1,"a"=3,"b"=3
Nächster Teil: Escape/Update-Strategien, Codierung der Wahrscheinlichkeiten
Pinoccio
2010-01-08, 22:17:15
Ich freue mich immer über deine Beitrag, aber hier befürchte ich, daß man ihn nur versteht, wenn man schon vorher weiß, wovon du redest. (Ähnlich wie bei Rekursion ;D)
mfg
wenn man schon vorher weiß, wovon du redest.
die Posts sind chronologisch, oder verstehst du was nicht :D ?
wobei ich zugeben muss, dass vieles sehr Allgemein gehalten ist,
ob das nun jetzt gut oder schlecht ist kann ich nicht beurteilen
Was bringt bei a) langen Textdateien b) normalen Dateien mehr?
- Wörterbuchverfahren wie LZW, LZ77, LZ78, ...
- Burrows-Wheeler mit Move-to-front und dann Entropieoptimierung (Huffman)?
Wie kann man überhaupt beide Ansätze sinnvoll kombinieren? Entropieoptimerung sind ja die Ansätze beider Verfahren, einmal werden Zeichenketten betrachtet, das andere mal einzelne Zeichen wobei bestimmte Zeichenketten durch Burrows-Wheeler auch besser komprimiert werden.
Anschauen, da wird alles behandelt:
http://users.minet.uni-jena.de/~sack/SS08/RNIT08-materialien.htm#kodierung
Übrigens, Top Professor, so einen hätte ich auch gerne gehabt.
Das lese ich mir in der nächsten Zeit alles mal in Ruhe durch. Diese Tage habe ich leider nicht die Zeit dafür.
Ich brauche es aber sehr einfach gehalten. Zum Beispiel habe ich überlegt, bei einem Wörterbuchverfahren die Indizes entropieoptimiert zu speichern, also oft genutzte Indizes mit kurzen Bitlängen zu versehen. Wo man da Bits in Form eleganter Kodierung sparen kann, ist für mich noch nicht so wichtig.
Mir geht es nicht um Feinheiten der optimalen Speicherung, sondern um ein Grundverständnis. Ich hatte mal einen Zweipass-RLE-Algo und später einen Einpass-RLE-Algo geschrieben. An einem LWZ-ähnlichen Verfahren scheiterte ich schon, obwohl mir die Grundidee klar war. Möglicherweise ist Burrows-Wheeler mit Move-to-Front und anschließendem Huffman-Kodierung (oder arithmetischer Kodierung) aber besser. Dann würde ich mich in der Richtung weiter belesen. Alles dazu hatten wir im Studium, aber ein tieferes Verständnis habe ich noch nich. Zum Beispiel wäre doch mal interessant, ob sich ein Text der mit BW+MTF für die darauffolgende Entropiekodierung optimiert wurde, mit einem zweiten BW+MTF-Pass noch etwas weiter verbessern lässt.
Bei der erwähnten LZW-Methode die ich mal implementieren wollte, aber aufgrund meiner falschen Programmierung nur Stuss ausgab, gab es komprimierungstechnisch Overhead, da immer ein neues Wort angelegt wird wenn es noch nicht im Wörterbuch ist. Bei "MISSIMISSI" würde es ausreichen, nur "MISSI" als Wort zu speichern. Wie man das erreichen kann, wäre ganz interessant aber so weit bin ich eigentlich noch nicht. Man müsste mehr Zeichen als nur Puffer + nächstes Zeichen betrachten, das sind dann aber schon fortgeschrittene Überlegungen.
Wenn man eine Huffman-Kodierung für einen großen Text blockweise macht, hätte ich die Idee, pro Block zu prüfen ob es sinnvoll ist einen neuen Huffman-Baum zu speichern oder den alten weiterzunutzen. Nicht klar ist mir, ob man auf diese Weise besser komprimieren kann als wenn ein einziger Huffman-Baum für den gesamten Text genutzt wird.
Möglicherweise ist Burrows-Wheeler mit Move-to-Front und anschließendem Huffman-Kodierung (oder arithmetischer Kodierung) aber besser.
sicher, lass das mit dem LZW-Verfahren
Zum Beispiel wäre doch mal interessant, ob sich ein Text der mit BW+MTF für die darauffolgende Entropiekodierung optimiert wurde, mit einem zweiten BW+MTF-Pass noch etwas weiter verbessern lässt.
sehr unwahrscheinlich
Man müsste mehr Zeichen als nur Puffer + nächstes Zeichen betrachten, das sind dann aber schon fortgeschrittene Überlegungen.
macht man bei LZ77 doch automatisch, also ein LookAhead-Buffer um die String-Vergleiche durchzuführen
Wenn man eine Huffman-Kodierung für einen großen Text blockweise macht, hätte ich die Idee, pro Block zu prüfen ob es sinnvoll ist einen neuen Huffman-Baum zu speichern oder den alten weiterzunutzen. Nicht klar ist mir, ob man auf diese Weise besser komprimieren kann als wenn ein einziger Huffman-Baum für den gesamten Text genutzt wird.
ne gewisse Adaptivität ist auch mit Huffman-Bäumen realisierbar.
Allerdings wird diese recht kompliziert Variante von einem simplen Zähl PPM-Algorithmus jederzeit geschlagen und ist daei noch schneller.
Dazu brauchst du ja nur ein Array mit 2^8 Einträgen, und zählst darin das Vorkommen jedes Zeichens dynamisch.
@aths
wärest du an C-Code interessiert, der einen simplen adaptiven Modellierer der Ordnung-0 implementiert?
also sozusagen das was als Letztes über diesem Post steht
Vielleicht hab ich morgen etwas Zeit...nur so zum Spass? ;)
Hallo,
bevor ich mir Code ansehe, meine ich, erst mal "philosophisches" Verständnis zu benötigen ob, und wenn ja warum eine aufs einzelne Zeichen bezogene Entropiekodierung oft besser als Wörterbuchkodierung ist.
Hallo,
bevor ich mir Code ansehe, meine ich, erst mal "philosophisches" Verständnis zu benötigen ob, und wenn ja warum eine aufs einzelne Zeichen bezogene Entropiekodierung oft besser als Wörterbuchkodierung ist.
lass mich versuchen es so zu erklären. Jeder Packalgorithmus modelliert den empfangenen Datenstrom auf eine bestimmte Art und Weise. Wörterbuchverfahren sind dabei darauf angewiesen das die Struktur der Daten (auf eine gewisse Art) sich wiederholende Zeichenketten (auf Bytebene) enthält. Kontext-Modellierer können komplexere Strukturen erfassen und sind deswegen Wörterbuchverfahren meist überlegen.
Man kann die häufigsten Zeichen auf kurze Bitlängen umkodieren und somit Platz sparen (Huffman, arithmetische Komprimierung.) Oder man kann sich bei sich wiederholenden Zeicheketten nur doch Verweise auf diese Wörter speichern (Wörterbuchverfahren mit diversen unterschiedlichen Implementierungen. Die Index-Liste ist zudem Huffman-komprimierbar.)
Wenn ich das kontestabhängige Verfahren richtig verstehe, versucht er, das nächste Zeichen zu erraten. Geringe Abweichungen (nächsthäufigere Zeichen) nehmen nur kurze Bitlängen ein. Größere Abweichungen (sehr unwahrscheinliche Zeichen) brauchen lange Bitlängen. Während des Entpackens muss es also irgendwie eine Tabelle gebe, welche diese Zeichen speichert, diese Tabelle muss laufend geändert werden.
Von wie vielen der letzten Zeichen sollte diese Tabelle aber abhängig sein? Letztenendes ist es doch vom Ansatz her ein Wörterbuchverfahren, jedenfalls wenn viele der bisher dekodierten Zeichen zum Aufbau der Tabelle genutzt werden, welches Zeichen jetzt wahrscheinlich kommt bzw. welche Zeichen möglich, aber unwahrscheinlich sind.
Man kann die häufigsten Zeichen auf kurze Bitlängen umkodieren und somit Platz sparen (Huffman, arithmetische Komprimierung.) Oder man kann sich bei sich wiederholenden Zeicheketten nur doch Verweise auf diese Wörter speichern (Wörterbuchverfahren mit diversen unterschiedlichen Implementierungen. Die Index-Liste ist zudem Huffman-komprimierbar.)
ja das ist eine Möglichkeit der Kompression. Zusätzlich musst du aber bedenken, das Huffman-Kodierung nur optimal ist, wenn die Wahrscheinlichkeit der Zeichen einer Potenz 2^n entspricht. Statische Huffman-Bäume höhere Ordnung sind dagegen nicht praktikabel, und dynamische zu langsam. Vergiss Huffmann einfach wenn es um moderne Verfahren geht. Worauf ziehlte der Teil jetzt eigentlich ab? Habe das nicht ganz verstanden?
Wenn ich das kontestabhängige Verfahren richtig verstehe, versucht er, das nächste Zeichen zu erraten. Geringe Abweichungen (nächsthäufigere Zeichen) nehmen nur kurze Bitlängen ein. Größere Abweichungen (sehr unwahrscheinliche Zeichen) brauchen lange Bitlängen. Während des Entpackens muss es also irgendwie eine Tabelle gebe, welche diese Zeichen speichert, diese Tabelle muss laufend geändert werden.
die "Tabelle" ist dynamisch. Kodierer und Dekodierer haben zu jedem Zeitpunkt das selbe Modell.
Von wie vielen der letzten Zeichen sollte diese Tabelle aber abhängig sein?
kommt drauf an, wie man die Verbundwahrscheinlichkeit berechnet. So wie ich das mit den Escape-Codes demonstriert habe sind ca. 4-8 praktikabel.
Letztenendes ist es doch vom Ansatz her ein Wörterbuchverfahren, jedenfalls wenn viele der bisher dekodierten Zeichen zum Aufbau der Tabelle genutzt werden, welches Zeichen jetzt wahrscheinlich kommt bzw. welche Zeichen möglich, aber unwahrscheinlich sind.
nein, ein Wörterbuchverfahren ist ein Substitutionsverfahren. D.h. eine Zeichenkette wird mit einem Index/Verweis oder Ähnlichem ersetzt!
Ein Kontextmodellierer macht eine Aussage über die Wahrscheinlichkeitsverteilung der Zeichen in Abhängigkeit von der Vergangenheit. Natürlich sind gewisse Datenstrukturen äquivalent aber die Philosophie dahinter eine andere.
Vergiss aber nicht, das innerhalb einer modernen Implementierung beides ineinader fließt.
also Wörterbuchverfahren+Kontextmodellierung für die Verweise
oder Kontextmodellering mit Wörterbuch-Präprozessor.
vBulletin®, Copyright ©2000-2024, Jelsoft Enterprises Ltd.