Przechowywanie danych n-gramowych

Miałem nadzieję na burzę mózgów na temat przechowywania danych n- gram. W moim projekcie próbuję rozwiązać problemy językowe, w których znam wszystkie elementy danych ( n -1) i chcę statystycznie odgadnąć moje n za pomocą interpolacji liniowej dla wszystkich odpowiednich n- gramów. (Tak, istnieje tagger, który przypisuje tagi do znanych słów zgodnie z jego leksykonem i drzewem sufiksów, które próbują odgadnąć rodzaj słowa dla nieznanych słów; omawiany tutaj komponent n -gram będzie miał zadanie rozwiązać ambugułę).

Moje początkowe podejście polegałoby po prostu na przechowywaniu wszystkich zaobserwowanych n- gramów (dla n = 1..3, tj. Monogramu, bigrama, trigramu) w odpowiednich bazach danych SQL i nazywanie go dniem. Ale wymagania mojego projektu mogą ulec zmianie i obejmować inne długości wektorów ( n ), i chciałbym, aby moja aplikacja dostosowała się do 4 gramów bez większego nakładu pracy (aktualizacja schematu, aktualizacja kodu aplikacji itp.); idealnie, po prostu powiedziałbym mojej aplikacji, aby teraz pracowała z 4-gramami, bez konieczności zmiany kodu (lub wcale) i trenowania danych z danego źródła danych.

Podsumowując wszystkie wymagania:

• Możliwość przechowywania danych n- gram (początkowo dla n = {1, 2, 3}
• Możliwość zmiany, jakiego rodzaju n- gramów należy użyć (między uruchomieniami aplikacji)
• Możliwość (ponownego) trenowania danych n- gramowych (między uruchomieniami aplikacji)

• Możliwość zapytania do magazynu danych (np. Jeśli zaobserwowałem A, B, C, chciałbym poznać najczęściej obserwowany element, co może nastąpić przy użyciu wyszkolonych zestawów danych 4-, 3-, 2-, 1-gramowych )

  Aplikacja najprawdopodobniej będzie obciążona odczytem, ​​najprawdopodobniej zestawy danych nie będą tak często ponownie szkolone

• Rozwiązanie wykorzystuje platformę .NET Framework (do 4.0)

Jaki projekt byłby lepiej dopasowany do takiego zadania?

• Stała tabela zarządzana przez serwer SQL (MSSQL, MySQL, ...) dla każdego n (np. Dedykowane tabele dla bi-gramów, tri-gramów itp.)
• Lub rozwiązanie bazy danych dokumentów NoSQL, które przechowuje pierwsze n -1 jako klucz dokumentu, a sam dokument zawiera n-tą wartość i obserwowane częstotliwości?
• A może coś innego?

Biorąc pod uwagę, że nie poznasz optymalnego zakresu N, zdecydowanie chcesz móc go zmienić. Na przykład, jeśli twoja aplikacja przewiduje prawdopodobieństwo, że określony tekst jest angielski, prawdopodobnie będziesz chciał użyć N-gramów znaków dla N 3..5. (Właśnie to znaleźliśmy eksperymentalnie.)

Nie udostępniłeś szczegółowych informacji o swojej aplikacji, ale problem jest wystarczająco jasny. Chcesz reprezentować dane w gramach w relacyjnej bazie danych (lub rozwiązaniu opartym na dokumentach NoSQL). Zanim zaproponuję własne rozwiązanie, możesz rzucić okiem na następujące podejścia:

1. Jak najlepiej przechowywać ngramy Google w bazie danych?
2. Przechowywanie n-gramów w bazie danych w <n liczbie tabel
3. Zarządzanie Google Web 1T 5-gram za pomocą relacyjnej bazy danych

Teraz, nie czytając żadnego z powyższych łączy, sugeruję proste, relacyjne podejście do bazy danych przy użyciu wielu tabel, po jednej dla każdego rozmiaru N-gramów. Możesz umieścić wszystkie dane w jednej tabeli z maksymalną niezbędną liczbą kolumn (tj. Przechowywać bigramy i trygramy w ngram_4, pozostawiając końcowe kolumny puste), ale zalecam partycjonowanie danych. W zależności od silnika bazy danych pojedyncza tabela z dużą liczbą wierszy może mieć negatywny wpływ na wydajność.

  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));

Następnie dam ci zapytanie, które zwróci najbardziej prawdopodobne następne słowo, biorąc pod uwagę wszystkie tabele ngram. Ale po pierwsze, oto kilka przykładowych danych, które powinieneś wstawić do powyższych tabel:

  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)

Aby wyszukać najbardziej prawdopodobne następne słowo, użyj takiego zapytania.

  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

Jeśli dodasz więcej tabel ngram, będziesz musiał dodać kolejną klauzulę UNION do powyższego zapytania. Możesz zauważyć, że w pierwszym zapytaniu użyłem słowa1 = @ słowo3. A w drugim zapytaniu słowo1 = @ słowo2 ORAZ słowo2 = @ słowo3. Jest tak, ponieważ musimy wyrównać trzy słowa w zapytaniu dotyczącym danych ngram. Jeśli chcemy najbardziej prawdopodobnego następnego słowa dla ciągu trzech słów, będziemy musieli sprawdzić pierwsze słowo w danych bigram z ostatnim słowem słów w sekwencji.

