Интернет, компьютеры, софт и прочий Hi-Tech

SQLite: расширения FTS3 и FTS4

Содержание

1. Введение в FTS3 и FTS4
   1. Различия между FTS3 и FTS4
   2. Создание и удаление таблиц FTS
   3. Заполнение таблиц FTS
   4. Простейшие FTS-запросы
   5. Резюме
2. Компиляция и включение FTS3 и FTS4
3. Запросы с использованием полнотекстового индекса
   1. Набор операций в расширенном языке запросов
   2. Набор операций в стандартном языке запросов
4. Вспомогательные функции — Snippet, Offsets и Matchinfo
   1. Функция Offsets
   2. Функция Snippet
   3. Функция Matchinfo
5. Токенайзеры
   1. Кастомные токенайзеры (реализуемые пользователями)
6. Структуры данных
   1. Формат целых чисел переменного размера (varint)
   2. Формат сегмента B-дерева
      1. Листовые вершины сегмента B-дерева
      2. Внутренние узлы сегмента B-дерева
   3. Формат Doclist
7. Приложение A: Советы по разработке приложений поиска

4. Вспомогательные функции — Snippet, Offsets и Matchinfo

Модули FTS3 и FTS4 предоставляют три специальные скалярные функции SQL, которые могут быть полезны разработчикам систем полнотекстового поиска: "snippet", "offsets" и "matchinfo". Назначение функций "snippet" и "offsets" — дать пользователю возможность узнать местоположение запрашиваемых термов в найденных документах. Функция "matchinfo" предоставляет пользователю набор числовых значений, которые могут быть использованы для фильтрации и сортировки результатов по релевантности.

Первым аргументом всех трех этих специальных скалярных функций SQL должен быть скрытый столбец той таблицы FTS, к которой применяется функция. Скрытый столбец FTS генерируется автоматически для каждой таблицы FTS и имеет то же самое имя, что и сама таблица FTS. Пусть, например, дана таблица FTS по имени "mail". Тогда можно так обращаться к специальным функциям:

SELECT offsets(mail) FROM mail
    WHERE mail MATCH <выражение полнотекстового запроса>;
SELECT snippet(mail) FROM mail
    WHERE mail MATCH <выражение полнотекстового запроса>;
SELECT matchinfo(mail) FROM mail
    WHERE mail MATCH <выражение полнотекстового запроса>;

Эти три вспомогательных функции полезны только в тех запросах SELECT, которые используют полнотекстовый индекс таблицы FTS. Если обращаться к ним в запросе SELECT, который использует стратегию "запрос по rowid" или "линейное сканирование", то функции snippet и offsets будут возвращать пустые строки, а функция matchinfo вернет значение BLOB нулевой длины.

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

Каждая серия токенов в таблице FTS, которая совпадает с одной из искомых фраз запроса, называется "фразовым соответствием" со следующими оговорками:

1. Если искомая фраза является частью последовательности фраз, соединенных в запросе FTS оператором NEAR, то каждая такая фраза не должна пересекаться с другими искомыми фразами данной последовательности и должна удовлетворять условию NEAR.
2. Если поиск фразы из запроса FTS ограничен данными в каком-то отдельном столбце таблицы FTS, то во внимание принимаются только фразовые соответствия, находящиеся в этом столбце.

4.1. Функция Offsets

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

Следующий блок содержит примеры использования функции offsets:

CREATE VIRTUAL TABLE mail USING fts3(subject, body);
INSERT INTO mail
    VALUES('hello world', 'This message is a hello world message.');
INSERT INTO mail
    VALUES('urgent: serious', 'This mail is seen as a more serious mail');

-- Следующий запрос возвращает единственную запись (вставленную первой в
-- таблицу "mail"). Текст, выданный функцией offsets, будет следующий:
-- "0 0 6 5 1 0 24 5".
--
-- Первые четыре числа этого результата указывают на то, что столбец с индексом
-- 0 (subject) содержит терм с индексом 0 ("world") со смещением в 6 байт от
-- начала, а сам этот терм имеет длину в 5 байт. Следующие четыре числа
-- показывают, что столбец 1 (body) содержит терм 0 ("world") со смещением в 24
-- байта, и сам этот терм имеет длину в 5 байт.
SELECT offsets(mail) FROM mail WHERE mail MATCH 'world';

-- Следующий запрос также возвращает только одну первую строку из таблицы
-- "mail". В этом случае получим текст "1 0 5 7 1 0 30 7".
SELECT offsets(mail) FROM mail WHERE mail MATCH 'message';

-- Следующий запрос найдет вторую строку из таблицы "mail". Он выдаст текст
-- "1 0 28 7 1 1 36 4". Учитываться будут только те слова "serious" и "mail",
-- которые встречаются как часть фразы "serious mail". Другие вхождения
-- "serious" и "mail" игнорируются.
SELECT offsets(mail) FROM mail WHERE mail MATCH '"serious mail"';

