Informationstheorie und Textkategorisierung Anastasia Aftakhova — 14. Januar 2016 Literaturarbeit und Präsentation“ ” Seminar im Wintersemester 2015 · Friedrich-Schiller-Universität Jena 1 Einleitung 1.1 Information Was ist eine Information und Informationsgehalt? Die Information kann schlicht definiert werden als eine Menge Wissen oder Daten. Damit ist die Menge der Information untrennbar von ihrer Bedeutung. In der Informatik wird die Information aber nicht nach ihrer Bedeutung, sondern an ihrem Informationsgehalt I gemessen 1 I(x) = log2 = −log2 (px ), (1) px wo px die Auftrittswahrscheinlichkeit des Zeichens x ist [7]. Entropie H ist als Maß für den mittleren Informationsgehalt definiert und wird wie folgt berechnet: X H= pz I(pz ) (2) z∈Z Diese beiden Begriffe, sowie eine Menge von weiteren Konzepten und Theoreme wurden im Jahr 1948 vom Claude E. Shannon in seiner Arbeit Ä mathematical Theory of Communication” [7] erfasst, die eine fundamentale Grundlage für die heutige Informationstheorie geschaffen hat. 1.2 Kompression Motivation: Warum komprimieren? Die weltweite Digitalisierung hat die Informationserzeugung soweit beschleunigt, sodass heutzutage in sechzig Minuten soviel Daten produziert werden, wie vor ein paar Jahrzehnten mit allen Rechner zusammen nicht gespeichert werden könnten. So ist die Datenkompression unentbehrlich geworden. Kompressionsverfahren: mit Verlust, ohne Verlust? Es gibt verlustfreie und nicht verlustfreie Kompressionsverfahren. Kompression mit Verlust findet ihre Anwendung bei Bildern, Video- und Audiodateien, wo die Daten durch eine Qualitätsverschlechterung komprimiert werden können. Für Textdaten ist so eine Kompression ungeeignet, da der Verlust auch ganz kleiner Informationsmengen unzulässig ist. Ohne Verlust komprimieren: Wie geht denn das überhaupt? Verlustfreie Kompressionsverfahren benutzen die Redundanz der Daten um diese optimal umzukodieren. 1 2 Einige verlustfreie Kompressionsverfahren 2.1 Huffman-Kodierung Beschreibung: Das Verfahren sortiert die Zeichen nach deren Häufigkeiten (oder Wahrscheinlichkeiten) und kodiert diese entsprechend um. Die häufigsten Zeichen bekommen die kürzesten Codes, seltenste - die längsten. Damit wird die Gesamtlänge des Textes minimiert. Funktionsweise: Zunächst sollte für jedes Zeichen seine Häufigkeit oder Wahr- scheinlichkeit ermittelt werden. Dann wird ein Huffman-Baum konstruiert. Jedes Blatt des Baumes entspricht einem Zeichen. Die Kanten bekommen die Bezeichnungen: jede Kante zum linken Knoten eine 0, und jede rechte eine 1 (oder umgekehrt). Die Kodierung eines Zeichens ergibt sich aus der Folge der Bezeichnungen der Kanten, die die Wurzel mit dem entsprechendem Knoten verbinden. Anwendungen: Der Huffman-Algorithmus ist sehr beliebt für seine intuitive Implementierung und Effizienz. Obwohl zu dem aktuellen Zeitpunkt viele bessere Algorithmen vorliegen, wird die Huffman-Codierung immer noch bei den Dateitypen wie JPEG, ZIP und MP3 benutzt [3]. 2.2 Arithmetisches Kodieren Beschreibung: Der eine Nachteil des Huffman-Algorithmus besteht darin, dass er prinzipiell nur für einen Text optimal sein kann, bei dem die Wahrscheinlichkeiten der Symbole die inversen Potenzen von 2 sind, wie 14 , 18 , 21 usw., da jedem Zeichen des Textes eine ganze Zahl als Kodierung zugeordnet wird. Die arithmetische Kodierung ordnet dem ganzen Text eine reelle Zahl aus dem Intervall [0, 1) zu und umgeht damit dieses Problem. Funktionsweise: Beginnend mit dem Intervall [0, 1), wird das ausgewählte Intervall in die Subintervalle geteilt, deren Längen jeweils den Wahrscheinlichkeitswerten der Symbole entsprechen. Je nach dem, was für ein Symbol als nächstes im Text kommt, wird sein Subintervall als nächstes ausgewählt. Nach dem das Intervall für das letzte Zeichen bestimmt worden war, wird aus diesem Intervall eine möglichst runde Zahl gewählt, die dann als Kodierung des Textes dient. Anwendungen: Arithmetische Kodierung hat in vielen Fällen die Huffman-Kodierung ersetzt. Eines der Beispiele ist der neue Standard des JPEG-Formats. 2.3 Lempel-Ziv-Welch-Algorithmus Intro: Der Lempel-Ziv-Welch-Algorithmus gehört zu der Entwicklungskette der LZ*-Algorithmen die mit LZ77 anfängt. Diese Algorithmen benutzen im Vergleich zu den oben betrachteten Methoden nicht das statistische Modell, sondern ein Wörterbuch. Funktionsweise: Der Lempel-Ziv-Welch-Algorithmus arbeitet mit einem dynamischen Wörterbuch, das vor dem Beginn mit allen Symbolen des Alphabets initialisiert wird. Bei der Kodierung durchgeht das LZW-Suchfenster die Zeichenkette in der Suche nach einem Wort, was nicht in dem Wörterbuch vorhanden ist. Dabei ist das Suchfenster erst nur ein Zeichen groß und wird um ein Symbol vergrößert, wenn das gelesene Wort bekannt ist. Bei jedem 2 unbekanntem Wort wird ein neuer Wörterbucheintrag angelegt und der Index des letzten bekannten Wortes ausgegeben. Die Suche fängt von neu an, mit dem letzten Zeichen des neuen Wortes als Fenster. Anwendungen: Der LZW ist z.B. für seine Anwendung in GIF und TIFF bekannt. Andere Algorithmen der LZ*-Gruppe werden bei Datei-Formaten, wie HTTP, ZIP, GZIP, PNG, MNG und PDF benutzt. 2.4 Burrows-Wheeler-Transformation Intro: Burrows-Wheeler-Transformation gehört zu den alternativen Kompressionsverfahren, die das Wissen anderer Wissenschaftsbereiche (in diesem Fall: Mathematik) benutzen, um die gestellten Ziele zu erreichen. Funktionsweise: Das Burrows-Wheeler-Verfahren teilt den Eingabestrom in einzelne Blöcke, die getrennt voneinander kodiert werden. Der Inhalt eines Blocks wird so transformiert, dass die sich wiederholenden Zeichenfolgen in einem Bereich des Blocks aufsammeln. Die so optimal vorbereiteten Blöcke werden schnell und effizient mit RLE(Lauflängenkodierung)1 , Move-toFront 2 und anschließend mit Huffman-Algorithmus komprimiert. Zur Transformation werden die Permutationen des Blocks, wie in dem Vortrag gezeigt, verwendet. Anwendungen: Das BWT-Verfahren findet heutzutage bei den Datei-Formaten wie BZIP2, 7z und ZIP seine Anwendung [6]. 3 Textkategorisierung durch Kompression 3.1 Klassifikation Motivation: Da die Klassifikation von Daten heute aufgrund der riesigen Mengen nicht mehr manuell möglich ist, wird auch diese Aufgabe zunehmend von Algorithmen übernommen. 3.2 Textklassifizierung mittels Kompression Kompression zur Klassifikation: Nach Shannon’s Theorem werden für die Kodierung einer Nachricht mindestens so viel Bit gebraucht, wie groß die Entropie dieser Nachricht ist [7]. Gegeben ein Kompressionsverfahren, welches die Daten nahezu optimal komprimieren würde, könnte aus der Länge der komprimierten Daten deren Entropie ermittelt werden. Überdies könnten aus der Entropie der Daten, die Aussagen über deren Inhalt getroffen werden. Um darauf näher einzugehen müsste der Begriff relative Entropie geklärt werden. In dem Artikel ”Language Trees and Zipping”[2] wird diese wie folgt definiert: Angenommen es gibt eine Kodierung für eine Zeichenfolge A, die diese Zeichenfolge optimal komprimiert. Für eine andere Zeichenfolge B ist diese konkrete Kodierung nicht mehr optimal. Falls aber B mit dieser Kodierung komprimiert 1 2 RLE - (english: run-length encoding) ist das einfache Kompressionsverfahren, was das mehrfache kontinuierliche Vorkommen eines Zeichens mit dem Zeichen und der Anzahl seiner Wiederholungen kodiert. Move-to-Front - das Kompressionsverfahren, was die Zeichen der Eingabe mit ihrer Positionen in dem Alphabet kodiert. 3 wird, so ist die Anzahl an Bits pro Zeichen, die für die Kodierung von B ”verschwendet”werden, die relative Entropie von A und B. Damit sind zwei Texte um so ähnlicher, je kleiner ihre relative Entropie ist, weil die optimale Kodierung des einen auch für den anderen nahezu optimal ist. Eine mächtige Klassifizierungsmethode: Prinzip: Die Grundidee des in dem Artikel [2] beschriebenen Verfahren besteht darin, die relative Entropie zwischen den bekannten und einem unbekannten Text zu messen und mittels den Vergleichen aller Werte zu bestimmen, welchem bekannten Text, dieser am ähnlichsten ist. Berechnung der relativen Entropie: Für die Berechnung wird das Kompressionsverfahren LZ77 benutzt, was über folgende Eigenschaft verfügt: dieser Algorithmus komprimiert um so besser, je länger der zu komprimierende Eingabestrom ist. Gebe es z.B. zwei Texte A und B. Um die relative Entropie zu messen, komprimieren zunächst den Text A und dann den Text B mit dem LZ77. Dann nehmen ein kurzes Stück b aus dem Text B, hängen das jeweils an A und B und komprimieren diese Texte. Seien die entsprechende Längen jeweils LA und LB , sowie LA+b und LB+b . Wenn die Länge des Stück b im Vergleich zu A und B jeweils sehr gering ist, so wird dieses Stück mit der jeweils optimalen Kodierung für A oder B komprimiert. Damit ist Lbopt = LB+b − Lb die Länge des optimal kodierten Stück b, während LbA = LA+b − LA die Länge vom Stück b ist, das mit der für A optimalen Kodierung komprimiert wurde. Die relative Entropie zwischen A und B ist damit die Differenz LbA − Lbopt [2]. Zusammenfassung: Durch seine Flexibilität und Unabhängigkeit von den vorliegenden Daten kann das Verfahren in verschiedensten Bereichen die Anwendung finden. Es verlangt keine Vorinformation über die Eingaben, was die Bearbeitung und Klassifizierung absolut neuer Daten ermöglicht. Es können auch die Daten verglichen werden, über die es nicht bekannt ist, welchen Klassen die gehören können. Damit lassen sich die erstaunlichen Ergebnisse erzielen. Literatur [1] BinaryEssence - Datenkompression und Kodierungstechnologien. binaryessence.de/. Accessed: 10-01-2016. http://www. [2] Dario Benedetto, Emanuele Caglioti, and Vittorio Loreto. Language Trees and Zipping. Physical Review Letters. [3] A. Bookstein and S.T. Klein. Is huffman coding dead? Computing, pages 279–296, 1993. [4] M. Burrows and D. Wheeler. A block sorting lossless data compression algorithm. technical report 124. Technical report, Digital Equipment Corporation, 1994. [5] David A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the I.R.E., pages 1098–1101, 1952. [6] David Salomon. A concise introduction to data compression. Springer, 2008. [7] Claude E. Shannon and Warren Weaver. The mathematical theory of communication. The Bell System Technical Journal, 27:379–423, 623–656, 1948. 4
© Copyright 2024 ExpyDoc
