Как осуществляется эффективный последовательный поиск слов?

Question

Поисковые системы и базы данных позволяют вам использовать последовательный поиск строк (например, "this is a test"), который соответствует this is a test that will match, но не соответствует test this is a.

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

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

Что будет проиндексированотаблица выглядит как приведенный выше пример?Будет ли что-то похожее на это?

// IndexedItemID | Position | Word
1 | 0 | this
1 | 1 | is
1 | 2 | a
1 | 3 | test
1 | 4 | that
1 | 5 | will
1 | 6 | match
2 | 0 | test
2 | 1 | this
2 | 2 | is
2 | 3 | a

Теперь, когда есть проиндексированные элементы, как эффективно создать оператор SQL, соответствующий этим элементам?

Вот один пример, который я могу вспомнить:

select IndexedItemID form
  (select IndexedItemID, Position from indexedWords where Word = "this") as word1Position
where
  exists(select * from indexedWords where IndexedItemID = word1Position.IndexedItemID AND Word = "is" AND Position = word1Position.Position + 1)
  AND exists(select * from indexedWords where IndexedItemID = word1Position.IndexedItemID AND Word = "a" AND Position = word1Position.Position + 2)
  AND exists(select * from indexedWords where IndexedItemID = word1Position.IndexedItemID AND Word = "test" AND Position = word1Position.Position + 3)

Я уверен, что, возможно, есть более стандартизированный способ, который более эффективен.

Answer 1

То, что вы хотите, это отсортированный перевернутый индекс слов из вашего документа.В основном, если ваш текст

«Вот пример предложения. Это то, как вы индексируете вещи», вы превращаете это в:

Here: 1
is: 2, 7
an: 3
example: 4
......
......

Затем, когда вы ищете последовательность слов,Вы ищите список позиций для каждого слова.Теперь вы хотите пройти список отсортированных позиций одновременно, как если бы вы пытались объединить списки.при объединении списков было бы легко определить, где находится список слов в той последовательности, в которой вы хотите.

Answer 2

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

Answer 3

Я не уверен, как база данных sql сузит свой поиск, но в конечном итоге это приведет к совпадению строк.

Если у вас есть целевая строка и строка шаблона, самый простой способ сделать сравнение - начать с начала целевой строки и попытаться сопоставить ее с символьной строкой строки шаблона. Если совпадение не удалось, вы переходите к следующему символу в целевой строке и повторяете вышеуказанный шаг. Это, очевидно, неэффективно, поскольку сложность имеет порядок O (m * n), где m - количество символов в строке шаблона, а n - количество символов в целевой строке.

Существует алгоритм под названием Алгоритм Рабина-Карпа , который может выполнять этот поиск в O (m + n) с использованием хеширования.

Конечно, mysql мог вычислить хэши, которые помогли бы уменьшить количество целевых строк.