Shannon-Fano-Codierung - Shannon–Fano coding

Auf dem Gebiet der Datenkompression ist die Shannon-Fano-Codierung , benannt nach Claude Shannon und Robert Fano , ein Name für zwei verschiedene, aber verwandte Techniken zum Konstruieren eines Präfixcodes basierend auf einem Satz von Symbolen und deren Wahrscheinlichkeiten (geschätzt oder gemessen).

• Das Verfahren von Shannon wählt einen Präfixcode, bei dem einem Quellsymbol die Codewortlänge gegeben wird . Ein üblicher Weg zur Auswahl der Codewörter verwendet die binäre Erweiterung der kumulativen Wahrscheinlichkeiten. Diese Methode wurde in Shannons " A Mathematical Theory of Communication " (1948) vorgeschlagen, seinem Artikel, der das Gebiet der Informationstheorie einführt .${\displaystyle i}$${\displaystyle l_{i}=\lceil -\log_{2}p_{i}\rceil}$
• Das Verfahren von Fano teilt die Quellsymbole in zwei Sätze ("0" und "1") mit Wahrscheinlichkeiten so nahe wie möglich bei 1/2. Dann werden diese Mengen selbst in zwei Teile geteilt und so weiter, bis jede Menge nur noch ein Symbol enthält. Das Codewort für dieses Symbol ist die Folge von "0"en und "1"en, die aufzeichnet, auf welche Hälfte der Divisionen es fiel. Diese Methode wurde in einem späteren technischen Bericht von Fano (1949) vorgeschlagen.

Shannon-Fano-Codes sind insofern suboptimal , als sie nicht immer die geringstmögliche erwartete Codewortlänge erreichen, wie dies bei der Huffman-Codierung der Fall ist. Shannon-Fano-Codes haben jedoch eine erwartete Codewortlänge innerhalb von 1 Bit des Optimums. Die Methode von Fano erzeugt normalerweise eine Kodierung mit kürzeren erwarteten Längen als die Methode von Shannon. Die Methode von Shannon ist jedoch theoretisch einfacher zu analysieren.

Die Shannon-Fano-Kodierung sollte nicht mit der Shannon-Fano-Elias-Kodierung (auch bekannt als Elias-Kodierung), dem Vorläufer der arithmetischen Kodierung , verwechselt werden .

Benennung

In Bezug auf die Verwirrung in den beiden verschiedenen Codes, auf die mit demselben Namen verwiesen wird, schreiben Krajči et al:

Um 1948 schlugen sowohl Claude E. Shannon (1948) als auch Robert M. Fano (1949) unabhängig voneinander zwei verschiedene Quellencodierungsalgorithmen für eine effiziente Beschreibung einer diskreten speicherlosen Quelle vor. Obwohl sie unterschiedlich waren, wurden beide Schemata leider unter dem gleichen Namen Shannon-Fano-Codierung bekannt .

Für diese Verwechslung gibt es mehrere Gründe. Zum einen erwähnt Shannon in der Diskussion seines Kodierungsschemas Fanos Schema und nennt es „im Wesentlichen dasselbe“ (Shannon, 1948, S. 17). Zum anderen sind sowohl die Codierungsschemata von Shannon als auch Fano in dem Sinne ähnlich, dass sie beide effiziente, aber suboptimale präfixfreie Codierungsschemata mit ähnlicher Leistung sind

Die Methode von Shannon (1948), die vordefinierte Wortlängen verwendet, wird von Cover und Thomas, Goldie und Pinch, Jones und Jones sowie Han und Kobayashi als Shannon-Fano-Codierung bezeichnet . Es wird von Yeung Shannon-Codierung genannt .

Die Methode von Fano (1949), die eine binäre Division von Wahrscheinlichkeiten verwendet, wird von Salomon und Gupta als Shannon-Fano-Codierung bezeichnet . Es wird von Krajči et al. als Fano-Codierung bezeichnet .

Shannons Code: vordefinierte Wortlängen

Shannons Algorithmus

Shannons Methode beginnt mit der Entscheidung über die Länge aller Codewörter und wählt dann einen Präfixcode mit diesen Wortlängen aus.

