Gemeinsamkeit im Konzentrat

News: Gemeinsamkeit im Konzentrat

Die meisten Computernutzer werden das hilfreiche ZIP-Programm kennen, mit dem sich umfangreiche Datenbestände zu kleinen Dateien komprimieren lassen. Nun fanden Wissenschaftler heraus, dass die Software wesentlich mehr kann, als nur Datenberge zu schrumpfen: Sie eignet sich auch dazu, den Informationsgehalt von Texten zu bestimmen und so deren Autorenschaft, die Sprache und sogar einen Sprachstammbaum abzuleiten.

Thorsten Krome

"Uns ist in alten maeren wunders vil geseit
von helden lobebaeren, von grôzer arebeit,
von vreude und hôchgezîten, von weinen und von klagen,
von küener recken strîten muget ir nu wunder hoeren sagen."

So beginnt die bedeutendste mittelhochdeutsche Heldensage – das Nibelungenlied. Die 39 Abschnitte der Dichtung, die "Aventiuren", erzählen uns die Geschichte von Siegfried und Kriemhild und ihrer späterer Rache an den Nibelungen. Der Schöpfer dieses berühmten Werks ist jedoch unbekannt. Zwar gibt es durchaus einige Vermutungen, und so manche Ortschaft preist ihre einstigen Schreiberlinge als mutmaßliche Urheber – doch Sicherheit gibt es nicht. In Zukunft ließe sich ein Verdacht unter Umständen jedoch sehr schnell überprüfen, dazu bedürfte es einzig und allein eines Computers, einer herkömmlichen Komprimierungssoftware, die mit ZIP-Archiven umgehen kann, und einiger Textpassagen des zu überprüfenden Dokuments sowie einige der in Frage kommenden Autoren.

Denn Dariao Benedetto, Emanuele Caglioti und Vittorio Loreto von der Università degli Studi di Roma "La Sapienza" fanden heraus, dass sich das hilfreiche Programm bestens dazu eignet, den Informationsgehalt von Texten zu vergleichen. Dabei entspricht eine Zunahme an Information einer Abnahme der Entropie des Systems – hier eines Textes. Und genau diese Entropie liefert der Lempel-Ziv-Algorithmus (LZ77), welcher der ZIP-Software zugrunde liegt, auf denkbar einfach Weise: Denn die Länge der Zeichenfolge nach dem Komprimieren geteilt durch die ursprüngliche Länge strebt im Grenzwert für unendlich lange Textpassagen gegen den Wert ihrer Entropie.

Doch wie lässt sich das ausnutzen, um Dokumente zu vergleichen? Dazu komprimierten die Forscher zunächst eine bekannte Zeichenfolge und notierten sich deren Länge. Danach fügten sie der ursprünglichen Abfolge ein kurzes Fragment einer zu prüfenden Sequenz an und ließen auch dieses Datenpaket mit dem Algorithmus schrumpfen. Die Längendifferenz zwischen den beiden komprimierten Zeichenabfolgen liefert nun ein Maß dafür, wie nahe sich die beiden ursprünglichen Zeichenreihen stehen. Dabei lässt sich das Verfahren nicht nur auf Zeichen und Texte, sondern auf nahezu beliebige Datensätze anwenden.

Die Forscher prüften ihr Konzept jedoch an Texten. In einem ersten Test sollte damit die Sprache von Schriftstücken bestimmt werden. Dazu komprimierten sie jeweils eine lange Passage verschiedensprachiger Texte mit einem kurzen zu testenden Abschnitt. Ihre Annahme war dabei, dass die komprimierte Datei gerade dann am kleinsten ausfällt, wenn das kürzere Textstück in derselben Sprache verfasst ist wie der größere Teil. Benedetto, Caglioti und Loreto verwendeten für ihren Test zehn offizielle Sprachen der EU in allen möglichen Kombinationen. Das Ergebnis war erstaunlich: Tatsächlich lieferten die Textkombinationen aus gleichen Sprachen jeweils die kleinsten Dateien.

Anschaulich lässt sich das verstehen, wenn man sich das Prinzip des LZ77-Algorithmus vergegenwärtigt: Dieser legt nämlich eine Art Wörterbuch für bereits verwendete Sequenzen an. Wenn dann im weiteren Verlauf diese Sequenz wiederholt auftritt, so wird nur noch auf die entsprechende "Hausnummer" im Wörterbuch verwiesen. Ein Text, welcher Sprache auch immer, beinhaltet stets wiederkehrende Zeichenfolgen – man denke nur an sich wiederholende Wörter, aber auch bestimmte kürzere Abfolgen sind typisch, wie im Deutschen beispielsweise "sch", "tz" oder ähnliches. Ändert sich nun aber plötzlich beim Komprimieren die Sprache eines Dokuments, dann wird der Algorithmus zunächst nicht mehr so viele Treffer im Wörterbuch finden und produziert entsprechend größere Dateien. Das fällt jedoch nur auf, wenn der angehängte fremdsprachliche Abschnitt kurz genug ist. Denn bei längeren Anhängseln hat der Algorithmus wieder genug Zeit zu lernen, und Abweichungen in der Dateigröße fallen nicht mehr so stark ins Gewicht. Typischerweise belegten die umfangreichen Dateien zwischen 32 und 64 Kilobyte und die kleinen 1 bis 15 Kilobyte.

Die Wissenschaftler prüften aber nicht nur, inwieweit sich die Sprache wiederkennen lässt, sondern auch, ob sich so der Autor eines Stücks offenbart. Das Prinzip war dasselbe wie beim Sprachentest: Große Passagen mit bekanntem Autor wurden mit Testfragmenten komprimiert. Und auch hier war die Treffsicherheit verblüffend: In 93 Prozent der Fälle wies die minimale Dateigröße auf denselben Schöpfer hin.

In einem letzten Experiment versuchten die Forscher das Verfahren zu nutzen, um Sprachen zu klassifizieren. Dazu verwendeten sie die "Allgemeine Erklärung der Menschenrechte", da deren Formulierung in sehr vielen Sprachen verfügbar ist. Dabei lagen alle Texte im so genannten Unicode vor, um auch jegliche Schriftzeichen erfassen zu können. Schließlich bedienten sie sich einer Methode, die normalerweise zur Stammbaumanalyse biologischer Sequenzen dient, im Prinzip wurden dazu jedoch wieder Textpassagen in gewohnter Manier anhand ihrer ZIP-Archive verglichen. Heraus kam ein Stammbaum für 50 Sprachen, der erstaunlich genau dem von Linguisten entwickelten System ähnelt: So bildeten sich beispielsweise auch hier die großen zusammenhängenden Sprachklassen heraus.

Wenngleich Benedetto, Caglioti und Loreto ihr Verfahren in erster Linie an Texten verschiedener Sprachen testeten, so taugt es doch auch für unzählige andere Bereiche, bei denen Zeichenabfolgen untersucht werden: DNA- und Protein-Squenzierungen, Aktienmarktanalysen und medizinische Kontrollen sind dabei nur einige wenige Beispiele. Und wer weiß, vielleicht lässt sich mit dieser Methode auch irgendwann der Dichter des Nibelungenlieds finden.