N-Gram-Analyse

Die N-Gram Analyse ist ein Verfahren, um mathematische Gesetze, die auf Vektoren angewandt werden können auch auf andere Objekte anzuwenden. Das Verfahren wurde am 23. Mai 1995 vom amerikanischen Geheimdienst NSA patentiert und ständig weiterentwickelt.

Mit der N-Gram Analyse können Kontexte gesucht werden, beispielsweise die Wortgruppe "Atombombe in Nordkorea" in einer großen Anzahl von E-Mails. Dabei ist die verwendete Sprache nicht von Bedeutung: N-Gram Analyse funktioniert in jeder Sprache und jedem Alphabet.

Definition

Sei A ein Alphabet, dann ist |A| die Mächtigkeit des Alphabets. n sein eine positive Zahl. Ein N-Gram ist dann ein Wort der Länge n.

Beispiel

Eine zu durchsuchende Zeichenkette lautet: w={"Welcome to come"}.

n = 2 (sog. Bigramm)

Die "Frequenz", also die Zeichenketten die durch die Analyse entstehen lauten dann:

_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.