Найти максимально похожую строку

Подписчик задал интересный вопрос:

Есть строка в переменной str1.
Есть sqlite3 и 600,000 строк внутри.
Как найти макимально приближенно похожую строку в базе? Точного сходства с str1 в базе нет!

Посмотрим на упрощенном примере. Допустим, у нас есть таблица employees, а в ней столбец name:

sqlite> select name from employees;
Дарья
Борис
Елена
Ксения
Леонид
Марина
Иван
Вероника
Григорий
Анна

Хотим найти сотрудника, чье имя больше всего похоже на Вера. Как это сделать?

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

select
  name,
  similarity(name, 'Вера') as sim
from employees
order by sim desc
limit 1

Но такой функции нет. Значит, либо искать расширение, в котором она найдется, либо подключить функцию из любимого языка программирования. На питоне, например, сделать это несложно:

import sqlite3
from difflib import SequenceMatcher

def similarity(a, b):
  ratio = SequenceMatcher(None, a.lower(), b.lower()).ratio()
  return round(ratio, 2)

db = sqlite3.connect("employees.db")
db.create_function("similarity", 2, similarity)

Теперь можно выполнить наш запрос:

cursor = db.execute(query)
result = cursor.fetchall()
print(result)

Он вернет самое похожее имя:

[('Вероника', 0.67)]

Ровно то, что мы хотели. Для 600К строк, правда, отработает не слишком быстро.