4.2. Функция Snippet

Функция snippet используется для создания форматированных фрагментов текста документа, предназначенных для вывода результатов запроса. Функция "snippet" может принимать от одного до шести следующих аргументов:

Функция snippet сначала пытается найти фрагмент текста, содержащий |N| токенов внутри текущей строки, которая должна содержать хотя-бы одно вхождение для каждой искомой фразы. Здесь |N| — это абсолютная величина шестого аргумента функции snippet. Если текст в единственном столбце содержит менее чем |N| токенов, то выбирается всё значение столбца. Текстовые фрагменты не должны находиться в различных столбцах.

Если такой текстовый фрагмент может быть найден, он будет выдан со следующими изменениями:

• Если текстовый фрагмент начинается не с начала значения столбца, в его начало будет добавлен текст "троеточие".
• Если текстовый фрагмент не заканчивается с концом значения столбца, в его конец будет добавлен текст "троеточие".
• Перед каждым токеном в текстовом фрагменте, который является частью найденной фразы, будет вставлен текст "начало совпадения", а немедленно после этого токена будет вставлен текст "конец совпадения".

Если будет найдено более одного подходящего фрагмента, то предпочтение будет отдано тем фрагментам, которые содержат большее число "дополнительных" искомых фраз. Начало выбранного текстового фрагмента может быть перемещено на несколько токенов вперед или назад в попытке собрать все попавшие в него искомые фразы в середину фрагмента.

Если N имеет положительное значение, и несуществует фрагментов, которые содержат совпадения для всех искомых фраз, функция snippet попытается найти два фрагмента длиной приблизительно по N/2 токенов, которые вместе содержат хотя-бы по одному вхождению каждой искомой фразы. Если это не получается, осуществляется поиск трех фрагментов по N/3 токенов в каждом, затем — четырех фрагментов по N/4. Если нет четырех фрагментов, которые вместе содержали бы требуемые искомые фразы, то будут выбраны такие четыре фрагмента по N/4 токенов, которые обеспечат наилучшее покрытие искомых фраз.

Если N — отрицательное значение и единственный фрагмент, содержащий нужные фразовые совпадения, найти невозможно, функция snippet ищет два фрагмента по |N| токенов каждый, затем три, затем четыре. Иначе говоря, если указанное значение N является отрицательным, то при необходимости поиска более чем одного фрагмента размеры этих фрагментов не уменьшаются.

После нахождения M фрагментов, где M может принимать значения от двух до четырех, как описано в предыдущем абзаце, они соединяются вместе через "троеточие" в том порядке, в каком находились в документе. После выполнения перечисленных выше преобразований, результирующий текст возвращается функцией.

-- Замечание: в примерах этого блока символы новой строки и пробелы,
-- входящие в документ, вставляемый в таблицу FTS, ожидаются, соответственно, в
-- результатах, которые описываются в SQL-комментариях. Однако в целях
-- читабельности примеров эти результаты опубликованы не так, как они выглядят
-- при выводе реальных команд SQLite.

