EinN-Gramm, manchmal auchQ-Gramm genannt,[1] ist das Ergebnis der Zerlegung eines Textes in Fragmente.
Der Text wird dabei zerlegt, und jeweils aufeinanderfolgende Fragmente werden alsN-Gramm zusammengefasst. Die Fragmente können Buchstaben,Phoneme,Wörter und Ähnliches sein. N-Gramme finden Anwendung in derKryptologie undKorpuslinguistik, speziell auch in derComputerlinguistik,Quantitativen Linguistik undComputerforensik. Einzelne Wörter, ganzeSätze oder kompletteTexte werden hierbei zur Analyse oder statistischen Auswertung in N-Gramme zerlegt[2] und inDatensätzen zusammengefasst.
Drei Datensätze von N-Grammen ausGoogle Books mit den Stichtagen Juli 2009, Juli 2012 und Februar 2020 wurden mit einer Weboberfläche und grafischer Auswertung in Form vonDiagrammen versehen und unter dem NamenGoogle Books Ngram Viewer ins Netz gestellt.
Wichtige N-Gramme sind dasMonogramm, dasBigramm (manchmal auch als Digramm bezeichnet) und dasTrigramm. Das Monogramm besteht auseinem Fragment, beispielsweise nur aus einem einzelnen Buchstaben, das Bigramm auszwei und das Trigramm ausdrei Fragmenten. Allgemein kann man auch vonMultigrammen sprechen, wenn es sich um eine Gruppe von„vielen“ Fragmenten handelt.
DiePräfixe wissenschaftlicher Bezeichnungen werden häufig unter Zuhilfenahmegriechischer Zahlwörter gebildet. Beispiele sindmono 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 undmulti sind Vorsilben lateinischen Ursprungs und stehen für „zwei“ beziehungsweise „viele“.
Die folgende Tabelle gibt eine Übersicht über die Bezeichnungen der N-Gramme, sortiert nach der Anzahl der Zeichen und versehen mit jeweils einem Beispiel, das Buchstaben deslateinischen Alphabets verwendet:
| N-Gramm-Name | N | Beispiel |
|---|---|---|
| Monogramm | 1 | A |
| Bigramm, Digramm | 2 | AB |
| Trigramm | 3 | UNO |
| Tetragramm | 4 | HAUS |
| Pentagramm | 5 | HEUTE |
| Hexagramm | 6 | SCHIRM |
| Heptagramm | 7 | TELEFON |
| Oktogramm | 8 | COMPUTER |
| … | … | … |
| Multigramm | 17 | BEOBACHTUNGSLISTE |
Sei ein endlichesAlphabet und sei eine positive ganze Zahl. Dann ist ein-Gramm ein Wort der Länge über dem Alphabet, das heißt.
DieN-Gramm-Analyse wird verwendet, um die Frage zu beantworten, wiewahrscheinlich auf eine bestimmte Buchstaben- oder Wortfolge ein bestimmter Buchstabe oder ein bestimmtes Wort folgen wird. Die bedingten Wahrscheinlichkeiten für den nächsten Buchstaben der Folge „for ex…“ betragen für eine bestimmte Stichprobe aus dem Englischen in absteigenderRangreihenfolge etwa: 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 ihreStatistik: Die N-Gramm-Analyse funktioniert in jeder Sprache und jedem Alphabet. Daher hat sich die Analyse in den Feldern derSprachtechnologie bewährt: Zahlreiche Ansätze dermaschinellen Ü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, beispielsweiseE-Mails, auf ein bestimmtes Themengebiet hin untersucht werden sollen. Durch die Ähnlichkeit mit einem Referenzdokument, etwa einem technischen Bericht überAtombomben oderPolonium, lassen sichCluster 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, sindRechtschreibprüfungen undForensik-Werkzeuge. In der ProgrammierspracheJava verfügt dieBibliothekApache OpenNLP über Werkzeuge zur N-Gramm-Analyse,[3] inPython stehtNLTK zur Verfügung.[4]
Google veröffentlichte im Jahr 2006 sechs DVDs[5] mit englischsprachigen N-Grammen von einem 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:[6]
3-Gramme:
4-Gramme:
Das heißt. Der Unterstrich steht für die Wortgrenze.Die Länge des Vektors ist dabei durch nach oben beschränkt, wobei die Länge von und derBinomialkoeffizient ist.
Ein Datensatz ausGoogle Books mit Stichtag Juli 2009 wurde mit einer Weboberfläche und grafischer Auswertung in Form vonDiagrammen versehen und unter dem NamenGoogle Books Ngram Viewer ins Netz gestellt.[7] Standardmäßig zeigt sie die normalisierte Häufigkeit relativ zur Anzahl der bis zu diesem Jahr vorhandenen Bücher für bis zu 5-Gramme. Mit Operatoren lassen sich mehrere Begriffe zu einem Graphen 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“[8]), 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 unterCreative Commons Attribution Lizenz. Neben einer Auswertungsmöglichkeit für Englisch allgemein gibt es spezielle Abfragen fürAmerican English undBritish English (differenziert anhand der Veröffentlichungsorte), sowie fürEnglish Fiction (anhand der Einstufung der Bibliotheken) undEnglish 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. ZurTokenisierung wurden einfach die Leerzeichen herangezogen. Die N-Gramm-Bildung geschah über Satzgrenzen hinweg, aber nicht über Seitengrenzen. Es wurden nur Wörter aufgenommen, die mindestens 40-mal im Korpus 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 das Korpus auf einer größeren Anzahl von Büchern, verbesserterOCR-Technik und verbessertenMetadaten. Die Tokenisierung geschah hier nach einem Set handgeschriebener Regeln, außer für Chinesisch, wo eine statistische Methode zurSegmentierung 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 (gleich geschriebene) Substantive und Verben unterscheiden lassen, wobei dies in moderner Sprache besser funktioniert.[8][9]
Mit Stichtag Februar 2020 wurde nunmehr ein drittes Korpus mit dem Nennjahr 2019 ins Netz gestellt, dessen Features denen der Version 2012 entsprechen.
Der Dice-Koeffizient ist eins von mehrerenÄhnlichkeitsmaßen für Terme. Er ermittelt den Anteil der N-Gramme, die in zwei Termen und vorhanden sind. Die Formel ist
wobei die Menge der N-Gramme des Terms ist. d liegt dabei immer zwischen 0 und 1.
Bei Verwendung von Trigrammen sieht die Zerlegung folgendermaßen aus:
Das heißt d(wirk, work) =.Der Dice-Koeffizient beträgt also 0,5 (50 %).
Aufgrund der weitgehenden Sprachneutralität kann dieser Algorithmus auf folgenden Gebieten angewandt werden:
AlsN-Gramm-Statistik bezeichnet man eineStatistik ü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 derKryptoanalyse und in derLinguistik, dort vor allem beiSpracherkennungssystemen. Dabei prüft das System während der Erkennung die verschiedenen Hypothesen zusammen mit dem Kontext und kann dadurchHomophone (gleich klingende Wörter) 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[10] undBeutelspacher.[11]
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 % |
