Markus Stengel, Universität Tübingen, Juni 2002



LZxx Kompressionsverfahren

und

Anwendungsmöglichkeiten






Vorschau

  1. LZxx-Verfahren und Beispiele

  2. Pressestimmen

  3. Entropie

  4. Anwendungen

    1. Spracherkennung

    2. Autorenidentifikation

    3. Sprachklassifizierung

    4. weitere Anwendungen

  5. Quellen





1. Kompressionsverfahren





LZ77

Begriff

Erklärung

Input Stream

„Eingabestrom“: zu komprimierende Sequenz von Zeichen (Character)

Character

„Zeichen“: das zugrundeliegende Datenelement im Eingabestrom (Input Stream)

Coding Position

Position des character's im Eingabestrom, das gerade kodiert wird (Anfang des Lookahead Buffer's)

Lookahead Buffer

die Zeichenfolge von der Coding Position bis zum Ende des Input Stream's

Window

Das „Fenster“ der Größe W enthält die W Zeichen vor der coding position, also die letzten W bearbeiteten Zeichen

Pointer

verweist auf die letzte Übereinstimmung im Fenster und gibt die Länge derselben an





  1. setze der coding position auf den Anfang des Eingabestroms

  2. finde die längste Übereinstimmung im Fenster für den lookahead buffer

  3. gib das Paar (P,C) mit der folgenden Bedeutung zurück:

  4. ist der lookahead buffer nicht leer, setze die coding position und das Fenster auf den character nach C und wiederhole Schritt 2



Eingabestrom:

Position

1

2

3

4

5

6

7

8

9

10

character

A

A

B

C

B

B

A

B

C

X

Kodierungsablauf:

Schritt

Position

Übereinst.

Zeichen

Ausgabe

1

1

--

A

(0,0) A

2

2

A

B

(1,1) B

3

4

--

C

(0,0) C

4

5

B

B

(2,1) B

5

7

A B C

X

(5,3) X







LZ78

Begriff

Erklärung

Charstream

„Zeichenstrom“: zu komprimierende Sequenz von Zeichen (character)

Character

Grundlegendes Datenelement in einem charstream

Prefix

„Präfix“: eine Sequenz von Zeichen, die einer anderen vorhergeht

String

Das prefix zusammen mit dem character, dem es vorhergeht

Code word

Grundlegendes Datenelement im code stream; Es repräsentiert einen string aus dem dictionary

Code stream

Die Sequenz der code words und characters (also die Ausgabe des Kompressionsalgorithmus)

Dictionary

Eine Tabelle mit strings als Einträge. Jedem string wird entsprechend seiner ID im dictionary ein code word zugeordnet

Current prefix

Das prefix, das gerade vom Kompressionsalgorithmus bearbeitet wird. Symbol: P

Current character

Wird vom Kompressionsalgorithmus ermittelt. Im Allgemeinen ist dies der character, dem das aktuelle prefix vorangeht. Symbol: C

Current code word

Das code word, das gerade vom Dekompressionsalgorithmus bearbeitet wird. Es wird mit W bezeichnet, und die strings, die es repräsentiert, als string.W







Eingabestrom:

Position

1

2

3

4

5

6

7

8

9

Zeichen

A

B

B

C

B

C

A

B

A

Kodierungsablauf:

Schritt

Position

dictionary

Ausgabe

1

1

A

(0,A)

2

2

B

(0,B)

3

3

B C

(2,C)

4

5

B C A

(3,A)

5

8

B A

(2,A)







Weitere LZxx-Kompressionsverfahren











2. Pressestimmen









3. Entropie



Im Folgenden soll die Definition von Chaitin-Kolmogorov gelten:
Die Entropie einer Zeichenfolge ist die Länge (in Bits) des kleinsten Programms, welches die Zeichenfolge produziert.








4. Anwendungen



Vorschau



Distanz
Der Quotient aus der Länge eines komprimierten Textes und der unkomprimierten Länge strebt gegen die Entropie des Zeichenstroms.








Symbol

Bedeutung

S

unkomprimierte Text

Z

komprimierter (gezippter) Text

s

Entropie pro Zeichen des Quelltextes



für



In anderen Worten:

Der Text wird nicht auf die beste Weise kodiert, aber je länge er ist, umso mehr nähert er sich dem Optimum an.





Relative Entropie
Die relative Entropie gibt an, wieviel Speicherplatz verschwendet wird, wenn eine Zeichenfolge mit einer Methode komprimiert wird, die für eine andere Folge optimiert wurde.






Symbol

Bedeutung

α

ein Zeichenstrom α

β

