mobileSimbirSoft 25 дек 2020 в 15:24

Полнотекстовый поиск FTS3, FTS4 и FTS5 в Android

10 мин

7.3K

Блог компании SimbirSoftРазработка под Android*SQLite*Kotlin*

Полнотекстовый поиск необходим в приложениях для того, чтобы быстро находить совпадения в большом объеме данных. Такая возможность удобна, например, для поиска товаров, фильмов, рецептов, научных статей, а также фрагментов текста в электронных книгах. Хотя зачастую поиск реализуют на сервере, иногда бывает необходимо работать в оффлайне, повысить отзывчивость мобильного приложения, избежав задержек при взаимодействии с сервером. В таких случаях используют полнотекстовый поиск — Full-Text Search.

В этой статье рассмотрим особенности полнотекстового поиска в Android с использованием FTS3, FTS4 и FTS5. Статья будет наиболее полезна для читателей, знакомых с Android и SQLite.

Ниже приведен пример поиска по SMS-сообщениям. Совпадения выделены желтым цветом, а текст сообщения обрезан до одной строки:

Для полнотекстового поиска в Android можно использовать виртуальные таблицы FTS3, FTS4 или FTS5 базы данных SQlite (БД Realm не поддерживает FTS). Виртуальные таблицы отличаются от обычных, т.е. реальных, тем, что реальные получают данные из файла БД, а виртуальные — выполняют программный код, который реализует логику для получения данных: например, информация может подтягиваться из разных источников.

Для виртуальной таблицы FTS в БД создается от трех до пяти вспомогательных реальных таблиц %_content, %_segdir, %_segments, %_stat и %_docsize (в версии FTS5: %_data, %_idx, %_config, %_content, %_docsize), где вместо % — название FTS-таблицы. Их еще называют “теневыми таблицами”. Они формируют структуру данных, основанную на B-деревьях и содержащую индексы, благодаря которым и осуществляется быстрый полнотекстовый поиск.

Но при этом FTS-таблицы имеют ограничения:

Таблица может содержать только текстовые данные, и у каждой записи должен быть уникальный целочисленный идентификатор с названием “rowid” (или alias “docid”). Возможно, для одной сущности вам придется завести две таблицы — одну, обычную, со всеми необходимыми данными и вторую, FTS-таблицу исключительно с теми столбцами, по которым будет проводиться поиск. При таком подходе вы, возможно, захотите учитывать остальные значения из реальной таблицы при поиске. Для этого можно использовать запрос с join, например:
```
SELECT snippet(my_fts_table) FROM my_real_table JOIN my_fts_table ON my_real_table.id=my_fts_table.rowid WHERE my_fts_table.text MATCH :search ORDER BY date
```
Как и для всех виртуальных таблиц, для FTS-таблиц нельзя добавлять триггеры и менять столбцы командой ALTER TABLE. Но можно использовать ALTER TABLE для переименования таблицы.

SQLite поддерживает следующие типы FTS-таблиц: FTS3, FTS4 и FTS5. Тип таблицы указывается при ее создании, например:

CREATE VIRTUAL TABLE email USING fts5(sender, title, body)

FTS3 появился еще в 2007 году в SQLite версии 3.5, FTS4 — в SQLite 3.7 (2010 г.), а FTS5 — в SQLite 3.9 (2015 г.). Первые версии FTS1 и FTS2 считаются устаревшими и не рекомендуются к использованию.

Наглядный пример полнотекстового поиска

Для демонстрации возможностей полнотекстового поиска мы используем текст романа «Петр Первый» А.Н.Толстого. Текст книги добавлен в таблицы построчно.

Вариант “No FTS” используется для обычной таблицы без FTS. Поиск по обычной таблице выполняется запросом с оператором LIKE, например, мы можем написать такую аннотацию Room:

@Query("SELECT * FROM text_table WHERE text LIKE :pattern || '%'")

Для полнотекстового поиска используется оператор MATCH:

