Интернет, компьютеры, софт и прочий 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: Советы по разработке приложений поиска

Приложение A: Советы по разработке приложений поиска

Изначально FTS был разработан для поддержки логического полнотекстового поиска — запросы должны находить набор документов, которые удовлетворяют заданным критериям. Однако многие (большинство?) приложений поиска требуют ранжирования этих результатов в порядке "релевантности", которая понимается как вероятность того, что пользователь заинтересуется конкретным документом из найденного набора документов. Когда пользователь использует поисковую систему для поиска во всемирной сети, он ожидает, что самые полезные (то-есть "релевантные") документы будут выданы ему на первой странице результатов, и что каждая последующая страница содержит все менее релевантные результаты. Научить машину определять релевантность документов на основе пользовательского запроса — это сложная проблема, которой в настоящее время посвящены многочисленные исследования.

Один из самых простых способов — это подсчёт числа нужных пользователю термов, присутствующих в результирующем документе. Документы, которые содержат больше термов, должны считаться более релевантными по сравнению с теми, которые содержат мало термов. В приложении FTS число вхождений термов для каждого результата может быть определено подсчётом целых чисел в строке, возвращаемой функцией offsets. Следующий пример демонстрирует запрос, который может быть использован для получения десяти наиболее релевантных результатов для введенного пользователем запроса:

-- Этот пример (и все другие в этом разделе) предполагает следующую
-- схему:
CREATE VIRTUAL TABLE documents USING fts3(title, content);

-- Будем считать, что приложение предоставляет пользовательскую функцию по
-- имени "countintegers", которая возвращает число разделенных пробелами целых
-- чисел, содержащихся в аргументе. Тогда следующий запрос может быть
-- использован для того, чтобы получить заголовки 10 документов, которые
-- содержат наибольшее число термов из запроса пользователя. Остается надеяться,
-- что эти 10 документов окажутся более или менее релевантными с точки зрения
-- пользователя.
SELECT title FROM documents 
  WHERE documents MATCH <query>
  ORDER BY countintegers(offsets(document)) DESC
  LIMIT 10 OFFSET 0

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

-- Если приложение предоставляет SQLite пользовательскую функцию по имени
-- "rank", которая интерпретирует бинарные данные, возвращаемые matchinfo, и
-- переводит их в числовую релевантность, то следующий SQL может быть
-- использован для получения заголовков 10 наиболее релевантных
-- пользовательскому запросу документов из всего набора документов.
SELECT title FROM documents 
  WHERE documents MATCH <query>
  ORDER BY rank(matchinfo(document)) DESC
  LIMIT 10 OFFSET 0

SQL-запрос в этом примере нагружает процессор меньше, чем первый пример в этом разделе. Однако оставляет нерешённой другую неочевидную проблему с производительностью. Выполняя этот запрос SQLite извлекает значения столбца "title" и данные matchinfo для каждой строки, соответствующей запросу пользователя, затем сортирует их выдает 10 результатов. Поскольку работает интерфейс виртуальных таблиц SQLite, получение значения столбца "title" влечет за собой загрузку сохранённых на диске записей целиком включая поле "content", которое может быть очень большим. Таким образом, если пользовательскому запросу соответствует несколько тысяч документов, то множество мегабайт данных из "title" и "content" могут быть загружены с диска в оперативную память даже при том, что большая их часть никак не будет использована.

Запрос SQL в следующем блоке примеров является одним из решений этой проблемы. В SQLite, когда используемый в объединении подзапрос использует выражение LIMIT, выдача этого подзапроса вычисляется и сохраняется во временной таблице перед выполнением основного запроса. Это означает, что для каждой строки пользовательского запроса SQLite будет загружать в память только docid и данные matchinfo. Определив значения docid, соответствующие десяти наиболее релевантным документам, затем будут загружены только заголовки и содержимое этих 10 документов. Поскольку значения matchinfo с docid составляют незначительную часть полнотекстового индекса, такой прием значительно уменьшает объем данных, загружаемых из базы в память.

