Полнотекстовый поиск в Android

В мобильных приложениях очень востребована функция поиска. И если в небольших продуктах ею можно пренебречь, то в приложениях, которые предоставляют доступ к большому количеству информации, без поиска не обойтись. Сегодня я расскажу, как правильно реализовать эту функцию в программах под Android.

Подходы к реализации поиска в мобильном приложении

1. Поиск как фильтр данных
   
   Обычно это выглядит как строка поиска над каким-нибудь списком. То есть мы просто фильтруем уже готовые данные.
2. Серверный поиск
   
   В этом случае мы отдаём всю реализацию на откуп серверу, а приложение выступает в роли тонкого клиента, от которого требуется лишь показать данные в нужном виде.
3. Комплексный поиск
   
   
   • приложение содержит в себе большое количество данных разного типа;
   • приложение работает оффлайн;
   • поиск нужен как единая точка доступа к разделам/контенту приложения.

В последнем случае на помощь приходит встроенный в SQLite полнотекстовый поиск (Full-text search). С его помощью можно очень быстро находить совпадения в большом объёме информации, что позволяет нам делать несколько запросов в разные таблицы без снижения производительности.

Рассмотрим реализацию такого поиска на конкретном примере.

Подготовка данных

Допустим, нам необходимо реализовать приложение, которое показывает список фильмов с сайта themoviedb.org. Для упрощения (чтобы не ходить в сеть), возьмём список фильмов и сформируем из него JSON-файл, положим его в assets и локально будем наполнять нашу базу данных.

Пример структуры JSON-файла:

[
  {
    "id": 278,
    "title": "Побег из Шоушенка",
    "overview": "Фильм удостоен шести..."
  },
  {
    "id": 238,
    "title": "Крестный отец",
    "overview": "Криминальная сага, повествующая..."
  },
  {
    "id": 424,
    "title": "Список Шиндлера",
    "overview": "Лента рассказывает реальную историю..."
  }
]

Наполнение базы данных

Для реализации полнотекстового поиска в SQLite используются виртуальные таблицы. Внешне они выглядят как обычные таблицы SQLite, но при любом обращении к ним выполняется некая закулисная работа.

Виртуальные таблицы позволяют нам ускорить поиск. Но, помимо преимуществ, у них есть и недостатки:

• нельзя создать триггер на виртуальной таблице;
• нельзя выполнять команды ALTER TABLE и ADD COLUMN для виртуальной таблицы;
• каждый столбец в виртуальной таблице индексируется, а это значит, что могут впустую тратиться ресурсы на индексацию столбцов, которые не должны участвовать в поиске.

Для решения последней проблемы можно использовать дополнительные таблицы, которые будут содержать часть информации, а в виртуальной таблице хранить ссылки на элементы обычной таблицы.

Создание таблицы немного отличается от стандартного, у нас появились ключевые слова VIRTUAL и fts4:

 CREATE VIRTUAL TABLE movies USING fts4(id, title, overview);

Наполнение же ничем не отличается от обычного:

fun populate(context: Context) {
        val movies: MutableList<Movie> = mutableListOf()

        context.assets.open("movies.json").use {
            val typeToken = object : TypeToken<List<Movie>>() {}.type
            movies.addAll(Gson().fromJson(InputStreamReader(it), typeToken))
        }

        try {
            writableDatabase.beginTransaction()

            movies.forEach { movie ->
                val values = ContentValues().apply {
                    put("id", movie.id)
                    put("title", movie.title)
                    put("overview", movie.overview)
                }

                writableDatabase.insert("movies", null, values)
            }

            writableDatabase.setTransactionSuccessful()
        } finally {
            writableDatabase.endTransaction()
        }
}

Базовый вариант

При выполнении запроса используется ключевое слово MATCH вместо LIKE:

fun firstSearch(searchString: String): List<Movie> {
        val query = "SELECT * FROM movies WHERE movies MATCH '$searchString'"
        val cursor = readableDatabase.rawQuery(query, null)
        val result = mutableListOf<Movie>()

        cursor?.use {
            if (!cursor.moveToFirst()) return result

            while (!cursor.isAfterLast) {
                val id = cursor.getInt("id")
                val title = cursor.getString("title")
                val overview = cursor.getString("overview")

                result.add(Movie(id, title, overview))

                cursor.moveToNext()
            }
        }

        return result
    }

