Полнотекстовый поиск в 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. Собрать в поисковый запрос.

 object Porter {      private val PERFECTIVEGROUND = Pattern.compile("((ив|ивши|ившись|ыв|ывши|ывшись)|((<=[ая])(в|вши|вшись)))$")      private val REFLEXIVE = Pattern.compile("(с[яь])$")      private val ADJECTIVE = Pattern.compile("(ее|ие|ые|ое|ими|ыми|ей|ий|ый|ой|ем|им|ым|ом|его|ого|ему|ому|их|ых|ую|юю|ая|яя|ою|ею)$")      private val PARTICIPLE = Pattern.compile("((ивш|ывш|ующ)|((?<=[ая])(ем|нн|вш|ющ|щ)))$")      private val VERB = Pattern.compile("((ила|ыла|ена|ейте|уйте|ите|или|ыли|ей|уй|ил|ыл|им|ым|ен|ило|ыло|ено|ят|ует|уют|ит|ыт|ены|ить|ыть|ишь|ую|ю)|((?<=[ая])(ла|на|ете|йте|ли|й|л|ем|н|ло|но|ет|ют|ны|ть|ешь|нно)))$")      private val NOUN = Pattern.compile("(а|ев|ов|ие|ье|е|иями|ями|ами|еи|ии|и|ией|ей|ой|ий|й|иям|ям|ием|ем|ам|ом|о|у|ах|иях|ях|ы|ь|ию|ью|ю|ия|ья|я)$")      private val RVRE = Pattern.compile("^(.*?[аеиоуыэюя])(.*)$")      private val DERIVATIONAL = Pattern.compile(".*[^аеиоуыэюя]+[аеиоуыэюя].*ость?$")      private val DER = Pattern.compile("ость?$")      private val SUPERLATIVE = Pattern.compile("(ейше|ейш)$")      private val I = Pattern.compile("и$")     private val P = Pattern.compile("ь$")     private val NN = Pattern.compile("нн$")      fun stem(words: String): String {         var word = words         word = word.toLowerCase()         word = word.replace('ё', 'е')         val m = RVRE.matcher(word)          if (m.matches()) {             val pre = m.group(1)             var rv = m.group(2)             var temp = PERFECTIVEGROUND.matcher(rv).replaceFirst("")             if (temp == rv) {                 rv = REFLEXIVE.matcher(rv).replaceFirst("")                 temp = ADJECTIVE.matcher(rv).replaceFirst("")                 if (temp != rv) {                     rv = temp                     rv = PARTICIPLE.matcher(rv).replaceFirst("")                 } else {                     temp = VERB.matcher(rv).replaceFirst("")                     if (temp == rv) {                         rv = NOUN.matcher(rv).replaceFirst("")                     } else {                         rv = temp                     }                 }             } else {                 rv = temp             }              rv = I.matcher(rv).replaceFirst("")              if (DERIVATIONAL.matcher(rv).matches()) {                 rv = DER.matcher(rv).replaceFirst("")             }              temp = P.matcher(rv).replaceFirst("")             if (temp == rv) {                 rv = SUPERLATIVE.matcher(rv).replaceFirst("")                 rv = NN.matcher(rv).replaceFirst("н")             } else {                 rv = temp             }             word = pre + rv         }          return word     } }

val words = searchString                 .replace("\"(\\[\"]|.*)?\"".toRegex(), " ")                 .split("[^\\p{Alpha}]+".toRegex())                 .filter { it.isNotBlank() }                 .map(Porter::stem)                 .filter { it.length > 2 }                 .joinToString(separator = " OR ", transform = { "$it*" })

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

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

Резюме

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

Ссылки:

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