Находим похожие результаты в PostgreSQL или поиск с ошибками

trgm.md

Замечали ли вы, что когда вы набираете что-то в google или yandex с ошибками, вас поправляют?

Возможно вы искали ... ?

Данная концепция называется триграммным поиском, она позволяет искать слова и фразы с опечатками.

Как это работает?

Каждое слово делится на сочетания из 3х букв – триграммы. На примере слова "Россия", будет:

р, ро, рос, осс, сси, сия, си, я

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

Установка зависимостей

Давайте посмотрим, как это выглядит на деле. Мы не будем создавать новое rails приложение и вместо этого напишем маленький ruby-скрипт, который сможет работать с базой данных PostgreSQL, используя Active Record. Весь код добавляется в один файл последовательно (итоговый скрипт для нетерпеливых)

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

gem install activerecord pg minitest --no-ri --no-doc

require 'active_record'
require 'open-uri'
require 'pg'
require 'minitest/autorun'

Подготовим данные

Создадим базу данных в терминале

createdb trgm;

Далее, нам необходимо установить соединение с базой (данные для входа могут отличаться, в зависимости от ваших настроек PostgreSQL)

# ...
ActiveRecord::Base.establish_connection(
  adapter: 'postgresql',
  database: 'trgm',
  host: 'localhost'
)

Добавим модель, миграцию и данные.

Вы спросите: "а что вообще за таблица, а где мы возьмём данные?" Всё просто, мы создадим табличку со списком стран, а для того, чтобы где-то взять этот список, воспользуемся api vk.com.

# ...
class Country < ActiveRecord::Base
end

class CreateCountryTable < ActiveRecord::Migration[4.2]
  def self.up
    create_table :countries do |t|
      t.string :name
    end

    # Загружаем json ответ от vk, перебираем каждый элемент массива и добавляем запись в базу
    data = JSON.load open("https://api.vk.com/api.php?oauth=1&method=database.getCountries&v=5.68&need_all=1&count=234")
    data["response"]["items"].each do |country|
      Country.create!(name: country["title"])
    end

    # Для работы триграммного поиска необходимо дополнительно активировать расширение
    enable_extension "pg_trgm"
    
    # Добавим индекс для быстрого поиска по полю
    execute 'CREATE INDEX trgm_idx ON countries USING gist (name gist_trgm_ops);'
  end

  def self.down
    drop_table :countries
  end
end

Вы спросите, а как прогнать миграцию, если у нас нет rails и rake db:migrate не сработает? Опять же, всё просто, мы запускаем класс вызовом метода migrate и в параметрах передаём какой метод нам нужен, если у нас не существует таблицы countries. Данная проверка необходима для того, чтобы скрипт не сваливался с ошибкой при повторном выполнении.

# ...
CreateCountryTable.migrate(:up) unless ActiveRecord::Base.connection.table_exists? :countries

Выведем количество стран, чтобы убедиться, что всё хорошо (на момент написания статьи насчитывалось 234 страны).

# ...
p "Country count: #{Country.count}"

Назначить Ты можешь назначить автора этой статьи
своим персональным наставником

Поиск схожих записей

Ну, а теперь самое главное: в postgresql есть функция similarity, которая высчитывает схожесть. По данному числу можно фильтровать данные, например.

ARGV[0] означает что нужно взять первый аргумент при вызове файла, а если он пустой, то подставить "мал", как значение по-умолчанию. Т.е. скрипт достаточно умён, чтобы мы могли вызвать его как trgm.rb Росси и в результате получить похожие страны с этим кусочком слова.

# ...
name = ARGV[0] || 'мал'

query = %(
  SELECT name, similarity(name, '#{name}') AS s_name
  FROM countries WHERE name % '#{name}'
  ORDER BY s_name desc
)

data = ActiveRecord::Base.connection.exec_query(query).rows

По запросу ruby trgm.rb мадивы, скрипт скажет что совпадений нет и "спросит": "Возможно вы искали мальдивы?".

# ...
data.each do |country|
  p country.first + ": " + country.last
  p
end

# => "Мальдивы: 0.454545"

Данный код является не очень безопасным, так как существует возможность эксплуатации SQL injection, мы упростим его и будем использовать встроенный метод where (метод Active Record) и доставать записи, процент схожести которых больше 0.3:

# ...
class Country < ActiveRecord::Base
  def self.similar(query)
    where('similarity(name, ?) > 0.3', query)
  end
end

Тестирование

Ну и в завершении, пара тестов (без них никогда не стать настоящим программистом, да, это так :))

# ...
describe Country do
  it 'находит страну по точному названию' do
    data = Country.similar 'Россия'
    assert_equal data.count, 1
    assert_equal data.first.name, 'Россия'
  end

  it 'находит страну с ошибкой в названии' do
    data = Country.similar 'Росия'
    assert_equal data.count, 1
    assert_equal data.first.name, 'Россия'
  end
end

Теперь, когда мы запустим наш итоговый скрипт, мы увидим, что импортировалось 234 страны, будут найдены Мальдивы и пройдёт 2 теста:

➜ trgm ruby trgm.rb 0s
"Country count: 234"
"Мальдивы:"
Run options: --seed 65291

# Running:

..

Finished in 0.011035s, 181.2481 runs/s, 543.7443 assertions/s.

2 runs, 4 assertions, 0 failures, 0 errors, 0 skips

Итого

Теперь мы можем:

• получать похожие записи 1 строчкой кода Country.similar("мадивы")
• получать записи с ошибками при вводе
• использовать данный поиск для похожих товаров, в интернет магазине например

Как альтернатива, чтобы не писать свой велосипед, можно воспользоваться чужим велосипедом - pg_search. Это на столько замечательный и удобный гем, что у нас есть на него целая статья :)