Хранение n-граммовых данных

Я надеялся немного подумать о сохранении данных n- граммы. В моем проекте я пытаюсь решить лингвистические проблемы, когда я знаю все ( n -1) элементы данных и хочу статистически угадать мой n, используя линейную интерполяцию по всем применимым n- диаграммам. (Да, есть тегер, который назначает теги известным словам в соответствии с его лексиконом, и дерево суффиксов, которое пытается угадать вид слова для неизвестных слов; обсуждаемый здесь компонент n -gram будет решен с целью устранения неоднозначности.)

Мой первоначальный подход состоял бы в том, чтобы просто сохранить все наблюдаемые n- грамм (для n = 1,3), то есть данные монограммы, биграммы, триграммы, в соответствующих базах данных SQL и назвать их день. Но требования моего проекта могут измениться, чтобы включить другие длины вектора ( n ), и я хотел бы, чтобы мое приложение адаптировалось к 4-граммовому без большой работы (обновление схемы, обновление кода приложения и т. Д.); в идеале я бы просто сказал, чтобы мое приложение теперь работало с 4-граммами без особого (или вообще) значительного изменения кода и обучения его данных из заданного источника данных.

Подводя итог всем требованиям:

• Возможность хранить данные n- граммы (изначально для n = {1, 2, 3}
• Возможность изменения того, какие типы n- диаграмм следует использовать (между запусками приложения)
• Возможность ( пере ) обучения данных n- граммы (между запусками приложения)

• Возможность запрашивать хранилище данных (например, если я наблюдал A, B, C, я хотел бы знать наиболее часто наблюдаемый элемент для того, что может последовать, используя мои обученные 4-, 3-, 2-, 1-граммовые наборы данных )

  Скорее всего, приложение будет загружено для чтения, наборы данных, скорее всего, не будут переучиваться так часто

• В решении используется .NET Framework (до 4.0)

Какой дизайн лучше подходит для такой задачи?

• Фиксированная таблица, управляемая сервером SQL (MSSQL, MySQL, ...) для каждого n (например, выделенные таблицы для биграмм, триграмм и т. Д.)
• Или решение для базы данных документов NoSQL, в котором в качестве ключа документа хранятся первые n -1, а сам документ содержит n- ое значение и наблюдаемые частоты?
• Или что-то другое?

Учитывая, что вы не будете знать оптимальный диапазон N, вы определенно захотите его изменить. Например, если ваше приложение прогнозирует вероятность того, что определенный текст является английским, вы, вероятно, захотите использовать N-граммы символов для N 3..5. (Это то, что мы обнаружили экспериментально.)

Вы не поделились информацией о вашем приложении, но проблема достаточно ясна. Вы хотите представить N-граммовые данные в реляционной базе данных (или решении на основе документов NoSQL). Прежде чем предлагать собственное решение, вы можете взглянуть на следующие подходы:

1. Как лучше хранить Google Ngrams в базе данных?
2. Хранение n-граммов в базе данных в количестве <n таблиц
3. Управление Google Web 1T 5-грамм с реляционной базой данных

Теперь, не прочитав ни одной из вышеуказанных ссылок, я предлагаю простой подход к реляционной базе данных, использующий несколько таблиц, по одной для каждого размера N-граммы. Вы можете поместить все данные в одну таблицу с максимально необходимыми столбцами (т.е. хранить биграммы и триграммы в ngram_4, оставляя последние столбцы пустыми), но я рекомендую разбить данные на части. В зависимости от вашего механизма базы данных, одна таблица с большим количеством строк может негативно повлиять на производительность.

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

Далее я дам вам запрос, который вернет наиболее вероятное следующее слово для всех ваших таблиц ngram. Но сначала, вот некоторые примеры данных, которые вы должны вставить в приведенные выше таблицы:

  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)

Чтобы запросить наиболее вероятное следующее слово, вы должны использовать такой запрос.

  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

Если вы добавите больше таблиц ngram, вам нужно будет добавить еще одно предложение UNION к вышеуказанному запросу. Вы можете заметить, что в первом запросе я использовал word1 = @ word3. И во втором запросе word1 = @ word2 AND word2 = @ word3. Это потому, что нам нужно выровнять три слова в запросе для данных ngram. Если мы хотим получить наиболее вероятное следующее слово для последовательности из трех слов, нам нужно сравнить первое слово в данных биграммы с последним словом из слов в последовательности.

