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

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

Есть строка в переменной 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К строк, правда, отработает не слишком быстро.

Вижу подзапрос → меняю на CTE

Многие студенты (да и не только студенты) обожают многоуровневые SQL-запросы. Пожалуйста, пожалуйста, пожалуйста, не пишите их. Используйте табличные выражения: https://antonz.ru/cte/

Нечеткое сравнение строк и фонетика

Пока готовлю заметку про поиск похожих строк, сделал новое расширение для SQLite. Вот что в нем есть.

Сравнение строк по похожести:

— Расстояние Левенштейна
— Расстояние Дамерау — Левенштейна
— Расстояние Хэмминга
— Сходство Джаро — Винклера
— Оптимальное выравнивание строк
— Расстояние Spellcheck

Фонетические коды:

— Soundex
— Refined Soundex
— Spellcheck

И транслитерация (привет → privet).

https://github.com/nalgeon/sqlean/blob/main/docs/fuzzy.md

Быстрый поиск похожих слов на SQL
(готовое решение)

Я что-то закопался с подробной статьей про поиск похожих слов, так что вот пока готовое решение на SQLite.

Напомню, что задача в общем виде такая:

— Человек ввел произвольное слово.
— Мы хотим найти наиболее похожее слово из готового словаря.
— И сделать это быстро.

Полный перебор по словарю работает хорошо, но медленно.

Чтобы сделать быстро, понадобится расширение spellfix.

Подключаем расширение:

.load ./spellfix

Создаем таблицу для словаря:

create virtual table dictionary using spellfix1;

Загружаем в нее данные:

insert into dictionary(word)
select ... from ...;

И ищем похожие слова:

select word
from dictionary
where word match ?
limit 1

Например:

sqlite> select word from dictionary where word match 'абривиатура' limit 1;
аббревиатура

sqlite> select word from dictionary where word match 'рассчет' limit 1;
расчет

sqlite> select word from dictionary where word match 'дорга' limit 1;
дорога

Изи!

Позже отдельно распишу, как и почему все работает. И как сделать самостоятельно на любой базе.

500 учеников на курсе про «окошки»!

Зашел сегодня на «Степик» и увидел, что на курс по оконным функциям записались уже 500 человек. Когда его делал, совсем не рассчитывал на такую популярность.

Вообще, курс про «окошки» появился как спин-офф моего большого курса «SQLite для аналитики». Там был модуль «оконные функции», и он мне самому так понравился, что на его основе сделал отдельный курс.

Судя по всему, получилось неплохо, потому что студентов много и отзывы очень позитивные. Люди находят курс без всякой рекламы. Полностью прошли курс 40% участников — это очень недурно для онлайн-формата. Выпускники пишут, что стали регулярно использовать «окошки» в повседневной работе — лучший результат, что я могу представить.

Признаться, мне курс тоже нравится. Сам использую его как конспект, когда не уверен, как что-то работает.

«Родительскому» курсу про SQLite такая популярность и не снилась 🤷

SQLite 3.37

Тут у sqlite вышла новая версия! Да какая — теперь он научился проверять типы данных (двадцать лет ругали, что не проверяет).

Написал обзор основных изменений:
https://habr.com/ru/news/t/592085/

Датасет слов английского языка

Обнаружил, что у Оксфордского университета есть списки распространенных слов и выражений английского языка. Доступны в традиционно «удобном» формате — html-амбразуре на сайте либо PDF.

Извлек их и сделал нормальные наборы данных в CSV.

Атрибутика:

— слово
— часть речи
— уровень (A1, A2, B1, B2, C1)
— ссылка на подробное определение
— ссылка на озвучку в ogg

https://github.com/nalgeon/words

Если вы написали отличную статью, о которой никто не знает

В русскоязычном айти есть несколько «селебрити», которых все читают и обсуждают. И намного больше малоизвестных ребят, которые пишут классные статьи. У селебрити и так все отлично, а вот остальным я бы хотел помочь найти свою аудиторию.

Поэтому провожу эксперимент! Готов опубликовать ссылку на вашу статью, если она мне понравится. Бесплатно. Знаменитостью это вас не сделает, но статью точно увидит больше людей.

Все условия

Быстрый поиск похожих слов на SQL

Написал статью о том, как искать похожие слова и исправлять опечатки на большом словаре (1.5 млн записей).

рассчет → расчет
сонце → солнце
абривиатура → аббревиатура

Попутно вы узнаете, как считать расстояние между словами, что такое фонетические коды, и как использовать фонетику и расстояния для моментального поиска (<50 мс).

https://antonz.ru/similar-words/

SQLite GUI

По запросу «sqlite gui» в гугле на первой позиции стоит программа «DB Browser for SQLite». На мой взгляд, она плоха примерно всем, и такая популярность ничем не оправдана.

Если вы работаете под Windows, обратите внимание на sqlite-gui. Она легкая, быстрая, удобная, и с кучей приятных дополнительных фич вроде настраиваемых шорткатов, генератора данных и даже встроенного REST API сервера.

А еще автор (к сожалению, не знаю даже его имени) пишет классные статьи про SQLite на хабре.

Читаем и пишем файлы прямо из SQLite

У CLI-утилиты sqlite есть встроенные функции writefile и readfile. Я их немного доработал и оформил в виде расширения fileio.

Пишем в файл:

select writefile('hello.txt', 'hello world');

Читаем:

select readfile('hello.txt');

Выводим содержимое каталога:

select * from lsdir('.');

Для любителей делать все на свете, не покидая SQL ツ

