W i l l k o m m e n   b e i   [ www.mauspfeil.com ]
 
 



 

Wörterbuch der Bedeutung
<<Zurück
Bitte wählen Sie einen Buchstaben:
A, Ä | B | C | D | E | F | G | H | I | J | K | L | M | N | O, Ö | P | Q | R | S | T | U, Ü | V | W | X | Y | Z | 0-9

Suchen:

(Groß-/Kleinschreibung wird nicht unterschieden)

Google


N-Gram-Analyse

*** Shopping-Tipp: N-Gram-Analyse

Die '''N-Gram 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 Wahrscheinlichkeiten für die Buchstaben des Alphabets sind demzufolge: a = 0.4, b = 0.00001, c = 0, ....; Die Gesamtsumme aller Wahrscheinlichkeiten beträgt 1. 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. Außerdem aber hat sich die N-Gram-Analyse in den Feldern der Sprachtechnologie bewährt: Zahlreiche Ansätze der Maschinelle Übersetzung bauen auf den Daten gewonnen aus der N-Gram Analyse 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, lassen sich Cluster bilden. Je näher eine Mail am Referenzdokument liegt, um so wahrscheinlicher ist, dass sich der Inhalt um sein Thema dreht. Kommerziell verfügbare Programme, die diese fehlertolerante und äußerst schnelle Methode ausnutzen, sind Rechtschreibprüfungen (StarOffice) und Forensik-Werkzeuge (Computer Associates eTrust Network Forensics - Context).

Google-Korpus
Die Firma [http://www.google.com 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)

Definition
Sei A ein Alphabet, dann ist |A| die Mächtigkeit des Alphabets. n sei 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 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-Ä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.

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} 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: * Rechtschreibkorrektur (für Korrekturvorschläge) * Suche nach ähnlichen Schlüsselwörtern (Überwachung, Spracherkennung#Sprachmodell Spracherkennung, ...) * Grundwortreduktion (Stemming) im Information Retrieval

Verschwörungstheorie
Durch die Anwendung der N-Gram-Analyse in der Kryptoanalyse stand bis vor kurzem auch auf dieser Seite, dass die N-Gram-Analyse eine "am 23.05.1995 patentierte Entwicklung" der NSA sei. Jedoch verweist bereits der in der englischen als Urheber genannte Claude Elwood Shannon in seinem 1948 erschienenen Buch A mathematical Theory of Communication (Seite 5) auf das Buch Secret and Urgent von Fletcher Pratt. 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. Da die NSA die N-Gram Analyse demzufolge nicht erfunden hat, und schon gar nicht am 23.5. Dreiundzwanzig, kann es demzufolge höchstens sein, dass sie eine bestimmte Technologie zur Anwendung von N-Grammen als Patent angemeldet hat. Kategorie:Algorithmus Kategorie:Korpuslinguistik Kategorie:Künstliche Intelligenz

*** Shopping-Tipp: N-Gram-Analyse




[Der Artikel zu N-Gram-Analyse stammt aus dem Nachschlagewerk Wikipedia, der freien Enzyklopädie. Dort findet sich neben einer Übersicht der Autoren die Möglichkeit, den Original-Text des Artikels N-Gram-Analyse zu editieren.
Die Texte von Wikipedia und dieser Seite stehen unter der GNU Free Documentation License.]

<<Zurück | Zur Startseite | Impressum | Zum Beginn dieser Seite