Bei einer gegebenen Quelle mit Wahrscheinlichkeiten sind die gewünschten Codewortlängen . Hier ist die Deckenfunktion , also die kleinste ganze Zahl größer oder gleich . ${\displaystyle p_{1},p_{2},\dots,p_{n}}$${\displaystyle l_{i}=\lceil -\log_{2}p_{i}\rceil}$${\displaystyle \lceil x\rceil}$${\displaystyle x}$

Nachdem die Codewortlängen bestimmt wurden, müssen wir die Codewörter selbst auswählen. Ein Verfahren besteht darin, Codewörter in der Reihenfolge von den wahrscheinlichsten zu den am wenigsten wahrscheinlichen Symbolen auszuwählen, wobei jedes Codewort als das lexikographisch erste Wort der richtigen Länge ausgewählt wird, das die präfixfreie Eigenschaft beibehält.

Eine zweite Methode verwendet kumulative Wahrscheinlichkeiten. Zuerst werden die Wahrscheinlichkeiten in absteigender Reihenfolge geschrieben . Dann sind die kumulativen Wahrscheinlichkeiten definiert als ${\displaystyle p_{1}\geq p_{2}\geq \cdots \geq p_{n}}$

${\displaystyle c_{1}=0,\qquad c_{i}=\sum _{j=1}^{i-1}p_{i}{\text{ für }}i\geq 2,}$

so und so weiter. Das Codewort für Symbol wird als die ersten Binärziffern in der Binärerweiterung von gewählt . ${\displaystyle c_{1}=0,c_{2}=p_{1},c_{3}=p_{1}+p_{2}}$${\displaystyle i}$${\displaystyle l_{i}}$${\displaystyle c_{i}}$

Beispiel

Dieses Beispiel zeigt die Konstruktion eines Shannon-Fano-Codes für ein kleines Alphabet. Es gibt 5 verschiedene Quellsymbole. Angenommen, es wurden insgesamt 39 Symbole mit den folgenden Häufigkeiten beobachtet, aus denen wir die Symbolwahrscheinlichkeiten abschätzen können.

Symbol	EIN	B	C	D	E
Anzahl	fünfzehn	7	6	6	5
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128

Diese Quelle hat Entropiebits . ${\displaystyle H(X)=2.186}$

Für den Shannon-Fano-Code müssen wir die gewünschten Wortlängen berechnen . ${\displaystyle l_{i}=\lceil -\log_{2}p_{i}\rceil}$

Symbol	EIN	B	C	D	E
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128
${\displaystyle -\log_{2}p_{i}}$	1.379	2.480	2.700	2.700	2.963
Wortlängen ${\displaystyle \lceil -\log_{2}p_{i}\rceil}$	2	3	3	3	3

Wir können Codewörter der Reihe nach auswählen, indem wir das lexikographisch erste Wort der richtigen Länge auswählen, das die präfixfreie Eigenschaft beibehält. Offensichtlich erhält A das Codewort 00. Um die präfixfreie Eigenschaft beizubehalten, darf das Codewort von B nicht mit 00 beginnen, daher ist das lexikographisch erste verfügbare Wort der Länge 3 010. Wenn wir so fortfahren, erhalten wir den folgenden Code:

Symbol	EIN	B	C	D	E
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128
Wortlängen ${\displaystyle \lceil -\log_{2}p_{i}\rceil}$	2	3	3	3	3
Codewörter	00	010	011	100	101

Alternativ können wir die kumulative Wahrscheinlichkeitsmethode verwenden.

Symbol	EIN	B	C	D	E
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128
Kumulative Wahrscheinlichkeiten	0.000	0,385	0,564	0,718	0,872
...in binär	0,00000	0,01100	0.10010	0.10110	0,11011
Wortlängen ${\displaystyle \lceil -\log_{2}p_{i}\rceil}$	2	3	3	3	3
Codewörter	00	011	100	101	110

Beachten Sie, dass, obwohl die Codewörter bei den beiden Verfahren unterschiedlich sind, die Wortlängen gleich sind. Wir haben Längen von 2 Bit für A und 3 Bit für B, C, D und E, was eine durchschnittliche Länge von ergibt