Możesz dostosować parametry wagi, jak chcesz. W tym przykładzie założyłem, że wyższe porządkowe „n” gramy będą bardziej niezawodne.

PS Skonfiguruję kod programu, aby obsługiwał dowolną liczbę tabel ngram_N poprzez konfigurację. Można deklaratywnie zmienić program, aby używał zakresu N-gramów N (1..6) po utworzeniu tabel ngram_5 i ngram_6.

W przeciwieństwie do tego, co sugerują inni, sugerowałbym unikanie struktur bardziej złożonych niż tablica skrótów lub magazyn wartości kluczowych.

Pamiętaj o swoich wymaganiach dotyczących dostępu do danych: a) 99% żądań - zapytaj ngram „aaa-bbb-ccc” i pobierz wartość (lub 0) b) 1% żądań - wstawianie / aktualizowanie liczby określonych ngram c) nie ma (do).

Najbardziej skutecznym sposobem jest odzyskanie go za pomocą jednego wyszukiwania. Możesz użyć separatora spoza zakresu (lub klawisza zmiany znaczenia), aby połączyć pełny n-gram w jednym ciągu (np. „Alpha | beta | gamma” dla 3gram, „alpha” dla unigram itp.) I po prostu pobrać ten ( hash tego). Tak robi to całkiem sporo oprogramowania NLP.

Jeśli twoje dane ngram są małe (powiedzmy, <1 gb) i mieszczą się w pamięci, sugerowałbym użycie wydajnej struktury pamięci w programie (mapy skrótów, drzewa, próby itp.), Aby uniknąć narzutu; i po prostu serializuj / deserializuj do płaskich plików. Jeśli twoje dane ngram to terabajty lub więcej, możesz wybrać magazyny klucz-wartość NoSQL podzielone na wiele węzłów.

Aby uzyskać dodatkową wydajność, możesz zastąpić wszystkie słowa wszędzie identyfikatorami całkowitymi, aby Twój algorytm podstawowy nie widział żadnych (wolnych) ciągów; to nieco inaczej wdraża ten sam pomysł.

Nie najbardziej wydajny, ale prosty i dopasowany do bazy danych, jak chcesz:

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 powinny mieć indeksy w dokumencie i poz.

bigramy to:

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

Następnie możesz policzyć () i pogrupować drogę do częstotliwości i innych rzeczy.

Aby przejść na trygramy, łatwo jest wygenerować ten ciąg znaków, aby zawierał słowo 3.

Zrobiłem to już wcześniej (nawet jeśli SQL tam jest prawdopodobnie trochę zardzewiały). Zdecydowałem się na zestaw płaskich plików, które można łatwo wyszukać, a następnie przesłać strumieniowo z dysku. Rodzaj zależy od twojego sprzętu, jak to zrobić lepiej.

Próbując ulepszyć proste wyszukiwania moich aplikacji do bigramów i trygramów z unigramów, w zasadzie widziałem twoje pytanie.

Jeśli jednym z wymagań jest możliwość wysłania zapytania do rozproszonego systemu plików lub bazy danych, może to również być interesujące dla Ciebie: papier Pibiri i Venturini 2018 „Skuteczne przetwarzanie ogromnych zestawów danych N-Gram” opisuje skuteczny sposób przechowywania danych w gramach N warunki środowiska wykonawczego i przestrzeni. Zaproponowali wdrożenie na stronie https://github.com/jermp/tongrams

Każde „n” n-gramów jest przechowywane w osobnej tabeli, do której dostęp ma minimalna idealna funkcja skrótu z bardzo szybkimi możliwościami wyboru i zapytania. Tabele są statyczne i zbudowane przez główny kod przy użyciu danych wejściowych w formacie plików tekstowych Google n-gram.

Nie korzystałem jeszcze z tego kodu, ale istnieje wiele sposobów na spełnienie otwartych wymagań dotyczących źródła zapytań.

Jeden sposób: jeśli odpowiednik serwletu .NET jest używany z bazą danych lub magazynem danych i jeśli chcesz zaoszczędzić miejsce w pamięci, to przechowywanie każdej tabeli ngram w formie binarnej w bazie danych / magazynie danych jako jedna opcja (jedna baza danych / tabela danych dla wynikowego pliku statycznego wydajnego kodu ngram dla wszystkich 1-gramów, inny dla wszystkich 2-gramów itp.). Zapytania byłyby uruchamiane przez wywołanie wydajnego kodu n-gram (zapakowanego, aby był dostępny dla twojego serwletu). Obejściem problemu jest utworzenie rozproszonej bazy danych, która używa wydajnego kodu n-gram do uzyskiwania dostępu do plików w rozproszonym systemie plików. Zauważ, że w tabelach binarnych baz danych / magazynów danych obowiązują ograniczenia rozmiaru pliku systemu plików.