Содержание
Коротко
Разработчик словаря tsk заменил 3 ГБ SQLite на бинарник FST (finite state transducer) размером порядка 10 МБ — примерно в 300 раз меньше по памяти. История про то, как выбор структуры данных важнее «просто подключить базу».
Что произошло
Проект — мобильный словарь (финско-английский). Сначала поиск по префиксу строили на trie в памяти: для простых языков работало, для финского с богатой флексией — нет.
Временным решением стал SQLite с полнотекстовым поиском (FTS). Плюсы: быстро внедрить, привычный SQL. Минусы: пользователям приходилось качать гигабайты данных — неприемлемо для слабых устройств.
Следующий шаг — Rust и FST: автомат, который компактно кодирует словарь, используя общие суффиксы и повторяющиеся части форм. Вместо хранения «плоского» массива строк структура сжимает лексикон так, как это делают морфологические словари.
Итоговая линейка tsk v2 — порядка 20 МБ на диске вместо многогигабайтного дампа, с сохранением нужного поиска.
Почему это важно
Не каждая задача «поиска по словам» = SQLite или Elasticsearch. Когда данные статичны, хорошо структурированы и читаются целиком в память или с диска одним куском, специализированные структуры (trie, FST, суффиксные массивы) часто бьют универсальную БД по размеру и латентности.
Уроки для бэкенда и тулинга:
- FTS в SQLite — отличный прототип, плохой финальный формат дистрибутива, если вес критичен.
- Морфология и агглютинация ломают наивный trie; нужны структуры, учитывающие общие окончания.
- Rust + нативные crate’ы под FST — практичный путь, если команда готова выйти за пределы «всё в Postgres».
На практике
Если у вас похожая задача (глоссарий, подсказки, автокомплит по статическому корпусу):
- Оцените размер дистрибутива так же строго, как latency API.
- Прототипируйте на SQLite/Postgres, но заложите экспорт в read-only бинарник для продакшена.
- Посмотрите FST / double-array trie и готовые библиотеки в экосистеме вашего языка.
- Замерьте память на целевом устройстве, а не только на dev-машине.
Для веб-приложений с частыми обновлениями корпуса FST сложнее инкрементировать — этот кейс про редко обновляемый словарь.
Итог
Замена SQLite на FST — не магия Rust, а правильная модель данных под домен: статический словарь, префиксный поиск, минимальный вес. Имеет смысл читать оригинал, если проектируете собственные справочники, подсказки или офлайн-корпуса — особенно с богатой морфологией.