Speichern von n-Gramm-Daten

Ich hatte gehofft, ein wenig über das Speichern von n- Gramm-Daten nachdenken zu können. In meinem Projekt versuche ich, sprachliche Probleme zu lösen, bei denen ich alle ( n -1) Datenelemente kenne und mein n mithilfe einer linearen Interpolation über alle anwendbaren n- Gramme statistisch erraten möchte. (Ja, es gibt einen Tagger, der bekannten Wörtern Tags gemäß seinem Lexikon zuweist, und einen Suffixbaum, der versucht, die Wortart für unbekannte Wörter zu erraten. Die hier diskutierte n- Gramm-Komponente wird mit der Lösung von Mehrdeutigkeiten beauftragt.)

Mein anfänglicher Ansatz wäre, einfach alle beobachteten n- Gramm-Daten (für n = 1..3, dh Monogramm, Bigram, Trigramm) in den jeweiligen SQL-Datenbanken zu speichern und sie einen Tag lang aufzurufen. Die Anforderungen meines Projekts können sich jedoch ändern und andere Vektorlängen ( n ) enthalten, und ich möchte, dass sich meine Anwendung ohne großen Aufwand (Aktualisieren des Schemas, Aktualisieren des Anwendungscodes usw.) an 4 Gramm anpasst. Im Idealfall würde ich meiner Anwendung einfach sagen, dass sie jetzt mit 4 Gramm arbeiten soll, ohne den Code viel (oder überhaupt) ändern und ihre Daten aus einer bestimmten Datenquelle trainieren zu müssen.

Um alle Anforderungen zusammenzufassen:

• Fähigkeit zum Speichern von n- Gramm-Daten (anfänglich für n = {1, 2, 3})
• Möglichkeit zu ändern, welche Arten von n- Gramm verwendet werden sollen (zwischen Anwendungsläufen)
• Fähigkeit zum ( erneuten ) Trainieren von n- Gramm-Daten (zwischen Anwendungsläufen)

• Möglichkeit, den Datenspeicher abzufragen (z. B. wenn ich A, B, C beobachtet habe, möchte ich anhand meiner trainierten 4-, 3-, 2-, 1-Gramm-Datensätze wissen, welches Element am häufigsten beobachtet wird )

  Die Anwendung wird höchstwahrscheinlich leselastig sein, Datensätze werden höchstwahrscheinlich nicht so oft umgeschult

• Die Lösung verwendet .NET Framework (bis zu 4.0).

Welches Design passt nun besser zu einer solchen Aufgabe?

• Eine feste Tabelle, die von einem SQL Server (MSSQL, MySQL, ...) für jedes n verwaltet wird (z. B. dedizierte Tabellen für Bi-Gramm, Tri-Gramm usw.).
• Oder eine NoSQL-Dokumentendatenbanklösung, die das erste n -1 als Schlüssel des Dokuments speichert und das Dokument selbst den n- ten Wert und die beobachteten Häufigkeiten enthält?
• Oder etwas anderes?

Da Sie den optimalen Bereich von N nicht kennen, möchten Sie ihn auf jeden Fall ändern können. Wenn Ihre Anwendung beispielsweise die Wahrscheinlichkeit vorhersagt, dass ein bestimmter Text Englisch ist, möchten Sie wahrscheinlich das Zeichen N-Gramm für N 3..5 verwenden. (Das haben wir experimentell gefunden.)

Sie haben keine Details zu Ihrer Anwendung mitgeteilt, aber das Problem ist klar genug. Sie möchten N-Gramm-Daten in einer relationalen Datenbank (oder einer dokumentbasierten NoSQL-Lösung) darstellen. Bevor Sie eine eigene Lösung vorschlagen, sollten Sie sich die folgenden Ansätze ansehen:

1. Wie speichere ich Google ngrams am besten in einer Datenbank?
2. Speichern von n-Gramm in der Datenbank in <n Tabellen
3. Verwalten des Google Web 1T 5-Gramm mit der relationalen Datenbank

Nachdem ich keinen der oben genannten Links gelesen habe, schlage ich einen einfachen relationalen Datenbankansatz vor, der mehrere Tabellen verwendet, eine für jede Größe von N-Gramm. Sie könnten alle Daten in eine einzige Tabelle mit den maximal erforderlichen Spalten einfügen (dh Bigrams und Trigramme in ngram_4 speichern, wobei die letzten Spalten null bleiben), aber ich empfehle, die Daten zu partitionieren. Abhängig von Ihrem Datenbankmodul kann eine einzelne Tabelle mit einer großen Anzahl von Zeilen die Leistung beeinträchtigen.

  create table ngram_1 (
      word1 nvarchar(50),
      frequency FLOAT,
   primary key (word1));

  create table ngram_2 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2));

  create table ngram_3 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      word3 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2, word3));

  create table ngram_4 (
      word1 nvarchar(50),
      word2 nvarchar(50),
      word3 nvarchar(50),
      word4 nvarchar(50),
      frequency FLOAT,
   primary key (word1, word2, word3, word4));