Для реализация обработки ввода текста в интерфейсе будем использовать RxJava:

RxTextView.afterTextChangeEvents(findViewById(R.id.editText))
        .debounce(500, TimeUnit.MILLISECONDS)
        .map { it.editable().toString() }
        .filter { it.isNotEmpty() && it.length > 2 }
        .map(dbHelper::firstSearch)
        .subscribeOn(Schedulers.computation())
        .observeOn(AndroidSchedulers.mainThread())
        .subscribe(movieAdapter::updateMovies)

Получился базовый вариант поиска. В первом элементе нужное слово нашлось в описании, а во втором элементе — и в заголовке, и в описании. Очевидно, что в таком виде не совсем понятно, что мы нашли. Давайте это исправим.

Добавляем акценты

Для улучшения очевидности поиска воспользуемся вспомогательной функцией SNIPPET. Она используется для отображения отформатированного фрагмента текста, в котором найдено совпадение.

snippet(movies, '<b>', '</b>', '...', 1, 15)

• movies — название таблицы;
• <b&gt и </b> — эти аргументы используются для того, чтобы выделить участок текста, по которому был выполнен поиск;
• … — для оформления текста, если результатом стало неполное значение;
• 1 — номер столбца таблицы, из которого будут выделяться куски текста;
• 15 — примерное количество слов, включаемых в возвращаемое текстовое значение.

Код идентичен первому, не считая запроса:

SELECT 
id, 
snippet(movies, '<b>', '</b>', '...', 1, 15) title,
snippet(movies, '<b>', '</b>', '...', 2, 15) overview 
FROM movies 
WHERE movies 
MATCH 'фильм'

Пробуем ёще раз:


Получилось нагляднее, чем в предыдущем варианте. Но это ещё не конец. Давайте сделаем наш поиск более «полным». Воспользуемся лексическим анализом и выделим значимые части нашего поискового запроса.

Финишное улучшение

В SQLite есть встроенные токенизаторы, позволяющие выполнить лексический анализ и преобразовать исходный поисковый запрос. Если при создании таблицы мы не указывали конкретный токенизатор, то будет выбран «простой». По сути он всего лишь преобразует наши данные в нижний регистр и откидывает нечитаемые символы. Нам это не совсем подходит.

Для качественного улучшения поиска нам необходимо использовать стемминг — процесс нахождения основы слова для заданного исходного слова.

В SQLite есть дополнительный встроенный токенизатор, который использует алгоритм стемминга «Стеммер Портера». Этот алгоритм последовательно применяет ряд определённых правил, выделяя значимые части слова путем отсечения окончаний и суффиксов. Например, при поиске «ключей», мы сможем получить выдачу, где содержатся слова «ключом», «ключами» и «ключа». Ссылку на подробное описание алгоритма я оставлю в конце.

К сожалению, встроенный в SQLite токенизатор работает только с английским языком, поэтому для русского языка необходимо написать свою реализацию или воспользоваться уже готовыми наработками. Мы возьмём готовую реализацию с сайта algorithmist.ru.

Преобразуем наш поисковый запрос в необходимый вид:

1. Убрать лишние символы.
2. Разбить фразу на слова.
3. Пропустить через стеммер.
4. Собрать в поисковый запрос.

После этого преобразования фраза «дворы и призраки» выглядит как «двор* OR призрак*».

Символ "*" означает, что поиск будет вестись по вхождению данного слова в другие слова. Оператор "OR" означает, что будут показаны результаты, которые содержат хотя бы одно слово из поисковой фразы. Смотрим:

Резюме

Полнотекстовый поиск не такой сложный, как может показаться с первого взгляда. Мы разобрали конкретный пример, который вы быстро и легко сможете реализовать у себя в проекте. Если вам нужно что-то сложнее, то стоит обратиться к документации, благо она есть и довольно хорошо написана.

Ссылки:

• Полные исходники
• Алгоритм стемминга
• Стеммер Портера для русского языка
• Документация по FTS4
• Про виртуальные таблицы в SQLite