-- Создаем и заполняем таблицу FTS.
CREATE VIRTUAL TABLE text USING fts4();
INSERT INTO text VALUES('
  During 30 Nov-1 Dec, 2-3oC drops. Cool in the upper portion, minimum
  temperature 14-16oC and cool elsewhere, minimum temperature 17-20oC. Cold to
  very cold on mountaintops, minimum temperature 6-12oC. Northeasterly winds
  15-30 km/hr. After that, temperature increases. Northeasterly winds 15-30
  km/hr.
');

-- Следующий запрос выведет такое текстовое значение:
--
-- "<b>...</b>cool elsewhere, minimum temperature 17-20oC.
-- <b>Cold</b> to very <b>cold</b> on mountaintops,
-- minimum temperature 6<b>...</b>".
--
SELECT snippet(text) FROM text WHERE text MATCH 'cold';

-- Следующий запрос выведет такое текстовое значение:
--
-- "...the upper portion, [minimum] [temperature] 14-16oC and cool elsewhere,
-- [minimum] [temperature] 17-20oC. Cold..."
--
SELECT snippet(text, '[', ']', '...') FROM text WHERE text MATCH '"min* tem*"'

4.3. Функция Matchinfo

Функция matchinfo возвращает значение типа BLOB. Если она вызывается в запросе, который не использует полнотекстовый индекс ("запрос по rowid" или "линейное сканирование"), то возвращаемый BLOB будет нулевой длины. В противном случае, этот BLOB состоит из нуля или более 32-битных беззнаковых целых чисел в машинном порядке байтов. Точное число этих целочисленных значений в возвращаемом массиве зависит как от запроса, так и от второго аргумента функции matchinfo (если он есть).

При вызове функция matchinfo получает один или два аргумента. Как и во всех вспомогательных функциях, первым аргументом должен быть скрытый столбец FTS. Второй аргумент, если он указан, должен быть текстовым значением, состоящим только из символов 'p', 'c', 'n', 'a', 'l', 's' и 'x'. Если второй аргумент не задан, то считается, что задана строка "pcx". Второй аргумент интерпретируется как "строка формата", описываемая ниже.

Символы в строке формата для matchinfo обрабатываются слева направо. Каждый символ в строке формата отвечает за одно или более 32-битных беззнаковых целых, добавляемых в возвращаемый массив. Столбец "Значения" следующей таблицы содержит число этих целочисленных значений, добавляемых в вывод для каждого символа строки формата. В приведённых ниже формулах величина cols — это число столбцов таблицы FTS, а phrases — число искомых фраз в запросе.

          hits_this_row  = array[3 * (c + p*cols) + 0]
          hits_all_rows  = array[3 * (c + p*cols) + 1]
          docs_with_hits = array[3 * (c + p*cols) + 2]

Например:

-- Создаем и заполняем таблицу FTS4 с двумя столбцами:
CREATE VIRTUAL TABLE t1 USING fts4(a, b);
INSERT INTO t1 VALUES('transaction default models default', 'Non transaction reads');
INSERT INTO t1 VALUES('the default transaction', 'these semantics present');
INSERT INTO t1 VALUES('single request', 'default data');

-- В следующем запросе строка формата не указывается. Поэтому используется
-- умолчальная "pcx". Поэтому результатом запроса будет единственная строка,
-- содержащая бинарные данные объемом в 80 байт (20 32-битных целых - 1 для "p",
-- 1 для "c" и 3*2*3 для "x"). Если каждый блок из 4 байтов интерпретировать как
-- беззнаковое целое в машинном порядке байт, то получим следующую
-- последовательность:
--
--     3 2  1 3 2  0 1 1  1 2 2  0 1 1  0 0 0  1 1 1
--
-- Строка результата соответствует второй вставленной в таблицу t1 записи.
-- Первые два числа в последовательности показывают, что запрос содержит три
-- фразы и что поиск в таблице осуществляется по двум столбцам. Следующий блок
-- из трех целых чисел сообщает сведения о столбце 0 (в данном случае "a") и
-- фразе 0 (в данном случае "default"): найденная строка содержит 1 вхождение
-- "default" в столбце 0; всего в столбце 0 по всей таблице слово "default"
-- встречается 3 раза; слово присутствует в 2 записях.
--
-- Следующая тройка чисел (0 1 1) показывает число вхождений "default" в столбец
-- 1 (0 для данной строки, 1 для всех строк, 1 строка с вхождением).
--
SELECT matchinfo(t1) FROM t1 WHERE t1 MATCH 'default transaction "these semantics"';

-- Строка формата для следующего запроса - "nl". Поэтому возвращаемый массив
-- содержит 3 целочисленных значения - 1 для "n" и 2 для "l". Запрос находит две
-- строки (первые две строки, вставленные в таблицу). Выдача будет следующей:
--
--     3  1 1
--     3  2 0
--
-- Первое число в массиве, выданном matchinfo, одинаково для обеих строк и равно
-- 3 (число строк в таблице). Следующие два числа - это длины (в словах) самых
-- длинных подпоследовательностей фраз, найденных в соответствующих столбцах.
--
SELECT matchinfo(t1, 'nl') FROM t1 WHERE t1 MATCH 'default transaction';

Функция matchinfo отрабатывает значительно быстрее чем функции snippet и offsets, поскольку реализация обеих этих функций требует получение документов с диска и их анализ, тогда как все данные, необходимые для "matchinfo", доступны как части полнотекстового индекса, который и так необходим для выполнения самого полнотекстового запроса. Это означает, что из следующих двух запросов первый должен выполниться значительно быстрее, чем второй:

SELECT docid, matchinfo(tbl) FROM tbl WHERE tbl MATCH <query expression>;
SELECT docid, offsets(tbl) FROM tbl WHERE tbl MATCH <query expression>;

Функция matchinfo предоставляет всю информацию, требуемую для вычисления статистической релевантности типа "мешок-слов" ("bag-of-words") по формулам Okapi BM25/BM25F, которая может использоваться для сортировки результатов в приложении полнотекстового поиска. В приложении A к этому документу ("Советы по разработке приложений поиска"), приведен пример эффективного использования функции matchinfo().

Перевод Дмитрия Скоробогатова, 02.06.2011
Оригинальный текст может быть найден по адресу http://www.sqlite.org/fts3.html

Предыдущие публикации:

Последнее редактирование: 2011-06-02 20:17:09

Метки материала: функции, snippet, offsets, matchinfo, sqlite, fts3, fts4, базы данных, db, sql, программирование

Оставьте, пожалуйста, свой комментарий к публикации

Представиться как

Антибот:

Просьба не постить мусор. Если вы хотите потестить xBB, воспользуйтесь кнопкой предварительного просмотра на панели инструментов xBBEditor-а.