Вы можете настроить весовые параметры по своему желанию. В этом примере я предположил, что старшие порядковые n граммов будут более надежными.

PS Я бы структурировал программный код для обработки любого количества таблиц ngram_N через конфигурацию. Вы можете декларативно изменить программу на использование диапазона N-грамм N (1..6) после создания таблиц ngram_5 и ngram_6.

Вопреки тому, что предлагают другие, я бы посоветовал избегать любых структур данных, более сложных, чем хэш-карта или хранилище значений ключей.

Помните о ваших требованиях к доступу к данным: a) 99% запросов - запросите ngram "aaa-bbb-ccc" и получите значение (или 0); b) 1% запросов - добавьте / обновите число определенных ngram; c) нет (с).

Самый эффективный способ - получить его одним поиском. Вы можете использовать за пределами (или экранированный) разделитель, чтобы объединить полный n-грамм в одну строку (например, «alpha | beta | gamma» для 3-граммы, «alpha» для униграммы и т. Д.) И просто получить это ( по хэшу этого). Вот как это делает довольно много программного обеспечения НЛП.

Если ваши данные ngram малы (скажем, <1 ГБ) и помещаются в памяти, то я бы предложил использовать эффективную структуру памяти в программе (хеш-карты, деревья, попытки и т. Д.), Чтобы избежать накладных расходов; и просто сериализовать / десериализовать в плоские файлы. Если ваши данные ngram составляют терабайты или больше, вы можете выбрать хранилища ключей-значений NoSQL, разделенные на несколько узлов.

Для повышения производительности вы можете захотеть заменить все слова везде целочисленными идентификаторами, чтобы ваш основной алгоритм вообще не видел (медленных) строк; тогда немного по-другому реализовать ту же идею.

Не самая эффективная, но простая и встроенная в базу данных, как вы хотите:

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 должны быть индексы на документе и поз.

биграммы это:

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

Затем вы можете считать () и группировать свой путь к частотам и прочее.

Чтобы перейти на триграммы, легко сгенерировать эту строку, чтобы включить слово 3.

Я сделал это раньше на самом деле (хотя SQL там, вероятно, немного ржавый). Я остановился на наборе плоских файлов, которые можно было легко найти, а затем стереть с диска. Вид зависит от вашего оборудования, как сделать это лучше.

Пытаясь улучшить простой поиск в моих приложениях по биграммам и триграммам из униграмм, по сути, я понял ваш вопрос.

Если одним из требований является возможность запроса распределенной файловой системы или базы данных, то это может быть также интересно для вас: в статье Pibiri и Venturini 2018 «Эффективная обработка массивных наборов данных N-граммы» описывается эффективный способ хранения данных N-граммы в сроки выполнения и пространство. Они предложили свою реализацию на https://github.com/jermp/tongrams

Каждое «n» из n-граммов хранится в отдельной таблице, доступ к которой осуществляется с помощью минимальной идеальной хеш-функции с очень быстрым выбором и запросом. Таблицы статичны и построены по основному коду с использованием ввода в формате текстовых файлов Google n-грамм.

Я еще не использовал этот код, но есть много способов, которыми вы могли бы с вашими открытыми требованиями о том, откуда ваши запросы.

Один из способов: если .NET-эквивалент сервлета используется с базой данных или хранилищем данных, и если вам необходимо сэкономить место для хранения, то сохранение каждой таблицы ngram в двоичном виде в базе данных / хранилище данных в виде таблицы - это один вариант (одна база данных / datastore таблица для результирующего статического файла эффективного кода ngram для всех 1 граммов, еще один для всех 2 граммов и т. д.). Запросы будут выполняться путем вызова эффективного n-граммового кода (обернутого, чтобы быть доступным для вашего сервлета). Это обходной путь для создания распределенной базы данных, которая использует эффективный n-граммовый код для доступа к файлам в распределенной файловой системе. Обратите внимание, что каждая двоичная таблица базы данных / хранилища данных имеет ограничение на размер файла базовой файловой системы.