Unix timestamp

SQLite 3.38 получит функцию даты/времени в формате unix timestamp! А пока он не вышел, можно попробовать в моем расширении isodate:

select unixepoch('2021-12-22 12:34:45');
1640176485

https://github.com/nalgeon/sqlean/issues/27#issuecomment-998138191

Все расширения SQLite

Мне очень нравится SQLite. Это миниатюрная встраиваемая база, которая отлично подходит как для исследовательского анализа данных, так и в качестве хранилища для небольших приложений.

Но есть у нее один недостаток: маловато встроенных функций по сравнению с PostgreSQL или Oracle.

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

Мне хотелось большой системности.

Так появился проект sqlean — в нем я собираю вместе недостающие в SQLite функции, распределяю их по модулям, рефакторю код, пишу тесты и документацию. Получается что-то вроде стандартной библиотеки, как в Python или Go, только для SQLite.

Там есть регулярные выражения, работа с файлами, мат. статистика, поддержка CSV. Даже массивы есть! (почти как в постгресе).

Планирую по каждому модулю написать отдельную статью, а пока вот краткий обзор:

https://antonz.ru/sqlean/

Стрелочка для JSON

В SQLite может появиться специальный синтаксис для JSON, как в постгресе!

Было:

select json_extract(person,'$.name') ...

Стало:

select person->'name' ...

Не 100%, но весьма вероятно.

https://sqlite.org/src/doc/json-enhancements/doc/json-enhancements.md

Гибкие типы данных

Люди часто не понимают, что за ерунда происходит в SQLite с типами данных. Давайте разберемся.

SQLite использует пять типов данных:

— INTEGER — целые числа,
— REAL — действительные числа,
— TEXT — строки,
— BLOB — бинарные данные,
— NULL — пустое значение.

Пока ничего необычного (только типов маловато по сравнению с другими СУБД).

А как вам такое:

SQLite может хранить данные любого типа — вне зависимости от того, какой тип указан на столбце.

Хотите записать число 3.14 в integer-поле? Пожалуйста (и никакого округления). Или, может быть, 'привет' в поле типа real? Без проблем.

Дело в том, что SQLite хранит тип не только на столбце, но и на каждом значении в таблице. Именно поэтому в одном столбце без проблем хранятся значения разных типов. Тип на столбце используется как рекомендация: при вставке SQLite пытается привести значение к рекомендуемому типу, но если не получилось — сохраняет «как есть».

Это удобно для анализа данных — можно сначала все загрузить, а потом средствами SQL разбираться с проблемными значениями. Любая другая СУБД выдаст ошибку при импорте и заставит вас «шерстить» файл скриптами или вручную.

С другой стороны, это неожиданное поведение, за которое многие недолюбливают SQLite и даже прозвали его «JavaScript в мире баз данных». Со временем разработчики SQLite прислушались и сделали альтернативный механизм «строгих» таблиц — но о нем в другой раз.

Люди и код

Неожиданно для себя стал гостем подкаста. Мы с Тимуром Тукаевым хотели сделать статью, но в аудио-формате она получилась живее и интереснее.

Послушайте, если вам интересно про sqlite, мои проекты или открытый код в целом.

Конкретно sqlite обсуждаем с 12:15.

https://we.fo/1604736632

P.S. Поскольку к записи мы специально не готовились, звучу я как из ведра. Но если потерпеть минуту, вы привыкнете 😁

Новости песочницы

Обновил SQLite-песочницу! Самое главное — теперь можно сохранять сниппеты, не указывая API-ключ гитхаба. Жмакнули на «share» и готово. Так что песочницей смогут пользоваться люди, далекие от гитхаба 🎉

Еще обновил SQLite до свежайшей версии 3.37.2. И включил пачку стандартных расширений вроде R*Tree. А в планах еще приделать все расширения из sqlean, вот тогда заживем вообще.

https://sqlime.org/

Как хранить дату

В SQLite нет отдельных типов для даты и времени. Поэтому у вас есть только два варианта, каждый со своими достоинствами и недостатками. Рассмотрим их вкратце.

ISO 8601

Международный стандарт, который записывает дату как 2022-01-27, а дату-время как 2022-01-27 19:30:15. Иногда добавляют еще миллисекунды: 2022-01-27 19:30:15.123.

Стандарт включает кучу нюансов, но основные формы записи именно такие.

Дата при этом хранится в SQLite как текст. Занимает 12 байт (без времени), 21 байт (до секунд) или 25 байт (с миллисекундами).

➕ Человекочитаемая дата
➕ Удобно сравнивать ('2021-12-30' < '2022-01-27')
➖ Неудобно считать разницу между датами
➖ Занимает много места

Unix Time

Unix Time — это количество секунд, прошедшее с 01.01.1970. Например unix time для 2022-01-27 19:30:15 = 1643311815, а для 1960-03-25 = -308361600.

Дата при этом хранится в SQLite как число: целое, если достаточно точности до секунды, или действительное — если нужны миллисекунды. Занимает 8 байт.

➕ Удобно сравнивать
➕ Удобно считать разницу между датами
➕ Компактное представление
➖ Непонятна человеку

Часовые пояса

Если вы работали раньше с «международными» датами в любом виде, то знаете, как больно бывает от часовых поясов. В SQLite с ними все просто: часовые пояса не поддерживаются.

Поэтому, какой бы формат вы не выбрали (ISO 8601 или Unix Time), соблюдайте главное правило:

Хранить даты только в часовом поясе UTC

Иначе никогда концов не найдете.

⚫ В О Й Н А