Триграммный поиск
Триграммный поиск — это метод поиска текста, когда точный синтаксис или написание целевого объекта точно не известны. [1] или когда запросы могут быть регулярными выражениями . [2] Он находит объекты, соответствующие максимальному количеству трех последовательных строк символов (т. е. триграмм ) во введенных условиях поиска, которые обычно близки к совпадениям. [3] Можно ожидать, что две строки со многими общими триграммами будут очень похожими. [4] Триграммы также позволяют эффективно создавать индексы поисковых систем для поисков, которые являются регулярными выражениями или неточно соответствуют тексту. Индексы могут значительно ускорить поиск. [5] [6] Порог количества совпадений триграмм можно указать как точку отсечения после того, как результат не совпадает. [4]
Использование триграмм для ускорения поиска — это метод, используемый в некоторых системах для поиска кода в ситуациях, когда могут быть полезны запросы, являющиеся регулярными выражениями. [5] [2] [7] в поисковых системах, таких как Elasticsearch , [8] а также в таких базах данных, как PostgreSQL . [4]
Примеры
[ редактировать ]Рассмотрим строку «Алиса». Триграммами строки будут «ali», «lic» и «ice», без пробелов. [5] Поиск этой строки в базе данных с индексом на основе триграмм потребует выяснения того, какие объекты содержат как можно больше из трех триграмм.
В качестве конкретного примера использования поиска по триграммам для поиска запроса по регулярному выражению рассмотрим поиск строки ab[cd]e, где скобки означают, что третий символ в искомой строке может быть c или d. В этой ситуации можно запросить индекс объектов, имеющих две триграммы. abc и bce или две триграммы abd и bde. Таким образом, поиск этого запроса не потребует сопоставления строк , а можно просто запросить индекс напрямую, что на практике может быть быстрее. [2]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Хардарсон, Омар (1997). «Интерактивное кодирование экономической деятельности с использованием триграммного поиска в BLAISE III» (PDF) . Международная группа пользователей Blaise . Примечание. В этой статье рассматривается триграммный поиск как способ эффективного кодирования определенных видов экономических данных и обнаруживается, что этот метод особенно полезен, когда у пользователей системы мало контекста для структуры данных.
- ^ Jump up to: Перейти обратно: а б с Кокс, Расс (январь 2012 г.). «Сопоставление регулярных выражений с индексом триграммы или как работал поиск кода Google» .
- ^ Адамс, Элизабет; Мельцер, Арнольд (1 марта 1993 г.). «Триграммы как индексный элемент в полнотекстовом поиске: наблюдения и результаты экспериментов» . Материалы конференции ACM 1993 года по информатике - CSC '93 . стр. 433–439. дои : 10.1145/170791.170891 . ISBN 0897915585 . S2CID 16701550 .
- ^ Jump up to: Перейти обратно: а б с "F.33.pg_trgm" . Документация PostgreSQL . 12 мая 2022 г. Проверено 28 мая 2022 г.
- ^ Jump up to: Перейти обратно: а б с «Быстрый поиск с использованием текстовых индексов триграмм PostgreSQL» . ГитЛаб . 18 марта 2016 г. Проверено 28 мая 2022 г.
- ^ Зобель, Джастин; Моффат, Алистер; Сакс-Дэвис, Рон (1993). «Поиск в больших словарях частично определенных терминов с использованием сжатых инвертированных файлов» (PDF) . Конференция по очень большим базам данных (VLDB) . Примечание. В этой исследовательской работе не используется термин «поиск триграмм», но, похоже, это первый случай в литературе использования n-грамм в качестве индексов, и он цитируется в статье Расса Кокса как первый пример структуры обратный указатель на основе триграмм. В документе также приводятся успешные результаты использования этого стиля поиска.
- ^ «Большой Греп» . resources.sei.cmu.edu . Проверено 12 июня 2022 г. Также называется BigGrep. Использует n-граммы (не всегда 3),
- ^ «Токенизатор N-грамм | Руководство по Elasticsearch [8.2] | Elastic» . www.elastic.co . Проверено 28 мая 2022 г.