@Query("SELECT snippet(text_table_fts4) AS text FROM text_table_fts4 WHERE text MATCH :pattern || '*')

Символы % и * после параметра pattern нужны для поиска подстроки. Для поиска точного совпадения нужно их убрать.

Функция snippet() возвращает часть текста, в которой есть совпадения, и выделяет слова (токены), которые совпали с токенами в запросе. Например, SELECT snippet(text, ‘[‘, ‘]’, ‘...’) FROM text WHERE text MATCH ‘“min* tem*”’выдаст результат вида "...the upper portion, [minimum] [temperature] 14-16oC and cool elsewhere, [minimum] [temperature] 17-20oC. Cold...".

FTS3 и FTS4

Для начала рассмотрим основные отличия FTS3 от FTS4:

Отличия в скорости выполнения запросов – в пользу FTS4. В нашем случае запросы к таблице FTS4 работают быстрее в 2-3 раза.

Отметим также, что для повышения скорости поиска есть специальный запрос optimize, который сливает несколько B-деревьев в одно:
```
@Query("INSERT INTO text_table_fts3 VALUES('optimize')")
```
Его можно выполнить после заполнения FTS-таблицы данными.
Заполнение таблиц происходит практически с одинаковой скоростью. В нашем случае – 17.669 сек для FTS3 и 17.675 сек для FTS4. Учитывайте, что заполнение FTS-таблиц занимает больше времени, чем для обычных таблиц.
Отличия в объеме занимаемого пространства на жестком диске незначительные, в пользу FTS3. В среднем таблицы для FTS4 занимают на 2% больше, согласно документации sqlite.org.
FTS4 обладает более широким функционалом. Например, у него есть функция matchinfo(), позволяющая определить, сколько было найдено совпадающих фраз, в скольких столбцах и в каком количестве. Эту информацию можно использовать для ранжирования результатов поиска. Еще пример: в FTS4 при создании таблиц можно пометить столбцы параметром notindexed, и тогда данные в соответствующих столбцах не будут индексированы и не будут участвовать в поиске. Подробнее об отличиях функционала FTS3 и FTS4 здесь.
FTS4 может быть таблицей с внешним контентом, то есть использовать данные из другой таблицы. Пример создания таблицы с внешним контентом на основе реальной таблицы t2:
```
CREATE TABLE t2(id INTEGER PRIMARY KEY, a, b, c);
```
```
CREATE VIRTUAL TABLE t3 USING fts4(content="t2", a, c);
```
В Room, который поддерживает FTS3 и FTS4, можно создать таблицу с внешним контентом, если прописать параметр contentEntity в аннотации @Fts4:
```
@Entity(tableName = "text_table_fts4")
@Fts4(contentEntity = TextLine::class)
class TextLineFts4 (override val text: String): TextContainer
```
Room создает триггеры, срабатывающие при изменении данных в исходной таблице. Если при миграции БД в исходную таблицу будут внесены изменения (например, добавлен новый столбец), то триггеры и FTS-таблица будут удалены и созданы заново.
Room не поддерживает параметр contentEntity для FTS3, и в связи с этим есть еще одно небольшое неудобство: Room обязует использовать первичный ключ “rowid”, не воспринимает alias “docid”, а также в SELECT-запросах обязательно должен присутствовать “rowid”:
```
@Query("SELECT *, rowid FROM text_table_fts3 LIMIT :limit")
```
Если не написать rowid в запросе, то Kapt выдает ошибку на этапе сборки:
The single primary key field in an FTS entity must either be named 'rowid' or must be annotated with @ColumnInfo(name = «rowid»)
FTS4 поддерживается начиная с Android API 11 (SQLite 3.7)

При выборе между FTS3 и FTS4 предпочтительно использовать FTS4. При этом FTS3 может подойти вам в том случае, если необходимо поддерживать старые версии Android и SQLite. Если критичен размер таблицы, то при создании таблицы FTS4 можно задать параметр matchinfo=fts3, что позволит свести ее размер к размеру аналогичной таблицы FTS3. Однако, при этом пропадут некоторые возможности функции matchinfo().

FTS5

Другой вопрос – выбор между FTS4 и FTS5. Дело в том, что Android предоставляет SQLite с отключенным модулем FTS5. Мы можем подключить в свой проект другую версию SQLite с помощью библиотек, но тогда, скорее всего, придется отказаться от использования ORM. С другой стороны, у FTS5 есть много полезных функций. Рассмотрим эти аспекты более детально.

Подключение FTS5 с помощью библиотеки

Будем использовать библиотеку Requery, она содержит сборку последней версии SQLite с подключенным модулем FTS5. В качестве альтернативы, можно сделать свою сборку с помощью BrodyBits Android SQLite Native Driver с флагом -DSQLITE_ENABLE_FTS5.
Для начала добавляем зависимость в gradle:

dependencies {
    implementation 'io.requery:sqlite-android:3.33.0'
}

Затем мы могли бы добавить RequerySQLiteOpenHelperFactory в билдер для создания RoomDatabase:

val instance = Room.databaseBuilder(context.applicationContext,
   TextRoomDatabase::class.java, "text_database")
   .openHelperFactory(RequerySQLiteOpenHelperFactory())
   .build()

К сожалению, Room не предоставляет аннотаций или другого удобного интерфейса для работы с FTS5. Поэтому напишем свой SQLiteOpenHelper. При этом не забываем, что импортировать надо библиотечный SQLiteOpenHelper и SQLiteDatabase:

import io.requery.android.database.sqlite.SQLiteDatabase
import io.requery.android.database.sqlite.SQLiteOpenHelper

В onCreate создаем таблицу FTS5:

db.execSQL("CREATE VIRTUAL TABLE IF NOT EXISTS $TABLE USING FTS5( $TEXT )")

Обратите внимание, что в CREATE у столбцов не нужно указывать тип. Также не нужно задавать первичный ключ, столбец rowid создается неявно.

Функция поиска выглядит следующим образом:

fun find(pattern: String, limit: Int): Flow<List<TextLineFts5>> {
   val query = "SELECT snippet($TABLE, 0, '<b>', '</b>', '<b>...</b>', 14 ) AS $TEXT FROM $TABLE WHERE text MATCH ? || '*' LIMIT ?"
   return flow {
       db.query(query, arrayOf(pattern, limit)).use { cursor ->
           val result = ArrayList<TextLineFts5>(cursor.count)
           while (cursor.moveToNext()) {
               val text = cursor.getString(0)
               result.add( TextLineFts5(text) )
           }
           emit(result)
       }
   }
}

Возвращаем Coroutine Flow, чтобы можно было обрабатывать результат по аналогии с Room.

В функции snippet в FTS5 все шесть параметров стали обязательными, тогда как в FTS3/4 можно просто написать snippet(table_name). Последний аргумент со значением 14 – это максимальное число токенов в возвращаемом отрывке текста. Этот параметр может принимать значения не больше 64.

Полный текст реализации SQLiteOpenHelper можно посмотреть здесь

package com.simbirsoft.ftsstudyproject.data

import android.content.ContentValues
import android.content.Context
import com.simbirsoft.ftsstudyproject.data.entity.TextLineFts5
import io.requery.android.database.sqlite.SQLiteDatabase
import io.requery.android.database.sqlite.SQLiteOpenHelper
import kotlinx.coroutines.CoroutineScope
import kotlinx.coroutines.flow.Flow
import kotlinx.coroutines.flow.collect
import kotlinx.coroutines.flow.flow
import kotlinx.coroutines.launch

class Fts5DB(private val ctx: Context, private val scope: CoroutineScope, private val assets: AssetsDataProvider) {

   private val dbHelper: SQLiteOpenHelper by lazy {

       object: SQLiteOpenHelper(ctx, NAME, null, VERSION){

           override fun onCreate(db: SQLiteDatabase?) {
               db?.execSQL("CREATE VIRTUAL TABLE IF NOT EXISTS `$TABLE` USING FTS5(`$TEXT`)")
               scope.launch{
                   populate()
               }
           }

           override fun onUpgrade(db: SQLiteDatabase?, oldVersion: Int, newVersion: Int) {

           }

           private suspend fun populate(){
               deleteAll()
               //Текст книги берем из assets
               assets.readFileFromAssets("PeterI.txt").collect {
                   add(TextLineFts5(it))
               }
               optimize()
           }

       }
   }

   private val db: SQLiteDatabase by lazy { dbHelper.writableDatabase }

   //не забываем закрывать соединение с БД
   fun close(){
       dbHelper.close()
   }

   fun find(pattern: String, limit: Int): Flow<List<TextLineFts5>> {
       val query = "SELECT snippet($TABLE, 0, '<b>', '</b>', '<b>...</b>', 14 ) AS $TEXT FROM $TABLE WHERE text MATCH ? || '*' LIMIT ?"
       return flow {
           db.query(query, arrayOf(pattern, limit)).use { cursor ->
               val result = ArrayList<TextLineFts5>(cursor.count)
               while (cursor.moveToNext()) {
                   val text = cursor.getString(0)
                   result.add( TextLineFts5(text) )
               }
               emit(result)
           }
       }
   }

   fun add(textLine: TextLineFts5) {
       val cv = ContentValues()
       cv.put(TEXT, textLine.text)
       db.insert(TABLE, null, cv)
   }

   fun deleteAll(){
       db.delete(TABLE, null, null)
   }

   private fun optimize() {
       db.query("INSERT INTO $TABLE VALUES('optimize')")
   }

   companion object {
       private val NAME = "fts5_db"
       private val VERSION = 1
       private val TABLE = "text_table_fts5"
       private val TEXT = "text"
   }
}

Дополнительные возможности в FTS5

Теперь, когда мы подключили FTS5 в проект, можем использовать новые полезные функции, например:

ORDER BY rank. Таблица FTS5 включает в себя скрытый столбец rank, в котором содержится вычисленное значение функции bm25(). Его можно использовать для ранжирования результатов:
```
"SELECT snippet($TABLE, 0, '', '', '...', 14 ) AS $TEXT FROM $TABLE WHERE text MATCH '$pattern*' ORDER BY rank LIMIT $limit"
```
Теперь в начале будут идти строки, в которых больше концентрация найденных совпадений:
Символ ‘^∧’ позволяет искать совпадение по началу строки. Результаты MATCH ‘^∧двор*’:
Булевские операторы AND, OR, NOT. Например, MATCH ‘Петр AND Лефорт NOT Меньшиков’ выдаст результаты с токенами “Петр”, “Лефорт”, не содержащие токен “Меньшиков”.
Оператор NEAR ищет тексты, которые содержат несколько фраз, находящихся близко друг к другу. У NEAR два аргумента: первый – поисковые фразы через пробел, второй, необязательный – число токенов, которое может быть между первой и последней поисковой фразой (по умолчанию 10).

Для поиска NEAR (голова сердце, 9) результат будет пустой.
Фильтр по столбцам. Мы можем определять, по каким столбцам осуществлять поиск.
MATCH ‘{col1 col2}: query’ ищет “query” по столбцам col1 и col2,
MATCH ‘- col2: query’ ищет по всем столбцам кроме col2
Функция highlight() аналогична snippet(), только она возвращает текст целиком. У этой функции 4 аргумента:

1 – название FTS-таблицы
2 – порядковый номер столбца, по которому искать совпадения (нумерация с 0)
3 – текст, вставляемый перед найденным совпадением
4 – текст, вставляемый после найденного совпадения

Обратите внимание, что в FTS5 нельзя просто подставлять в MATCH любую строку. Если она будет содержать специальные символы, например, ‘?’ или ‘*’, то это будет считаться синтаксической ошибкой и приведет к SQLiteException. Чтобы избежать этого, заключаем строку в двойные кавычки, а если строка сама содержит двойные кавычки, дублируем их:

"\"${pattern.replace("\"","\"\"")}\""

