Das Kefk Network Wiki befindet sich im Testbetrieb.

Aus Kefk.

Ein N-Gramm ist eine Menge aus N Zeichen, beispielsweise ein Wortfragment. 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. Darüber hinaus werden die Begriffe Tetragramm für vier Zeichen, Pentagramm für fünf Zeichen, Hexagramm für sechs Zeichen, Heptagramm für sieben Zeichen und Oktogramm für acht Zeichen verwendet. 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 von griechisch monos für „allein“ oder „einzig“, tri für „drei““, tetra für „vier““, penta von griechisch pente 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 N der Zeichen 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       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  

N-Gramme finden Anwendung in der Kryptologie und Linguistik, speziell auch in der Computerlinguistik und Computerforensik. Einzelne Wörter, ganze Sätze oder komplette Texte werden hierbei zur Analyse oder statistischen Auswertung in N-Gramme zerlegt.

Formale Definition

Sei A ein Alphabet, dann ist |A| die Mächtigkeit des Alphabets. n sei eine positive Zahl. Ein N-Gramm ist dann ein Element der Länge n aus der Potenzmenge von A.

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 gewonnen aus dieser Methode auf.

Besondere Bedeutung bekommt die Analyse, wenn große Datenmengen, z.B. E-Mails auf ein bestimmtes Themengebiet hin untersucht werden sollen. Durch die Ähnlichkeit mit einem Referenzdokument, z.B. einem technischen Bericht über Atombomben, Polonium, etc., lassen sich Cluster bilden. Je näher eine Mail am Referenzdokument liegt, um so wahrscheinlicher ist, dass sich der Inhalt um sein Thema dreht und - in unserem Beispiel evtl. Terrorismus-relevant sein könnte, selbst wenn die Schlüsselwörter nicht selbst auftauchen.

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 2006 6 DVDs gefüllt mit englischsprachigen N-Grammen die bei der Indexierung des Web entstanden. Diese sind jetzt für alle Welt zugänglich. Hier ein Beispiel aus dem Google-Korpus:

3-grams

ceramics collectables collectibles (55)

ceramics collectables fine (130)

ceramics collected by (52)

ceramics collectible pottery (50)

ceramics collectibles cooking (45)

4-grams

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: w={"Welcome to come"}.

n = 2 (sog. Bigramm)

Die Häufigkeit des Vorkommens der einzelnen Bigramme wird bestimmt.

Somit lautet diese "Frequenz" für die Zeichenkette w:

_W:1

We:1

el:1

lc:1

co:2

om:2

me:2

e_:1

_t:1

to:1

o_:1

_c:1

Der Vektor lautet: (1,1,1,1,2,2,2,1,1,1,1,1) Die Länge des Vektors steigt exponentiell nach |A|^n.

Dice-Koeffizient

Über N-Gramme lassen sich wie beschrieben Wort-Ähnlichkeiten berechnen. Ein Algorithmus dafür ist der Dice-Algorithmus. Der Dice-Koeffizient d zweier Terme a und b ist dabei definiert durch:

wobei T(x) eine N-Gram Zerlegung des Terms x ist. d liegt dabei immer zwischen 0 und 1.

Siehe auch: Distanzfunktion

Beispiel

• Term a = "wirk"
• Term b = "work"

Wenn wir Tri-Gramme benutzen, so sieht die Zerlegung folgendermaßen aus:

• T(a) = {w, wi, wir, irk, rk, k}
• T(b) = {w, wo, wor, ork, rk, k}

D.h. d(wirk, work) = . Der Dice-Koeffizient (man kann auch sagen die Ähnlichkeit) beträgt also 0.5 (50%).

Anwendungsgebiete

Aufgrund der weitgehenden Sprachneutralität, kann dieser Algorithmus in folgenden Gebieten angewandt werden:

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

Verschwörungstheorie

Durch die Anwendung der N-Gramm-Analyse in der Kryptoanalyse stand bis vor kurzem auch auf dieser Seite, sie sei eine "am 23.05.1995 patentierte Entwicklung" der NSA. Laut der Einführung in Speech- and Language-Processing von Daniel Jurafsky und James H. Martin stammen die zugrundeliegenden mathematischen Gedanken von Markov, der sie 1913 entwickelte. Sein Verfahren ist heute als Markov-Kette bekannt.

Siehe auch

• Griechische Zahlwörter
• Trigrammstatistik
• Markowkette

Dieses Dokument entstammt in seiner ersten oder einer späteren Version der deutschsprachigen Wikipedia. Es ist dort zu finden unter dem Stichwort N-Gramm, die Liste der bisherigen Autoren befindet sich in der Versionsliste; die Originalfassung kann dort auch bearbeitet werden. Alle Texte der Wikipedia und ihre Derivate stehen unter der GNU-Lizenz für freie Dokumentation.