Схема базы данных для хранения ngrams с многократным поиска элемента

Question

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

• Fetch все ngrams
• Fetch все ngrams определенного размера
• Fetch все ngrams, которые содержат все эти данные элементы в любом положении (подмножества)
• извлечь все ngrams определенного размера, которые имеют эти данные элементы в этих положениях (шаблон)

Примером для третьего пункта будут все ngrams, содержащие «a», «b» и «c», что приводит к такимграммам, как (a, b, c), (b, c, a), (x, a, z, b, c) и т. д.

Примером для четвертого пункта будут все ngrams, следующие за шаблоном (a, *, *, b), что приводит к появлению таких nграмм, как (a, x, y, b), (a, a, a, b) и т. д.

В настоящее время я храню их в таблице базы данных с отдельным полем для каждого элемента ngram, но это не кажется лучшим вариант для поиска nграмм, содержащих заданные элементы в любом порядке и в позиции. Для того, чтобы найти 3grams, содержащих «а», «б» и «в» Я использую следующий SQL «где» раздел:

WHERE 
    (ele0 = 'a' OR ele1 = 'a' OR ele2 = 'a') AND 
    (ele0 = 'b' OR ele1 = 'b' OR ele2 = 'b') AND 
    (ele0 = 'c' OR ele1 = 'c' OR ele2 = 'c') 

Это не масштабироваться до хорошо на всех. Есть ли лучший способ структурировать данные и запросить его?

Answer 1

Вы не указали, что такое «большое число». Я не могу думать о том, как поддерживать все операции, которые вы хотите, используя стандартные методы оптимизации SQL. В некоторых базах данных полная текстовая поддержка может помочь.

Если вы хотите использовать SQL (что вполне разумно как постоянное хранилище), я бы предложил вам просто использовать строки. Другими словами, ngram - это строка.

Ваши запросы будут выглядеть следующим образом:

select * 
from ngrams; 

select * 
from ngrams 
where len(ngram) = XXX 

select * 
from ngrams 
where ngram like '%a%' and ngram like '%b%' and ngram like '%c%'; 

select * 
from ngrams 
where ngram like 'a__b'; 

Вы можете улучшить эту структуру, чтобы сделать его более эффективным для некоторых запросов. Например, если вы хотите оптимизировать запросы для получения длины, добавьте столбец length и проиндексируйте его (это будет не очень полезно, если у вас много разных длин). Чтобы оптимизировать запросы третьего типа, добавьте новый столбец, который имеет элементы в алфавитном порядке (так, «ЦБ» также будет иметь столбец «ABC»). Индекс этого будет облегчать запросы третьего типа.

EDIT (в ответ на комментарий):

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

Вы можете легко обрабатывать слова с помощью приведенной выше схемы, просто введя разделитель, который не является допустимым символом в любом слове, скажем, разделитель '|'. Таким образом, п-граммовый «ABC» будет храниться в виде «| | B | C |»:

select * 
from ngrams; 

select * 
from ngrams 
where ngramLen = XXX 

select * 
from ngrams 
where ngram like '%|a|%' and ngram like '%|b|%' and ngram like '%|c|%'; 

select * 
from ngrams 
where ngram like |a|%|b|' and ngramLen = 4; 

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

Учитывая, что вы думаете о том, что у вас есть миллионы ngrams, у вас есть проблема. Со словами это может занимать до гигабайт памяти. Для производительности вам нужно, чтобы таблица вписывалась в память. Эти операции очень хорошо подходят для параллельной базы данных, поэтому процесс будет масштабироваться плавно. На самом деле одно из преимуществ использования базы данных состоит в том, что вы можете просто бросить больше памяти/диска/процессоров в проблему, и вы получите лучшую производительность.