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

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

qf4ecmc9japqzpsmwfoajjrlozk.jpeg

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


  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);


Комменатрий про версию fts5

В SQLite её уже добавили. Эта версия более производительная, более точная и содержит в себе много новых фишек. Но из-за большой фрагментации Android мы не можем использовать fts5 (доступна с API24) на всех устройствах. Можно написать разную логику под разные версии операционной системы, но это серьёзно усложнит дальнейшую разработку и поддержку. Мы решили пойти более лёгким путём и используем fts4, который поддерживается на большинстве устройств.


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

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

        context.assets.open("movies.json").use {
            val typeToken = object : TypeToken>() {}.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 {
        val query = "SELECT * FROM movies WHERE movies MATCH '$searchString'"
        val cursor = readableDatabase.rawQuery(query, null)
        val result = mutableListOf()

        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)


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

wbjqvon_lp-zpsc9_wnnlxey6e0.png


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


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

snippet(movies, '', '', '...', 1, 15)


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


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

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


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

7uwc1x11wt7dw4qdterexvd2y1a.png


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

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


В 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» означает, что будут показаны результаты, которые содержат хотя бы одно слово из поисковой фразы. Смотрим:

vwc9sxcgklqvfinisn_yq3hx998.png

Резюме


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

Ссылки:


© Habrahabr.ru