N-Gramm

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

N-Gramme sind das Ergebnis der Zerlegung eines Textes in Fragmente. Der Text wird dabei zerlegt und jeweils N Fragmente als N-Gramm zusammengefasst. Die Fragmente können Buchstaben, Phoneme, Wörter und Ähnliches sein. N-Gramme finden Anwendung in der Kryptologie und Linguistik, speziell auch in der Computerlinguistik, Computerforensik und Quantitativen Linguistik. Einzelne Wörter, ganze Sätze oder komplette Texte werden hierbei zur Analyse oder statistischen Auswertung in N-Gramme zerlegt.

Arten von N-Grammen[Bearbeiten]

Bigramm-Häufigkeitsgebirge: Verteilung der Bigramme in einem deutschen Text.
Trigramm-Häufigkeitsgebirge: Verteilung der Trigramme in einem deutschen Text. Die Tripel ER_ und EN_ sind am häufigsten („_“ steht für das Leerzeichen).

Wichtige N-Gramme sind das Monogramm, das Bigramm (manchmal auch als Digramm bezeichnet) und das Trigramm. Das Monogramm besteht aus einem Zeichen, beispielsweise nur aus einem einzelnen Buchstaben, das Bigramm aus zwei und das Trigramm aus drei Zeichen. Allgemein kann man auch von Multigrammen sprechen, wenn es sich um eine Gruppe von „vielen“ Zeichen handelt.

Die Vorsilben der Bezeichnungen werden in der Regel unter Zuhilfenahme der griechischen Zahlwörter gebildet. Beispiele sind mono für „allein“ oder „einzig“, tri für „drei“, tetra für „vier“, penta für „fünf“, hexa für „sechs“, hepta für „sieben“, okto für „acht“ und so weiter. Bi und multi sind Vorsilben lateinischen Ursprungs und stehen für „zwei“ beziehungsweise „viele“.

Die folgende Tabelle gibt sortiert nach der Anzahl der Zeichen N zusammen mit einem Beispiel, bei denen als Zeichen Alphabet-Buchstaben genommen wurden, eine Übersicht über die Bezeichnung der N-Gramme:

N-Gramm-Name N Beispiel
Monogramm/Unigramm 1 A
Bigramm 2 AB
Trigramm 3 UNO
Tetragramm 4 HAUS
Pentagramm 5 HEUTE
Hexagramm 6 SCHIRM
Heptagramm 7 TELEFON
Oktogramm 8 COMPUTER
Multigramm N BEOBACHTUNGSLISTE

Formale Definition[Bearbeiten]

Sei \Sigma ein endliches Alphabet und sei n eine positive ganze Zahl. Dann ist ein n-Gramm ein Wort w der Länge n über dem Alphabet \Sigma, das heißt w=(w_1,\ldots,w_n)\in \Sigma^n.

Analyse[Bearbeiten]

Die N-Gramm-Analyse wird verwendet, um die Frage zu beantworten, wie wahrscheinlich auf eine bestimmte Buchstaben- oder Wortreihenfolge ein bestimmter Buchstabe oder ein bestimmtes Wort folgen wird, beispielsweise die englischen Zeichen „for ex…“. Die bedingten Wahrscheinlichkeiten für die Buchstaben des Alphabets in der englischen Sprache sind in absteigender Rangreihenfolge: a = 0.4, b = 0.00001, c = 0, … mit einer Gesamtsumme von 1. Auf der Grundlage der N-Gramm-Häufigkeiten erscheint also eine Fortsetzung des Fragmentes mit „a“ → „for exa(mple)“ deutlich wahrscheinlicher als die Alternativen.

Die verwendete Sprache ist für die Analyse nicht von Bedeutung, wohl aber ihre Statistik: Die N-Gramm-Analyse funktioniert in jeder Sprache und jedem Alphabet. Daher hat sich die Analyse in den Feldern der Sprachtechnologie bewährt: Zahlreiche Ansätze der maschinellen Übersetzung bauen auf den Daten auf, die mit dieser Methode gewonnen wurden.

Besondere Bedeutung kommt der N-Gramm-Analyse dann zu, wenn große Datenmengen, beispielsweise E-Mails, auf ein bestimmtes Themengebiet hin untersucht werden sollen. Durch die Ähnlichkeit mit einem Referenzdokument, etwa einem technischen Bericht über Atombomben oder Polonium, lassen sich Cluster bilden: Je näher die Worthäufigkeiten in einer Mail an denen im Referenzdokument liegen, umso wahrscheinlicher ist, dass sich der Inhalt um dessen Thema dreht und unter bestimmten Umständen – in diesem Beispiel – eventuell Terrorismus-relevant sein könnte, selbst wenn Schlüsselwörter, die eindeutig auf Terrorismus hinweisen, selbst nicht auftauchen.

