Лекция
Привет, Вы узнаете о том , что такое Введение - Индексируйте ключей с помощью автоматов , Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое Введение - Индексируйте ключей с помощью автоматов , настоятельно рекомендую прочитать все из категории Индексирование большого набора ключей с помощью конечных автоматов.
Оказывается, конечные автоматы полезны для других вещей, кроме выражения вычислений. Конечные автоматы также можно использовать для компактного представления упорядоченных наборов или отображений строк, в которых можно очень быстро искать.
Рассмотрим конечные автоматы как структуре данных для представления упорядоченных наборов и карт. Это включает в себя введение написанной на Rust реализации, называемой fstcrate . Поставляется с полной документацией по API . Так же рассмотрим, как создавать их с помощью простого инструмента командной строки. Рассмотрим несколько экспериментов, завершившихся индексированием более 1 600 000 000 URL (134 ГБ) из общего архива сканирования .
Методика, представленная в этой статье, также показывает, как Lucene представляет часть своего инвертированного индекса .
Попутно мы поговорим о картах памяти, пересечении автоматов с регулярными выражениями, нечетком поиске с расстоянием Левенштейна и операциях потокового множества.
Целевая аудитория : некоторое знакомство с программированием и фундаментальными структурами данных. Опыт работы с теорией автоматов или Rust не требуется.
В качестве показателя, чтобы показать, куда мы движемся, давайте кратко рассмотрим пример. Мы пока не будем рассматривать 1600000000 ключей. Вместо этого рассмотрено ~ 16 000 000 заголовков статей в Википедии ( 384 MB). Об этом говорит сайт https://intellect.icu . Вот как их проиндексировать:
$ time fst set --sorted wiki-titles wiki-titles.fst real 0m18.310
Результирующий индекс,, wiki-titles.fstравен 157 MB. Для сравнения, gzip занимает 12секунды и сжимается до 91 MB. (Для некоторых наборов данных наша схема индексации может превзойти gzipкак скорость, так и степень сжатия.)
Однако вот чего gzipнельзя сделать: быстро найти все заголовки статей, начинающиеся с Homer the:
$ time fst grep wiki-titles.fst 'Homer the.*' Homer the Clown Homer the Father Homer the Great Homer the Happy Ghost Homer the Heretic Homer the Moe Homer the Smithers ... real 0m0.023s
Для сравнения, исходные несжатые данные grepзанимают 0.3секунды.
И, наконец, то, что даже grepне может сделать: быстро найти все заголовки статей на определенном расстоянии редактирования Homer Simpson:
$ time fst fuzzy wiki-titles.fst --distance 2 'Homer Simpson' Home Simpson Homer J Simpson Homer Simpson Homer Simpsons Homer simpson Homer simpsons Hope Simpson Roger Simpson real 0m0.094s
Эта статья довольно длинная, поэтому, если вы пришли только ради фанатской платы за проезд, вы можете сразу перейти к разделу, где мы индексируем 1 600 000 000 ключей .
В первом разделе рассматриваются конечные автоматы и их использование в качестве структур данных в абстрактной форме. Этот раздел предназначен для того, чтобы дать вам мысленную модель, с помощью которой можно рассуждать о структуре данных. В этом разделе нет кода.
Во втором разделе используется абстракция, разработанная в первом разделе, и демонстрируется ее реализация. Этот раздел в основном предназначен для обзора того, как использовать мою fst библиотеку. Этот раздел содержит код. Мы обсудим некоторые детали реализации, но избегаем сорняков. Можно пропустить этот раздел, если вас не волнует код, а вы хотите увидеть эксперименты только с реальными данными.
Третий и последний раздел демонстрирует использование простого инструмента командной строки для построения индексов. Мы рассмотрим некоторые реальные наборы данных и попытаемся рассуждать о производительности конечных автоматов как структуры данных.
Исследование, описанное в статье про Введение - Индексируйте ключей с помощью автоматов , подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое Введение - Индексируйте ключей с помощью автоматов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Индексирование большого набора ключей с помощью конечных автоматов
Из статьи мы узнали кратко, но содержательно про
Комментарии
Оставить комментарий
Индексирование большого набора ключей с помощью конечных автоматов
Термины: Индексирование большого набора ключей с помощью конечных автоматов