${\displaystyle {\frac {2\,{\text{Bits}}\cdot (15)+3\,{\text{Bits}}\cdot (7+6+6+5)}{39\,{ \text{symbols}}}}\approx 2,62\,{\text{Bits pro Symbol,}}}$

die innerhalb eines Bits der Entropie liegt.

Erwartete Wortlänge

Für die Methode von Shannon erfüllen die Wortlängen

${\displaystyle l_{i}=\lceil -\log_{2}p_{i}\rceil\leq -\log_{2}p_{i}+1.}$

Daher erfüllt die erwartete Wortlänge

${\displaystyle \mathbb {E} L=\sum_{i=1}^{n}p_{i}l_{i}\leq \sum_{i=1}^{n}p_{i}(- \log_{2}p_{i}+1)=-\sum_{i=1}^{n}p_{i}\log_{2}p_{i}+\sum_{i=1} ^{n}p_{i}=H(X)+1.}$

Hier ist die Entropie , und das Quellcodierungstheorem von Shannon besagt, dass jeder Code eine durchschnittliche Länge von mindestens haben muss . Daher sehen wir, dass der Shannon-Fano-Code immer innerhalb eines Bits der optimalen erwarteten Wortlänge liegt. ${\displaystyle H(X)=-\textstyle \sum _{i=1}^{n}p_{i}\log _{2}p_{i}}$${\displaystyle H(X)}$

Fanos Code: Binäre Aufteilung

Umriss von Fanos Code

Bei der Methode von Fano werden die Symbole in der Reihenfolge von am wahrscheinlichsten bis am wenigsten wahrscheinlich angeordnet und dann in zwei Mengen geteilt, deren Gesamtwahrscheinlichkeiten möglichst gleich sind. Allen Symbolen werden dann die ersten Ziffern ihres Codes zugewiesen; Symbole im ersten Satz erhalten "0" und Symbole im zweiten Satz erhalten "1". Solange Mengen mit mehr als einem Mitglied übrig bleiben, wird derselbe Vorgang für diese Mengen wiederholt, um aufeinanderfolgende Ziffern ihrer Codes zu bestimmen. Wenn ein Satz auf ein Symbol reduziert wurde, bedeutet dies, dass der Code des Symbols vollständig ist und nicht das Präfix des Codes eines anderen Symbols bildet.

Der Algorithmus erzeugt ziemlich effiziente Codierungen mit variabler Länge; wenn die zwei kleineren Mengen, die durch eine Partitionierung erzeugt werden, tatsächlich die gleiche Wahrscheinlichkeit aufweisen, wird das eine Informationsbit, das verwendet wird, um sie zu unterscheiden, am effizientesten verwendet. Leider erzeugt die Shannon-Fano-Codierung nicht immer optimale Präfixcodes; der Satz von Wahrscheinlichkeiten {0,35, 0,17, 0,17, 0,16, 0,15} ist ein Beispiel dafür, dem nicht optimale Codes durch die Shannon-Fano-Codierung zugewiesen werden.

Fanos Version der Shannon-Fano-Codierung wird in der IMPLODE- Komprimierungsmethode verwendet, die Teil des ZIP- Dateiformats ist .

Der Shannon-Fano-Baum

Ein Shannon-Fano-Baum wird gemäß einer Spezifikation erstellt, die eine effektive Codetabelle definieren soll. Der eigentliche Algorithmus ist einfach:

1. Entwickeln Sie für eine gegebene Liste von Symbolen eine entsprechende Liste von Wahrscheinlichkeiten oder Häufigkeitszählungen, so dass die relative Häufigkeit des Auftretens jedes Symbols bekannt ist.
2. Sortieren Sie die Symbollisten nach Häufigkeit, wobei die am häufigsten vorkommenden Symbole links und die am seltensten vorkommenden rechts stehen.
3. Teilen Sie die Liste in zwei Teile, wobei die Gesamthäufigkeitszahlen des linken Teils so nah wie möglich an der Summe des rechten Teils liegen.
4. Dem linken Teil der Liste wird die Binärziffer 0 und dem rechten Teil die Ziffer 1 zugewiesen. Dies bedeutet, dass die Codes für die Symbole im ersten Teil alle mit 0 beginnen und die Codes im zweiten Teil alle beginne mit 1.
5. Wende die Schritte 3 und 4 rekursiv auf jede der beiden Hälften an, unterteile Gruppen und füge Bits zu den Codes hinzu, bis jedes Symbol ein entsprechendes Codeblatt im Baum geworden ist.