Kommerziell verfügbare Programme, die diese fehlertolerante und äußerst schnelle Methode ausnutzen, sind Rechtschreibprüfungen und Forensik-Werkzeuge.

Google-Korpus[Bearbeiten]

Die Firma Google veröffentlichte im Jahr 2006 sechs DVDs[1] mit englischsprachigen N-Grammen von ein bis fünf Wörtern, die bei der Indexierung des Webs entstanden. Nachfolgend einige Beispiele aus dem Google-Korpus für 3-Gramme und 4-Gramme auf Wortebene (d.h. n entspricht der Anzahl der Wörter) und die Häufigkeiten, mit denen diese auftreten:[2]

3-Gramme:

  • ceramics collectables collectibles (55)
  • ceramics collectables fine (130)
  • ceramics collected by (52)
  • ceramics collectible pottery (50)
  • ceramics collectibles cooking (45)

4-Gramme:

  • serve as the incoming (92)
  • serve as the incubator (99)
  • serve as the independent (794)
  • serve as the index (223)
  • serve as the indication (72)
  • serve as the indicator (120)
Beispiel
Eine zu durchsuchende Zeichenkette lautet
s = {„Welcome to come“}.
n = 2 (sog. Bigramm)
Die Häufigkeit des Vorkommens der einzelnen Bigramme wird bestimmt.
Somit lautet der „Frequenzvektor“ f für die Zeichenkette s:
_W:1
We:1
el:1
lc:1
co:2
om:2
me:2
e_:1
_t:1
to:1
o_:1
_c:1

Das heißt f=(1,1,1,1,2,2,2,1,1,1,1,1). Die Länge des Vektors ist dabei durch {|s|+2(n-1)\choose n} nach oben beschränkt, wobei |s| die Länge von s und {a\choose b} der Binomialkoeffizient ist.

Ein Datenset aus Google Bücher mit Stichtag Juli 2009 wurde mit einer Weboberfläche und grafischer Auswertung[3] versehen. Standardmäßig zeigt sie die normalisierte Häufigkeit zur Anzahl der für dieses Jahr vorhandenen Bücher für bis zu 5-Gramme. Mit Operatoren lassen sich mehrere Begriffe zu einem Graph zusammenfassen (+), ein Multiplikator für sehr unterschiedlich vorkommende Begriffe einbauen (*), das Verhältnis zwischen zwei Begriffen darstellen (-, /) oder verschiedene Korpora vergleichen (:). Die Grafiken können frei verwendet werden („freely used for any purpose“[4]), wobei die Angabe der Quelle und ein Link erwünscht sind. Die Grunddaten sind für eigene Auswertungen in einzelne Pakete gesplittet downloadbar und stehen unter Creative Commons Attribution Lizenz. Neben einer Auswertungsmöglichkeit für Englisch allgemein gibt es spezielle Abfragen für American English und British English (differenziert anhand der Veröffentlichungsorte), sowie für English Fiction (anhand der Einstufung der Bibliotheken) und English One Million. Bei letzterem wurden proportional zur Anzahl veröffentlichter und gescannter Bücher von 1500 bis 2008 bis zu 6000 Bücher pro Jahr zufällig ausgewählt. Zusätzlich gibt es auch Korpora für Deutsch, vereinfachtes Chinesisch, Französisch, Hebräisch, Russisch und Spanisch. Zur Tokenisierung wurden einfach die Leerzeichen herangezogen. Die N-Gramm-Bildung geschah über Satzgrenzen hinweg, aber nicht über Seitengrenzen. Es wurden nur Wörter aufgenommen, die in mindestens 40 Büchern vorkommen.

Ein neues Korpus mit Stichtag Juli 2012 wurde Ende des Jahres zugänglich gemacht. Als neue Sprache kam Italienisch hinzu, English One Million wurde nicht wieder gebildet. Grundlegend basiert er auf einer größeren Anzahl von Büchern, verbesserter OCR-Technik und verbesserten Metadaten. Die Tokenisierung geschah hier nach einem Set handgeschriebener Regeln, außer für Chinesisch, wo eine statistische Methode zur Segmentierung genutzt wurde. Die N-Gramm-Bildung endet nun bei Satzgrenzen, geht aber dabei nun über Seitengrenzen hinweg. Mit den nun beachteten Satzgrenzen sind neue Funktionen für das 2012er-Korpus eingeführt worden, die bei 1-, 2- und 3-Grammen auch mit hoher Wahrscheinlichkeit die Stellung im Satz auswerten lassen und so beispielsweise auch im Englischen homographe Substantive und Verben unterscheiden lassen, wobei dies in moderner Sprache besser funktioniert.[4][5]