SELECT title FROM documents JOIN (
    SELECT docid, rank(matchinfo(document)) AS rank
    FROM documents
    WHERE documents MATCH <query>
    ORDER BY rank DESC
    LIMIT 10 OFFSET 0
) AS ranktable USING(docid)
ORDER BY ranktable.rank DESC

В следующем блоке SQL-кода приводятся запросы, которые решают две другие проблемы, с которыми можно столкнуться при разработке поисковых приложений с использованием FTS:

1. Функция snippet не может быть использована в приведённом выше запросе, поскольку основной запрос не содержит выражения "WHERE ... MATCH", а функция snippet не может работать без него. Одним из решений является дублирование в основном запросе выражения WHERE, использованного в подзапросе. Обычно, это не приводит к большому перерасходованию вычислительных ресурсов.

2. Релевантность документа может зависеть от каких-то других данных, кроме тех, которые выдаются функцией matchinfo. Например, каждому документу в базе данных может быть сопоставлен статический "вес", основанный на факторах, не имеющих отношения к его содержанию (источник, автор, возраст, число ссылок и т.п.). Эти значения могут сохраняться приложением в отдельной таблице, которая может объединяться с таблицей документов в подзапросе, чтобы можно было передать значения в функцию rank.

Эта версия запроса очень похожа на ту, которая используется в приложении поиска документации на sqlite.org.

-- В этой таблице хранятся статические "веса", назначаемые каждому документу
-- в FTS-таблице "documents". Для каждой записи в таблице документов существует
-- соответствующая запись в данной таблице с тем же самым значением docid.
CREATE TABLE documents_data(docid INTEGER PRIMARY KEY, weight);

-- Этот запрос похож на тот, что в блоке выше, за исключением следующего:
--
--   1. Он возвращает "сниппет" текста для отображения вместе с заголовком
--      документа. Чтобы использовать для этого функцию snippet, конструкция
--      "WHERE ... MATCH ..." дублируется в подзапросе и в основном запросе.
--
--   2. Во вложенном запросе объединяются таблицы documents и document_data.
--      Последняя хранит статические веса всех документов, которые используются
--      данной реализацией функции rank.
SELECT title, snippet(documents) FROM documents JOIN (
    SELECT docid, rank(matchinfo(document), documents_data.weight) AS rank
    FROM documents JOIN documents_data USING(docid)
    WHERE documents MATCH <query>
    ORDER BY rank DESC 
    LIMIT 10 OFFSET 0
) AS ranktable USING(docid)
WHERE documents MATCH <query>
ORDER BY ranktable.rank DESC

Все вышеприведённые примеры запросов выдают десять результатов, наиболее релевантных запросу. Модифицировав значения в выражениях OFFSET и LIMIT можно заставить запрос выдавать, например, следующие десять наиболее релевантных результатов. Это можно использовать для того, чтобы в поисковом приложении выдавать вторую и следующие страницы результатов поиска.

Следующий блок содержит примерную реализацию функции rank (на C), которая использует данные, возвращаемые matchinfo. Вместо единственного "веса" она получает отдельные "веса", соответствующие каждому столбцу каждого документа. Эта функция может быть зарегистрирована в SQLite, как и любая другая пользовательская функция, с помощью sqlite3_create_function.

