N-Gram Analyse

N-Gram Analyse

Ein N-Gramm ist eine Folge aus N Zeichen, beispielsweise ein Wortfragment. 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.

Inhaltsverzeichnis

Arten von N-Grammen

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 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 Σ 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 Σ, d. h. 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 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, umso 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 im Jahr 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: 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

D.h. 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

Ü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:

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

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

D.h. d(wirk, work) = \frac{2\cdot3}{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 in folgenden Gebieten angewandt werden:

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[1] und Beutelsbacher.[2]

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.

Einzelnachweise

  1. Helmut Meier: Deutsche Sprachstatistik. Zweite erweiterte und verbesserte Auflage. Olms, Hildesheim 1967, S. 336-339
  2. Albrecht Beutelspacher, Kryptologie, 7. Aufl., Wiesbaden: Vieweg Verlagsgesellschaft, 2005, ISBN 3-8348-0014-7, Seite 230-236; dabei auch: Trigramme.

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • N-Gram-Analyse — Ein N Gramm ist eine Folge aus N Zeichen, beispielsweise ein Wortfragment. N Gramme finden Anwendung in der Kryptologie und Linguistik, speziell auch in der Computerlinguistik, Computerforensik und Quantitativen Linguistik. Einzelne Wörter, ganze …   Deutsch Wikipedia

  • ANALYSE — s. f. T. didactique. Résolution d un tout en ses parties. Faire l analyse d une fleur. L analyse d un mot composé. On le dit plus particulièrement, en Chimie, de L opération qui consiste à décomposer les corps et à séparer leurs éléments. Analyse …   Dictionnaire de l'Academie Francaise, 7eme edition (1835)

  • gram — [ gram ] n. m. inv. • 1897; de coloration de Gram, nom d un bactériologiste danois ♦ Biol. Méthode de coloration des microbes avec une solution à base d iode et d iodure de potassium. ⊗ HOM. Gramme. ● Gram nom masculin invariable Coloration de… …   Encyclopédie Universelle

  • analyse — [ analiz ] n. f. • fin XVIe; gr. analusis « décomposition, résolution » I ♦ (Idée de « décomposition »). 1 ♦ Action de décomposer un tout en ses éléments constituants. Faire l analyse d un roman, d une pièce de théâtre. ⇒ compte rendu, 2.… …   Encyclopédie Universelle

  • Analyse En Composantes Indépendantes — Pour les articles homonymes, voir ACI. L analyse en composantes indépendantes est une méthode d analyse des données (voir aussi Exploration de données) qui relève des statistiques, des réseaux de neurones et du traitement du signal. Elle est… …   Wikipédia en Français

  • Analyse en composantes independantes — Analyse en composantes indépendantes Pour les articles homonymes, voir ACI. L analyse en composantes indépendantes est une méthode d analyse des données (voir aussi Exploration de données) qui relève des statistiques, des réseaux de neurones et… …   Wikipédia en Français

  • Analyse en composantes indépendantes — Pour les articles homonymes, voir ACI. L analyse en composantes indépendantes est une méthode d analyse des données (voir aussi Exploration de données) qui relève des statistiques, des réseaux de neurones et du traitement du signal. Elle est… …   Wikipédia en Français

  • analyse — v.tr. (US analyze) 1 examine in detail the constitution or structure of. 2 Chem. ascertain the constituents of (a sample of a mixture or compound). 3 find or show the essence or structure of (a book, music, etc.). 4 Gram. resolve (a sentence)… …   Useful english dictionary

  • Analyse médicale — Biologie médicale La Biologie médicale (France), Biologie clinique (Belgique, Pays Bas), Médecine de Laboratoire (Allemagne et Suisse), Pathologie Clinique (Pays anglophones) ou encore Biopathologie (Grèce) est une spécialité de la médecine qui… …   Wikipédia en Français

  • Laugh-O-Gram Films — Laugh O Gram Laugh O Gram Films Inc Création 23 mai 1922 Disparition …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”