Эффективная модель базы данных для хранения данных, проиндексированных с помощью n-грамм

12

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

Мне нужны три эффективных типа операций: поиск и вставка, проиндексированные самой n-граммой, и запрос всех n-граммов, которые содержат вложенную n-грамм.

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

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

Phonon
источник
2
Я думаю, что структура, которую вы хотите реализовать, - это «пустяк» - вы не можете сказать, можете ли вы найти БД, которая эффективно работает с этой структурой, или вам нужно свернуть свою собственную в СУБД по вашему выбору.
Нил Слэйтер

Ответы:

9

Посмотреть Lucene NGramTokenizer

Вы уверены, что не можете просто использовать люцен или подобные методы индексации?

Инвертированные индексы будут хранить n-грамм только один раз, затем только идентификаторы документов, которые содержат ngram; они не хранят это как крайне избыточный необработанный текст.

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

ВЫЙТИ - Anony-Mousse
источник
3

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

Создайте 3 таблицы:

  1. Таблица документов, столбцы: идентификатор / документ
  2. Таблица N-грамм: n_gram_id / n_gram
  3. Отображение между n-граммами и документами: document_id / n_gram_id

Создайте индексы для таблицы N-грамм / строки n_gram и таблицы сопоставления / n_gram_id, также первичные ключи будут хорошо проиндексированы по умолчанию.

Ваши операции будут эффективными:

  1. Вставка документа: просто извлеките все n-граммы и вставьте в таблицу документов и таблицу N-грамм
  2. Поиск для in_gram будет быстрым с поддержкой индекса
  3. Запрашивать все n-граммы, которые содержат под-n-грамм: в 2 шага - просто запросить на основе индекса все n-граммы, которые содержат под-n-грамм из 2-й таблицы. Затем - получить все соответствующие документы для каждого из этих n-грамм.

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

Также вы можете использовать MongoDB, но я не уверен, как именно вам нужно реализовать схему индексации. Для MongoDB вы получите схему шардинга бесплатно, так как она уже встроена.

Максим Галушка
источник
1

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

Эмре
источник