Als nächstes werde ich Ihnen eine Abfrage geben, die das wahrscheinlichste nächste Wort bei all Ihren ngram-Tabellen zurückgibt. Aber zuerst sind hier einige Beispieldaten, die Sie in die obigen Tabellen einfügen sollten:

  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'building', N'with', 0.5)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'hit', N'the', 0.1)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'man', N'hit', 0.2)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'bat', 0.7)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'building', 0.3)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'the', N'man', 0.4)
  INSERT [ngram_2] ([word1], [word2], [frequency]) VALUES (N'with', N'the', 0.6)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'building', N'with', N'the', 0.5)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'hit', N'the', N'building', 0.3)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'man', N'hit', N'the', 0.2)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'the', N'building', N'with', 0.4)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'the', N'man', N'hit', 0.1)
  INSERT [ngram_3] ([word1], [word2], [word3], [frequency]) VALUES (N'with', N'the', N'bat', 0.6)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'building', N'with', N'the', N'bat', 0.5)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'hit', N'the', N'building', N'with', 0.3)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'man', N'hit', N'the', N'building', 0.2)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'the', N'building', N'with', N'the', 0.4)
  INSERT [ngram_4] ([word1], [word2], [word3], [word4], [frequency]) VALUES (N'the', N'man', N'hit', N'the', 0.1)

Um das wahrscheinlichste nächste Wort abzufragen, würden Sie eine Abfrage wie diese verwenden.

  DECLARE @word1 NVARCHAR(50) = 'the'
  DECLARE @word2 NVARCHAR(50) = 'man'
  DECLARE @word3 NVARCHAR(50) = 'hit'
  DECLARE @bigramWeight FLOAT = 0.2;
  DECLARE @trigramWeight FLOAT = 0.3
  DECLARE @fourgramWeight FLOAT = 0.5

  SELECT next_word, SUM(frequency) AS frequency
  FROM (
    SELECT word2 AS next_word, frequency * @bigramWeight AS frequency
    FROM ngram_2
    WHERE word1 = @word3
    UNION
    SELECT word3 AS next_word, frequency * @trigramWeight AS frequency
    FROM ngram_3
    WHERE word1 = @word2
      AND word2 = @word3
    UNION
    SELECT word4 AS next_word, frequency * @fourgramWeight AS frequency
    FROM ngram_4
    WHERE word1 = @word1
      AND word2 = @word2
      AND word3 = @word3
    ) next_words
  GROUP BY next_word
  ORDER BY SUM(frequency) DESC

Wenn Sie weitere ngram-Tabellen hinzufügen, müssen Sie der obigen Abfrage eine weitere UNION-Klausel hinzufügen. Möglicherweise stellen Sie fest, dass ich in der ersten Abfrage word1 = @ word3 verwendet habe. Und in der zweiten Abfrage ist word1 = @ word2 AND word2 = @ word3. Das ist , weil wir müssen ausrichten , die drei Wörter in der Abfrage für die ngram Daten. Wenn wir das wahrscheinlichste nächste Wort für eine Folge von drei Wörtern wollen, müssen wir das erste Wort in den Bigram-Daten mit dem letzten Wort der Wörter in der Folge vergleichen.

Sie können die Gewichtsparameter nach Ihren Wünschen anpassen. In diesem Beispiel habe ich angenommen, dass höhere Ordnungszahlen "n" zuverlässiger sind.

PS Ich würde den Programmcode so strukturieren, dass er eine beliebige Anzahl von ngram_N-Tabellen über die Konfiguration verarbeitet. Sie können das Programm deklarativ ändern, um den N-Gramm-Bereich N (1..6) zu verwenden, nachdem Sie die Tabellen ngram_5 und ngram_6 erstellt haben.

Im Gegensatz zu den Vorschlägen der anderen würde ich vorschlagen, Datenstrukturen zu vermeiden, die komplexer sind als eine Hashmap oder ein Schlüsselwertspeicher.

Beachten Sie Ihre Datenzugriffsanforderungen: a) 99% -Anfragen - fragen Sie ngram "aaa-bbb-ccc" ab und erhalten Sie den Wert (oder 0) b) 1% -Anfragen - Einfügen / Aktualisieren einer Anzahl spezifischer ngram c) es gibt keine (c).