Dice-Koeffizient[Bearbeiten]

Der Dice-Koeffizient gibt an, wie ähnlich zwei Terme sind. Er ermittelt dazu den Anteil der N-Gramme, die in beiden Termen vorhanden sind. Die Formel für zwei Terme a und b ist

d(a,b) = \frac{2|T(a) \cap T(b)|}{|T(a)|+|T(b)|}

wobei T(x) die Menge der N-Gramme des Terms x ist. d liegt dabei immer zwischen 0 und 1.

Siehe auch: Distanzfunktion
Beispiel
  • Term a = "wirk"
  • Term b = "work"
Bei Verwendung von Trigrammen, sieht die Zerlegung folgendermaßen aus:
  • T(a) = {§§w, §wi, wir, irk, rk§, k§§}
  • T(b) = {§§w, §wo, wor, ork, rk§, k§§}
  • T(a) \cap T(b) = {§§w, k§§, rk§}
Das heißt d(wirk, work) = \frac{2\cdot3}{6+6} = \frac{1}{2}.
Der Dice-Koeffizient (man kann auch sagen die Ähnlichkeit) beträgt also 0,5 (50 %).
Anwendungsgebiete
Aufgrund der weitgehenden Sprachneutralität kann dieser Algorithmus auf folgenden Gebieten angewandt werden:

Statistik[Bearbeiten]

Als N-Gramm-Statistik bezeichnet man eine Statistik über die Häufigkeit von N-Grammen, manchmal auch von Wortkombinationen aus N Wörtern. Spezialfälle sind die Bigrammstatistik und die Trigrammstatistik. Anwendungen finden N-Gramm-Statistiken in der Kryptoanalyse und in der Linguistik, dort vor allem bei Spracherkennungssystemen. Dabei prüft das System während der Erkennung die verschiedenen Hypothesen zusammen mit dem Kontext und kann dadurch Homophone unterscheiden. In der Quantitativen Linguistik interessiert unter anderem die Rangordnung der N-Gramme nach Häufigkeit sowie die Frage, welchen Gesetzen sie folgt. Eine Statistik von Digrammen (und Trigrammen) im Deutschen, Englischen und Spanischen findet man bei Meier[6] und Beutelsbacher.[7]

Für aussagefähige Statistiken sollten ausreichend große Textbasen von mehreren Millionen Buchstaben oder Wörtern benutzt werden. Als Beispiel ergibt die statistische Auswertung einer deutschen Textbasis von etwa acht Millionen Buchstaben „ICH“ als das häufigste Trigramm mit einer relativen Häufigkeit von 1,15 Prozent. Die folgende Tabelle gibt eine Übersicht über die zehn (in dieser Textbasis) als häufigste ermittelten Trigramme:

Trigramm Häufigkeit
ICH 1,15 %
EIN 1,08 %
UND 1,05 %
DER 0,97 %
NDE 0,83 %
SCH 0,65 %
DIE 0,64 %
DEN 0,62 %
END 0,60 %
CHT 0,60 %

Literatur[Bearbeiten]

  • Wolfgang Schönpflug: N-Gramm-Häufigkeiten in der deutschen Sprache. I. Monogramme und Digramme. In: Zeitschrift für experimentelle und angewandte Psychologie XVI, 1969, S. 157–-183.

Weblinks[Bearbeiten]

 Wiktionary: N-Gramm – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

Einzelnachweise[Bearbeiten]

  1. Web 1T 5-gram Version 1
  2. Alex Franz and Thorsten Brants: All Our N-gram are Belong to You. In: Google Research Blog. 2006. Abgerufen am 16. Dezember 2011.
  3. Google books Ngram Viewer
  4. a b Google books Ngramm Viewer - Info
  5. Google books Ngramm Viewer - Datasets
  6. Helmut Meier: Deutsche Sprachstatistik. Zweite erweiterte und verbesserte Auflage. Olms, Hildesheim 1967, S. 336–339
  7. Albrecht Beutelspacher: Kryptologie. 7. Aufl., Vieweg, Wiesbaden 2005, ISBN 3-8348-0014-7, Seite 230–236; dabei auch: Trigramme.