Beispiel

Wir fahren mit dem vorherigen Beispiel fort.

Symbol	EIN	B	C	D	E
Anzahl	fünfzehn	7	6	6	5
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128

Alle Symbole sind nach Häufigkeit sortiert, von links nach rechts (siehe Abbildung a). Setzt man die Trennlinie zwischen den Symbolen B und C, erhält man insgesamt 22 in der linken Gruppe und insgesamt 17 in der rechten Gruppe. Dadurch wird der Unterschied in den Summen zwischen den beiden Gruppen minimiert.

Bei dieser Division haben A und B jeweils einen Code, der mit einem 0-Bit beginnt, und die Codes C, D und E beginnen alle mit einer 1, wie in Abbildung b gezeigt. Anschließend erhält die linke Baumhälfte eine neue Teilung zwischen A und B, wodurch A auf ein Blatt mit Code 00 und B auf ein Blatt mit Code 01 gelegt wird.

Nach vier Divisionsprozeduren ergibt sich ein Baum von Codes. Im letzten Baum wurden den drei Symbolen mit den höchsten Frequenzen alle 2-Bit-Codes zugewiesen, und zwei Symbolen mit niedrigeren Zählungen haben 3-Bit-Codes, wie in der folgenden Tabelle gezeigt:

Symbol	EIN	B	C	D	E
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128
Erste Division	0		1
Zweite Division	0	1	0	1
Dritte Liga				0	1
Codewörter	00	01	10	110	111

Dies führt zu Längen von 2 Bit für A, B und C und pro 3 Bit für D und E, was eine durchschnittliche Länge von . ergibt

${\displaystyle {\frac {2\,{\text{Bits}}\cdot (15+7+6)+3\,{\text{Bits}}\cdot (6+5)}{39\,{ \text{symbols}}}}\approx 2,28\,{\text{Bits pro Symbol.}}}$

Wir sehen, dass die Methode von Fano mit einer durchschnittlichen Länge von 2,28 die Methode von Shannon mit einer durchschnittlichen Länge von 2,62 übertroffen hat.

Erwartete Wortlänge

Es wird von Krajči et al. gezeigt, dass die erwartete Länge von Fanos Methode die erwartete Länge hat, die oben durch begrenzt ist , wobei die Wahrscheinlichkeit des am wenigsten gemeinsamen Symbols ist. ${\displaystyle \mathbb{E} L\leq H(X)+1-p_{\text{min}}}$${\displaystyle p_{\text{min}}=\textstyle \min_{i}p_{i}}$

Vergleich mit anderen Kodierungsmethoden

Keiner der Shannon-Fano-Algorithmen kann garantiert einen optimalen Code generieren. Aus diesem Grund werden Shannon-Fano-Codes fast nie verwendet; Die Huffman-Codierung ist rechnerisch fast genauso einfach und erzeugt Präfixcodes, die immer die niedrigstmögliche erwartete Codewortlänge erreichen, unter der Einschränkung, dass jedes Symbol durch einen Code repräsentiert wird, der aus einer ganzen Zahl von Bits gebildet wird. Dies ist eine häufig unnötige Einschränkung, da die Codes in langen Sequenzen Ende-an-Ende gepackt werden. Wenn wir Gruppen von Codes gleichzeitig betrachten, ist die Symbol-für-Symbol-Huffman-Codierung nur dann optimal, wenn die Wahrscheinlichkeiten der Symbole unabhängig sind und eine halbe Potenz betragen, dh . In den meisten Situationen kann die arithmetische Codierung eine größere Gesamtkomprimierung erzeugen als entweder Huffman oder Shannon-Fano, da sie in Bruchzahlen von Bits codieren kann, die dem tatsächlichen Informationsgehalt des Symbols näher kommen. Die arithmetische Codierung hat Huffman jedoch nicht so abgelöst wie Huffman Shannon-Fano, sowohl weil die arithmetische Codierung rechenintensiver ist als auch weil sie durch mehrere Patente abgedeckt ist. ${\displaystyle \textstyle 1/2^{k}}$

