N-Gramm

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

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

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

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. Somit 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 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 eine Mail am Referenzdokument liegt, 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 aufscheinen.

Kommerziell verfügbare Programme, die diese fehlertolerante und äußerst schnelle Methode ausnutzen, sind Rechtschreibprüfungen und Forensik-Werkzeuge (z. B. Computer Associates eTrust Network Forensics – Context).

Google-Korpus

Die Firma Google veröffentlichte im Jahr 2006 sechs DVDs mit englischsprachigen N-Grammen, die bei der Indexierung des Webs entstanden. Diese sind mittlerweile allgemein zugänglich. 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:

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.

Dice-Koeffizient

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\cdot 3}{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:

• Rechtschreibkorrektur (für Korrekturvorschläge)
• Suche nach ähnlichen Schlüsselwörtern (Überwachung, Spracherkennung)
• Grundwortreduktion (Stemming) im Information Retrieval

Statistik

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 und Beutelsbacher.

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

• 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

• Tool zum Zählen von Mono-, Di- und Trigrammen mit Häufigkeitstabellen von N-Grammen aus 20 Sprachen
• Google-NGram-Viewer am Beispiel »Wikipedia, Lexikon, Nachschlagewerk«

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