Как работают полнотекстовые индексаторы (или кэши)?

Question

Интересно, как реализованы системы для полнотекстового поиска, чтобы можно было запрашивать миллионы записей очень быстро? Обратите внимание: я не говорю о системах, которые токенизируют контент, разделяя его в пробелах, а о системах, которые способны запросить даже детали из середины токенов (что является настоящим вызовом).

Справочная информация
Я экспериментировал с самодельным строковым кешером (использующим Java), который умеет искать для строк, учитывая подстроку в качестве запроса. Подстрока не требуется быть в начале потенциальных найденных строк.

Работает с огромным массивом строк. Кэширование выполняется с использованием
TreeMap<Character,TreeSet<String>>.

Добавление записи
Для каждого уникального символа в добавляемой строке:
Получите набор для этого символа и добавьте к нему строку.

Пример: «test» сначала разбивается на «t», «e», «s».
Затем мы получаем наборы для тех, три клавиши и добавьте «тест» к каждому набору.

Querieng
Запросы выполняются путем разделения запроса на уникальные символы, получить для каждого символа Set<String>, построить пересечение все наборы и, наконец, найдите пересечение, используя contains(), чтобы убедиться, что порядок символов запроса.

Benchmark
На машине 3GHz я добавил 2'000'000 строк со средней длиной 10 , случайное содержание.
Выполнено 100 запросов. Потребовалось: Мин: 0,4 с, Среднее: 0,5 с, Макс: 0,6 с .
1,5 ГБ памяти было потрачено впустую.

Answer 1

Один из способов сделать это - сохранить перестановочную перестановку всех хвостов вашего текста (текст от определенной точки до конца).

Затем, чтобы найти подстроку, вы бинарно ищете ее в этих циклических сдвигах. Объем памяти, используемой с использованием 32-битных битов, составляет 4 байта на исходный символ.

ps: я слышал, что есть способ сделать подобное, сохранив преобразование Берроуза-Уилера текста (1 символ на исходный персонаж), но я не могу найти никаких ссылок на это ..

Answer 2

Я внедрил такую ​​систему, для одного из них предлагается выпадающий список на веб-сайте с использованием индексации по n-граммах, в частности по 3 грамма. Вы разбиваете слово на составляющие n-граммы, например, для слова «привет» вы получите «hel», «lo». Затем вы строите индекс с n-граммами в качестве ключей, а слова, из которых они взяты, являются значениями. (Я использовал Trie для скорости, память была меньшим беспокойством). Далее, для данного запроса вы разбиваете его на n-граммы тем же процессом, что и при индексации, и выполняете поиск по каждому n-грамму, получая список возможных совпадений. Из этого списка вы выбираете слова с наибольшим количеством совпадающих n-грамм. Вы также можете использовать различные эвристики. Во-первых, совпадения в начале слова, как правило, более важны, поэтому вы можете дополнить все слова символом $.

Answer 3

Вы можете посмотреть на Lucene. Но я думаю, что в целом они делают токенизацию входного текста. Может быть, не только через пробел, но и с использованием более коротких последовательностей слов. Я не думаю, что односимвольные токены возможны.

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