Отличия в производительности

FTS5 выполняет сложные поисковые запросы быстрее, чем FTS3/4, за счет того, что индексы всех нахождений токена (instance list) хранятся не одной большой записью, как в FTS3/4, а по частям. Если в запросе содержится несколько токенов, то часто результат может быть получен после обработки лишь некоторой части instance list, в то время как FTS3/4 просматривает instance list целиком. Также при подгрузке instance list по частям расходуется меньше оперативной памяти.

С другой стороны, заполнение таблиц FTS5 занимает значительно больше времени, чем FTS3/4. В нашем примере на это ушло 49.549 сек. для FTS5 по сравнению с 17.675 сек. для FTS4.

Еще одно замечание относительно размера таблиц. FTS5 хранит данные о количестве токенов в текстах в отдельной таблице. Эта информация используется функцией для ранжирования bm25(). Чтобы сократить объем занимаемой памяти, можно воспользоваться опцией columnsize = 0

CREATE VIRTUAL TABLE ft USING fts5(a, b, c, columnsize=0);

Заключение

Как мы видим, в Android можно без особых затруднений использовать FTS5. Подключайте этот вариант, если хотите расширить возможности полнотекстового поиска или если для ваших целей недостаточно скорости FTS4. Учитывайте, что синтаксис FTS5 немного отличается от FTS3/4, и если в вашем проекте уже есть реализация FTS, то возможно, потребуется внести изменения в запросы.

Для рядового полнотекстового поиска возможностей FTS4 вполне достаточно, и в этом случае вам, вероятно, будет удобнее работать с FTS4, так как его поддерживает Room. FTS3 не рекомендуется использовать, если нет необходимости поддерживать старую версию SQLite.

Ссылки

Теги:

Хабы: