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',
  username: 'postgres'
)

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

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

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

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

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

    # Для работы триграммного поиска необходимо дополнительно активировать расширение
    enable_extension "pg_trgm"
  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"

Спрячем всю логику в метод модели и немного упростим код:

# ...
class Country < ActiveRecord::Base
  def self.similar(query)
    sql = %(
      SELECT name, similarity(name, '#{query}') AS s_name
      FROM countries WHERE name % '#{query}'
      ORDER BY s_name desc
    )
    connection.query(sql)
  end
end

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

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

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

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

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

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

# Running:

..

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

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

Итого

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

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

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