N-Gramm

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:

• 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

${\displaystyle s}$ = {„Welcome to come“}.

${\displaystyle n=2}$ (sog. Bigramm)

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

Somit lautet der „Frequenzvektor“ ${\displaystyle f}$ für die Zeichenkette ${\displaystyle s}$:

_W:1

We:1

el:1

lc:1

co:2

om:2

me:2

e_:2

_t:1

to:1

o_:1

_c:1

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

Ein Datensatz aus Google Books mit Stichtag Juli 2009 wurde mit einer Weboberfläche und grafischer Auswertung in Form von Diagrammen versehen und unter dem Namen Google 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 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 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, 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 (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 ${\displaystyle a}$ und ${\displaystyle b}$ vorhanden sind. Die Formel ist

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

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

• 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) ${\displaystyle \cap }$ T(b) = {§§w, k§§, rk§}

Das heißt d(wirk, work) = ${\displaystyle {\tfrac {2\cdot 3}{6+6}}={\tfrac {1}{2}}}$. Der Dice-Koeffizient beträgt also 0,5 (50 %).

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