Могу ли я использовать ActiveRecord для поиска строк на основе ближайшего совпадения (расстояние Левенштейна)

Question

У меня есть таблица строк в моей базе данных. Я выбираю один из них, A .

Как я могу искать в остальной части таблицы, чтобы найти строку, наиболее похожую на A ?

Answer 1

Я думаю, вы ищете расстояние Левенштейна. Расстояние Левенштейна между двумя строками - это количество, необходимое для добавления / удаления / изменения символа, чтобы сделать строку равной.

Вот реализация в Ruby

Answer 2

Вот простая реализация алгоритма расстояния Левенштейна в Ruby:

def levenshtein(a, b)
  case
    when a.empty?: b.length
    when b.empty?: a.length
    else [(a[0] == b[0] ? 0 : 1) + levenshtein(a[1..-1], b[1..-1]),
          1 + levenshtein(a[1..-1], b),
          1 + levenshtein(a, b[1..-1])].min
  end
end

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

Answer 3

Если вам нужно фонетическое сходство между двумя строками, вы можете использовать функцию soundex SQL (в Oracle также есть метафон).

Это преобразует передаваемую ему строку в 4-значный код (1 буква, 3 цифры iirc), который представляет фонетический звук слова (ей).

Если вы сделаете это для обеих сравниваемых строк, если они будут фонетически похожи, вы можете сопоставить коды.