N-Gramm
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-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 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 [http://www.ldc.upenn.edu/Catalog/CatalogEntry.jsp?catalogId=LDC2006T13 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-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
• Zahlwörter]
*Trigrammstatistik
*Markowkette