Am effektivsten ist es, es mit einer einzigen Suche abzurufen. Sie können ein außerhalb der Grenzen liegendes (oder maskiertes) Trennzeichen verwenden, um das gesamte n-Gramm in einer einzelnen Zeichenfolge zu kombinieren (z. B. "alpha | beta | gamma" für 3 Gramm, "alpha" für Unigramm usw.) und das einfach abzurufen ( durch den Hash davon). So viel NLP-Software macht das.

Wenn Ihre ngram-Daten klein sind (z. B. <1 GB) und in den Speicher passen, würde ich empfehlen, eine effiziente programminterne Speicherstruktur (Hashmaps, Bäume, Versuche usw.) zu verwenden, um Overhead zu vermeiden. und einfach in flache Dateien serialisieren / deserialisieren. Wenn Ihre ngram-Daten Terabyte oder mehr betragen, können Sie NoSQL-Schlüsselwertspeicher auswählen, die auf mehrere Knoten aufgeteilt sind.

Für zusätzliche Leistung möchten Sie möglicherweise alle Wörter überall durch ganzzahlige IDs ersetzen, damit Ihr Kernalgorithmus überhaupt keine (langsamen) Zeichenfolgen sieht. dann ist es etwas anders, die gleiche Idee umzusetzen.

Nicht die effizienteste, aber einfach und wie gewünscht mit der Datenbank verbunden:

Table: word
Colums:
word (int, primary key) - a unique identifier for each word
text (varchar) - the actual word

Table: wordpos
Columns:
document (int) - a unique identified for the document of this word
word (int, foreign key to word.word) - the word in this position
pos (int) - the position of this word (e.g., first word is 1, next is 2, ...)

wordpos sollte Indizes für document und pos haben.

Bigrams sind:

select word1.text as word1, word2.text as word2
from wordpos as pos1, wordpos as pos2, word as word1, word as word2
where pos1.document = pos2.document
      and pos1.pos = pos2.pos - 1
      and word1.word = pos1.word
      and word2.word = pos2.word

Dann können Sie zählen () und Ihren Weg zu Frequenzen und anderen Dingen gruppieren.

Um zu Trigrammen zu wechseln, ist es einfach, diese Zeichenfolge mit einem Wort3 zu generieren.

Ich habe das schon einmal gemacht (obwohl das SQL dort oben wahrscheinlich etwas verrostet ist). Ich entschied mich für eine Reihe von Flatfiles, die leicht gesucht und dann von der Festplatte gestreamt werden konnten. Ein bisschen hängt von Ihrer Hardware ab, wie man es besser macht.

Bei dem Versuch, die einfache Suche meiner Anwendungen nach Bigrams und Trigrammen von Unigrammen zu verbessern, habe ich im Wesentlichen Ihre Frage gesehen.

Wenn eine der Anforderungen die Fähigkeit ist, ein verteiltes Dateisystem oder eine verteilte Datenbank abzufragen, könnte dies auch für Sie interessant sein: Das Papier Pibiri und Venturini 2018 "Effizienter Umgang mit massiven N-Gramm-Datensätzen" beschreibt eine effiziente Möglichkeit zum Speichern von n-Gramm-Daten Laufzeit und Platz. Sie haben ihre Implementierung unter https://github.com/jermp/tongrams angeboten

Jedes "n" von n-Gramm wird in einer separaten Tabelle gespeichert, auf die über eine minimale perfekte Hash-Funktion mit sehr schnellen Auswahl- und Abfragefähigkeiten zugegriffen werden kann. Die Tabellen sind statisch und werden vom Hauptcode unter Verwendung der Eingabe im Format von Google n-Gramm-Textdateien erstellt.

Ich habe den Code noch nicht verwendet, aber es gibt viele Möglichkeiten, wie Sie mit Ihren offenen Anforderungen angeben können, woher Ihre Abfragen stammen.

Eine Möglichkeit: Wenn das .NET-Äquivalent eines Servlets mit einer Datenbank oder einem Datenspeicher verwendet wird und Sie Speicherplatz sparen müssen, ist das Speichern jeder ngram-Tabelle in binärer Form in der Datenbank / dem Datenspeicher als Tabelle eine Option (eine Datenbank) / Datenspeichertabelle für die resultierende statische Datei des effizienten Ngramm-Codes für alle 1 Gramm, eine andere für alle 2 Gramm usw.). Abfragen werden ausgeführt, indem der effiziente n-Gramm-Code aufgerufen wird (umschlossen, damit Ihr Servlet darauf zugreifen kann). Es ist eine Problemumgehung, um eine verteilte Datenbank zu erstellen, die den effizienten n-Gramm-Code verwendet, um auf die Dateien in einem verteilten Dateisystem zuzugreifen. Beachten Sie, dass die binären Datenbank- / Datenspeichertabellen jeweils die Dateigrößenbeschränkung des zugrunde liegenden Dateisystems aufweisen.