/*
** Пример пользовательской функции SQLite, использующей matchinfo() для
** вычисления релевантности записей в таблице FTS. Функция возвращает оценку
** релевантности (действительное число, равное или большее нуля). Большее
** значение оценки соответствует большей релевантности документа.
**
** Общая релевантность возвращается как сумма релевантностей значений отдельных
** столбцов таблицы FTS. Релевантность значения в столбце является суммой
** релевантностей этого значения для каждой отдельной фразы FTS-запроса, которые
** вычисляются следующим образом:
**
**   (<число вхождений>/<общее число вхождений>)*<вес столбца>
**
** где <число вхождений> - это число, сколько раз встречается фраза в
** значении столбца текущей строки; <общее число вхождений> - это число,
** сколько раз встречается фраза в значениях столбца для всех строк в таблице
** FTS; <вес столбца> - это весовой фактор, указываемый для каждого
** столбца при вызове функции (смотрите ниже).
**
** Первый аргумент этой функции должен быть значением, которое возвращает
** FTS-функция matchinfo(). После этого следует задать по одному числовому
** аргументу на каждый столбец таблицы FTS, в которых указать относительные веса
** соответствующих столбцов. Пример:
**
**     CREATE VIRTUAL TABLE documents USING fts3(title, content)
**
** Следующий запрос выдаст docid-ы документов, которые соответствуют
** полнотекстовому запросу <query>, отсортировав по убыванию
** релевантности. При вычислении релевантности слова запроса, содержащиеся в
** столбце 'title', добавляют документу вдвое больше веса, чем слова,
** содержащиеся в столбце 'content'.
**
**     SELECT docid FROM documents
**     WHERE documents MATCH <query>
**     ORDER BY rank(matchinfo(documents), 1.0, 0.5) DESC
*/
static void rankfunc(sqlite3_context *pCtx, int nVal, sqlite3_value **apVal){
  int *aMatchinfo;             /* Значение, возвращаемое matchinfo() */
  int nCol;                    /* Число столбцов в таблице */
  int nPhrase;                 /* Число фраз в запросе */
  int iPhrase;                 /* Текущая фраза */
  double score = 0.0;          /* Возвращаемое значение */

  assert( sizeof(int)==4 );

  /* Проверяем корректность числа аргументов, переданных в данную функцию.
  ** Если оно неверно, переходим к метке wrong_number_args. Задаем aMatchinfo
  ** как массив беззнаковых целых чисел, возвращаемый FTS-функцией matchinfo.
  ** Задаем nPhrase как число фраз, переданных пользователем в полнотекстовом
  ** запросе, а nCol задаем как число столбцов в таблице.
  */
  if( nVal<1 ) goto wrong_number_args;
  aMatchinfo = (unsigned int *)sqlite3_value_blob(apVal[0]);
  nPhrase = aMatchinfo[0];
  nCol = aMatchinfo[1];
  if( nVal!=(1+nCol) ) goto wrong_number_args;

  /* Итерируем по всем фразам пользовательского запроса. */
  for(iPhrase=0; iPhrase<nPhrase; iPhrase++){
    int iCol;                     /* Текущий столбец */

  /* Новая итерация по каждому столбцу из пользовательского запроса. Для
  ** каждого столбца оценка релевантности инкрементируется на следующее
  ** значение:
  **
  ** (<число вхождений>/<общее число вхождений>)*<вес столбца>
  **
  ** aPhraseinfo[] позиционируется на начало нужных данных во фразе iPhrase.
  ** Таким образом, число вхождений и общее число вхождений могут быть найдены
  ** для каждого столбца как aPhraseinfo[iCol*3] и aPhraseinfo[iCol*3+1],
  ** соответственно.
  */
    int *aPhraseinfo = &aMatchinfo[2 + iPhrase*nCol*3];
    for(iCol=0; iCol<nCol; iCol++){
      int nHitCount = aPhraseinfo[3*iCol];
      int nGlobalHitCount = aPhraseinfo[3*iCol+1];
      double weight = sqlite3_value_double(apVal[iCol+1]);
      if( nHitCount>0 ){
        score += ((double)nHitCount / (double)nGlobalHitCount) * weight;
      }
    }
  }

  sqlite3_result_double(pCtx, score);
  return;

  /*
  ** Переходим сюда, если в функцию передано неверное количество аргументов.
  */
wrong_number_args:
  sqlite3_result_error(pCtx, "wrong number of arguments to function rank()", -1);
}

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

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

Последнее редактирование: 2011-06-04 09:34:16

Метки материала: sqlite, fts3, fts4, базы данных, программирование, разработка по, db, sql, алгоритмы поисковых систем

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

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

Антибот:

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