Huffman-Codierung

Einige Jahre später gab David A. Huffman (1949) einen anderen Algorithmus an, der immer einen optimalen Baum für alle gegebenen Symbolwahrscheinlichkeiten erzeugt. Während der Shannon-Fano-Baum von Fano entsteht, indem man von der Wurzel zu den Blättern teilt, arbeitet der Huffman-Algorithmus in die entgegengesetzte Richtung, indem er von den Blättern zur Wurzel verschmilzt.

1. Erstellen Sie für jedes Symbol einen Blattknoten und fügen Sie ihn einer Prioritätswarteschlange hinzu , wobei die Häufigkeit des Auftretens als Priorität verwendet wird.
2. Während sich mehr als ein Knoten in der Warteschlange befindet:
   1. Entfernen Sie die beiden Knoten mit der niedrigsten Wahrscheinlichkeit oder Häufigkeit aus der Warteschlange
   2. Stellen Sie 0 bzw. 1 jedem Code voran, der diesen Knoten bereits zugewiesen ist
   3. Erstellen Sie einen neuen internen Knoten mit diesen beiden Knoten als Kinder und mit einer Wahrscheinlichkeit gleich der Summe der Wahrscheinlichkeiten der beiden Knoten.
   4. Fügen Sie den neuen Knoten zur Warteschlange hinzu.
3. Der verbleibende Knoten ist der Wurzelknoten und der Baum ist vollständig.

Beispiel mit Huffman-Codierung

Wir verwenden die gleichen Frequenzen wie für das Shannon-Fano-Beispiel oben, nämlich:

Symbol	EIN	B	C	D	E
Anzahl	fünfzehn	7	6	6	5
Wahrscheinlichkeiten	0,385	0,179	0,154	0,154	0,128

In diesem Fall haben D & E die niedrigsten Häufigkeiten und werden daher 0 bzw. 1 zugewiesen und mit einer kombinierten Wahrscheinlichkeit von 0,282 gruppiert. Das niedrigste Paar sind jetzt B und C, also werden ihnen 0 und 1 zugewiesen und mit einer kombinierten Wahrscheinlichkeit von 0,333 gruppiert. Dadurch haben BC und DE jetzt die niedrigsten Wahrscheinlichkeiten, so dass 0 und 1 ihren Codes vorangestellt und kombiniert werden. Es bleiben dann nur noch A und BCDE übrig, denen 0 bzw. 1 vorangestellt ist und die dann kombiniert werden. Dies lässt uns mit einem einzigen Knoten zurück und unser Algorithmus ist vollständig.

Die Codelängen für die verschiedenen Zeichen betragen diesmal 1 Bit für A und 3 Bit für alle anderen Zeichen.

Symbol	EIN	B	C	D	E
Codewörter	0	100	101	110	111

Daraus ergeben sich die Längen von 1 Bit für A und pro 3 Bit für B, C, D und E, was eine durchschnittliche Länge von ergibt

${\displaystyle {\frac {1\,{\text{bit}}\cdot 15+3\,{\text{bits}}\cdot (7+6+6+5)}{39\,{\text {Symbole}}}}\approx 2,23\,{\text{Bits pro Symbol.}}}$

Wir sehen, dass der Huffman-Code beide Arten von Shannon-Fano-Code übertroffen hat, die erwartete Längen von 2,62 und 2,28 hatten.

Anmerkungen

Verweise

• Fano, RM (1949). "Die Übermittlung von Informationen" . Technischer Bericht Nr. 65 . Cambridge (Mass.), USA: Forschungslabor für Elektronik am MIT.
• Shannon, CE (Juli 1948). "Eine mathematische Theorie der Kommunikation" . Bell System Fachzeitschrift . 27 : 379–423.