ein Zeichenstrom β

A

lange Sequenz von α

a

kurze Sequenz von α

B

lange Sequenz von β

b

kurze Sequenz von β

Zahl der Zeichen von b

A+b

Konkatenation von b an A, anschließendes komprimieren (zippen)

LX

Länge eines gezippten Textes X in Bits

Das Maß für die Länge von b in der für A optimierten Kodierung:

In anderen Worten:

Sind α und β Texte in verschiedenen Sprachen, so ist ein Maß für die Schwierigkeit, die eine Person mit der Muttersprache α hat, einen Text in der Sprache β zu lesen





Eigenschaften des Verfahrens:









Anwendung: Spracherkennung



Ziel

Automatische Erkennung der Sprache eines Textes

Gegeben

  • Text X

  • eine Sammlung langer Texte in sovielen Sprachen wie möglich

Ablauf

  • an alle Texte Ai in allen Sprachen wird ein Auszug x des Textes X angehängt

  • Messung der Unterschiede mittels

  • der Text mit dem kleinsten ist in derselben Sprache geschrieben

Versuch

10 Texte in je 10 Sprachen:
Dänisch, Deutsch, Englisch, Finnisch, Französisch, Holländisch, Italienisch, Portugiesisch, Schwedisch, Spanisch

⇨ Sammlung von 100 Texten

Ergebnis

  • jeder Text X mit einer Länge ≥ 20 Buchstaben Länge wurde der richtigen Sprache zugeordnet

Anwendung: Autorenidentifikation



Ziel

automatische Erkennung eines Textes zu einem Autor

Gegeben

  • Text X, der zugeordnet werden soll

  • eine möglichst große Sammlung von Texten bekannter Autoren in derselben Sprache wie Text X

Ablauf

  • an alle Texte Ai von allen Autoren wird ein Auszug x des Textes X angehängt

  • Suche nach dem Text Ai , dessen Unterschied minimal ist

Versuch

Sammlung von insgesamt 90 Texten von 11 italienischen Autoren



Autor

Textanzahl

Erste Wahl

Zweite Wahl

Alighieri

8

8

8

D'Annunzio

4

4

4

Deledda

15

15

15

Fogazzaro

5

4

5

Guicciardini

6

5

6

Macchiavelli

12

12

12

Manzoni

4

3

4

Pirandello

11

11

11

Salgari

11

10

10

Svevo

5

5

5

Vega

9

7

9

Summe

90

84

89



Ergebnis

  • Eindeutige Zuordnung des Textes in 93,3% der Fälle („erste Wahl“)

  • in der engen Auswahl, d.h. als schlechtestenfalls „zweite Wahl“ in 98,9% der Fälle


Bemerkung:

Anwendung: Sequenzklassifikation



Ziel

Klassifikation von Sprachen anhand von Texten

Gegeben

eine möglichst große Sammlung von Texten in jeweils sovielen Sprachen wie möglich

Probleme

  • Verfügbarkeit derselben langen Texte in vielen verschiedenen Sprachen

  • einheitliche Kodierung des Textes

Ablauf

  • Jeder Text in jeder Sprache wird an jeden der anderen Texte angehängt

  • Konstruktion einer Distanzmatrix, deren Elemente die Distanzen zwischen zwei Texten sind:

  • Normalisierung mit bzw.

  • Entropie keine Distanz im mathematischen Sinne
    ⇨ Matrixelemente sollen die Dreiecksungleichung erfüllen

  • Erzeugung des Sprachbaums aus der Distanzmatrix mittels der Margoliaschen Methode aus dem Softwarepaket PhylIP (Phylogeny Inference Package)

Versuch

  • In 52 europäischen Sprachen:
    „Die Allgemeine Erklärung der Menschenrechte“

  • Kodierung der Texte in UNICODE



Ergebnis

Alle linguistischen Hauptgruppen Romanisch, Keltisch, Germanisch, Ugro-Finnisch, Slavisch, Baltisch und Altaisch wurden erkannt

Zusammenfassung





Bemerkung

Die Arbeit von Benedetto, Caglioti und Loreto ist nicht die erste, die mit mathematischen Methoden literarische Texte auf Autorenschaft prüft:



Praxisbeispiel: Versuche eines Journalisten

Versuch 1: Informationsgehalt

Gegeben:



  1. reine Kompression:



  1. Sortierung:



  1. Randomisierung:





Versuch 2: Autorenidentifikation und Vergleich

Gegeben:



  1. Identifizierung des Autors:



  1. Vergleich kurze mit langen Artikeln:



Bemerkung:





5. Quellen











28