company_banner

Полнотекстовый поиск в 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);

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

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

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



    Резюме


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

    Ссылки:


    • +14
    • 3,3k
    • 9
    Райффайзенбанк
    161,24
    Развеиваем мифы об IT в банках
    Поделиться публикацией

    Комментарии 9

      0
      Если список уже в памяти, то зачем делать запросы к БД, это же будет дольше?
      Room уже вроде начал поддерживать FTS из коробки и всё должно быть проще?
        0
        Наполнение базы данных из ассетов сделано для примера. В реальном проекте данные будут загружаться с сервера, а между наполнением базы данных и поиском может пройти значительное время (причем поиск будет происходить без наличия интернета).
        По поводу Room я с вами согласен, реально удобнее, но, по тем или иным причинам, не все используют Room. Единственный момент, что с поддержкой русского языка так и не разобрались (если я не прав — поправьте пожалуйста).
        0
        val query = «SELECT * FROM movies WHERE movies MATCH '$searchString'»
        SQL-инъекция?
          0
          Хорошее замечание. Возможно стоило оставить небольшую заметку про возможность инъекции. Но раскрывать тему SQL-инъекций в рамках данной статьи не вижу смысла, так как на хабре есть несколько интересных статей на эту тему.
            0
            Имхо, проще ничего не раскрывать, а отредактировать пример, чтобы использовались параметризованные запросы. Это увеличит размер кода на 1 строку. Всё-таки, публиковать примеры с дырами в корпоративном блоге банка — опасная для репутации затея )))
              0
              А смысл делать инъекциию? Если клиент можно просто достать базу данных и посмотреть. (: Разве только для того что-бы приложение не упало.
                0
                А ничего, что по этой статье начинающие программисты учиться будут, и код копипастить, как образец наилучших практик.
                  0
                  Начинающие программисты и полнотекстовый поиск? Ну ладно (: А автору кстати можно поправить код и добавить вызов вот этой функции и если введут всякие кавычки и прочее то ничего не упадет developer.android.com/reference/android/database/DatabaseUtils.html#sqlEscapeString(java.lang.String)
          0
          Не стоит ли вместо map()-а использовать switchMap()? И стоит ли здесь еще BackPressure вписать?

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое