Textcodierung

Wie beim Morse-Code wird auch für die Codierung und Decodierung von Text eine Übersetzungs-Tabelle benötigt. In dieser Tabelle ist für jedes mögliche Zeichen einer Textnachricht eine Folge aus 0 und 1 zu finden:

	0100000	0	0110000	@	1000000	P	1010000	`	1100000	p	1110000
!	0100001	1	0110001	A	1000001	Q	1010001	a	1100001	q	1110001
"	0100010	2	0110010	B	1000010	R	1010010	b	1100010	r	1110010
#	0100011	3	0110011	C	1000011	S	1010011	c	1100011	s	1110011
$	0100100	4	0110100	D	1000100	T	1010100	d	1100100	t	1110100
%	0100101	5	0110101	E	1000101	U	1010101	e	1100101	u	1110101
&	0100110	6	0110110	F	1000110	V	1010110	f	1100110	v	1110110
'	0100111	7	0110111	G	1000111	W	1010111	g	1100111	w	1110111
(	0101000	8	0111000	H	1001000	X	1011000	h	1101000	x	1111000
)	0101001	9	0111001	I	1001001	Y	1011001	i	1101001	y	1111001
*	0101010	:	0111010	J	1001010	Z	1011010	j	1101010	z	1111010
+	0101011	;	0111011	K	1001011	[	1011011	k	1101011	{	1111011
,	0101100	<	0111100	L	1001100	\	1011100	l	1101100	|	1111100
-	0101101	=	0111101	M	1001101	]	1011101	m	1101101	}	1111101
.	0101110	>	0111110	N	1001110	^	1011110	n	1101110	~	1111110
/	0101111	?	0111111	O	1001111	_	1011111	o	1101111	DEL	1111111

Beispiel: Der Kleinbuchstabe t entspricht der Folge 1110100

Diese Tabelle wurde 1967 erstmals als Standard veröffentlicht unter der Bezeichnung American Standard Code for Information Interchange (ASCII) und bildet die Grundlage für die in heutigen Computern gebräuchliche Codierung von Textdaten (siehe Wikipedia).

Textkompression

Das Mobiltelefon der drei Roboter ist mit einem Kompressionsverfahren für Textnachrichten ausgestattet. Es handelt sich um ein verlustfreies Kompressionsverfahren, das sich eine Eigenart der deutschen Sprache zunutze macht. In der deutschen Sprache kommen immer wieder Doppelbuchstaben vor, wie dieser Satz schön illustriert. Die obenstehende Codierungstabelle wird deshalb mit folgender Regel ergänzt:

Kommt ein Buchstabe einmal vor, so setze ein 0 vor den Binärcode des Buchstaben,
kommt ein Buchstabe zweimal vor, so setze ein 1 vor den Binärcode des Buchstabens.

01010010	b
11010010	bb

Beispielnachricht

Im folgenden wird gezeigt, wie eine Textnachricht codiert werden kann und welche Auswirkungen die Kompression hat. Als Beispiel dient das Wort

Schifffahrtsgesellschaft

Ohne Kompression ist die Codierung relativ einfach: Jeder Buchstabe muss durch den entsprechenden Code der obenstehenden Tabelle ersetzt werden:

S	1010011
c	1100011
h	1101000
i	1101001
f	1100110
f	1100110
f	1100110
a	1100001
h	1101000
r	1110010
t	1110100
s	1110011
g	1100111
e	1100101
s	1110011
e	1100101
l	1101100
l	1101100
s	1110011
c	1100011
h	1101000
a	1100001
f	1100110
t	1110100

Fügt man die einzelnen Codeteile zusammen, so ergibt sich folgende, aus 168 bit (= 24 x 7) bestehende Nachricht:

1010011110001111010001101001110011011001 1011001101100001110100011100101110100111 0011110011111001011110011110010111011001 1011001110011110001111010001100001110011 01110100

Mit Kompressionsregel wird das Codieren etwas anspruchsvoller, denn nicht immer entspricht ein Zeichen genau einem Code. In der Beispielnachricht gibt es zwei Stellen, wo die Kompressionsregel eine Einsparung ermöglicht, indem zwei Zeichen durch einen Code repräsentiert werden:

S	01010011
c	01100011
h	01101000
i	01101001
ff	11100110
f	01100110
a	01100001
h	01101000
r	01110010
t	01110100
s	01110011
g	01100111
e	01100101
s	01110011
e	01100101
ll	11101100
s	01110011
c	01100011
h	01101000
a	01100001
f	01100110
t	01110100

Die Kompression hat sich in diesem Fall nicht gelohnt, denn die resultierende Nachricht besteht aus 176 bits (= 22 x 8) und ist somit länger als die unkomprimierte Nachricht:

0101001101100011011010000110100111100110 0110011001100001011010000111001001110100 0111001101100111011001010111001101100101 1110110001110011011000110110100001100001 0110011001110100

Denksportaufgabe: Gibt es andere Komprimierungsregeln, die effizienter sind bei der Kompression deutscher Sprache?

Das Dekomprimieren geschieht übrigens einfach in umgekehrter Reihenfolge:

1. Die Nachricht in Gruppen von 8 bits aufteilen
2. Für jede Gruppe von 8 bits die Entsprechung in der Codetabelle nachschauen

Weiter zur Musik-Codierung...

Hast du schon eine Lösung gefunden, dann kannst du sie hier überprüfen:

Lösung überprüfen