Как автор финско‑английского словаря ужал 3 ГБ SQLite до 10 МБ с помощью FST — VogueTech

Что нового

Разработчик финско‑английского словаря Taskusanakirja (tsk) выкинул из проекта отдельную базу SQLite с полнотекстовым поиском объёмом около 3 ГБ и заменил её на бинарный файл на основе конечного преобразователя (finite state transducer, FST) размером примерно 10 МБ.

Ключевые изменения:

Снижение занимаемого места для словоформ и поискового индекса примерно в 300 раз: с 3 ГБ до 10 МБ.
Переход с классического префиксного дерева (trie) и отдельной SQLite‑БД к статическому FST‑индексу, который загружается целиком.
Сохранение мгновенного поиска по мере ввода (incremental search‑as‑you‑type) даже на слабых ноутбуках.
Упор на работу с агглютинативным финским языком: десятки миллионов словоформ, большое число повторяющихся суффиксов.
Переписывание части инфраструктуры на Rust и использование библиотеки fst от Andrew Gallant (BurntSushi), автора ripgrep.

Итог: словарь по‑прежнему поставляется как один статически слинкованный бинарник (.exe, .app или единый бинарь), но теперь без обязательной разовой загрузки 3‑гигабайтной базы.

Как это работает

Исходная архитектура: trie + SQLite FTS

Первая версия tsk работала на Go и опиралась на классический trie для автодополнения по префиксу:

В бинарник зашивали несколько сотен тысяч слов (порядок средних сотен тысяч, около 400 000 записей).
Trie с простыми оптимизациями занимал примерно 50–60 МБ памяти.
Чтобы убрать лаг при наборе, автор:
- ограничивал число совпадений (например, первыми 50–100 результатами);
- кэшировал все запросы длиной 1, 2 и 3 символа.

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

Когда автор попробовал добавить в систему десятки миллионов словоформ (порядка 40–60 млн), trie перестал масштабироваться: 50 МБ на 400 тысяч элементов нельзя просто растянуть до десятков миллионов и всё ещё запускать на старом студенческом ноутбуке.

Компромиссное решение было таким:

оставить в бинарнике базовый словарь и trie;
вынести все словоформы в отдельную SQLite‑базу с FTS (Full Text Search);
при необходимости пользователь искал по этой БД с помощью полнотекстового поиска.

По скорости это работало без заметной задержки, но требовало разовой загрузки 3 ГБ. Для настольного словаря это тяжёлый багаж.

Новый подход: конечный преобразователь (FST)

Через девять месяцев автор вернулся к задаче уже с опытом коммерческой разработки и переписал индексацию на Rust с использованием библиотеки fst Andrew Gallant (BurntSushi), известного по ripgrep.

Ключевая идея FST в этом контексте:

FST — это конечный автомат, который хранит упорядоченный набор строк или отображение строк в значения (map) в компактном виде.
В отличие от trie, FST эффективно делит общие префиксы и суффиксы между разными строками.
Для финского языка это особенно выгодно: множество словоформ постоянно переиспользует небольшой набор популярных суффиксов.

Новый pipeline:

Небольшая утилита на Rust считывает данные из старой 3‑гигабайтной SQLite‑БД.
Утилита сортирует строки и строит из них статический FST с помощью библиотеки fst.
На выходе получается один бинарный файл объёмом около 10 МБ.
При запуске словарь загружает этот FST в память и выполняет:
- поиск по префиксу;
- переход от словоформы к базовой форме и её определению.

Ограничения и особенности:

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

Результат: все словоформы и связи с базовыми словами теперь помещаются в 10 МБ, а поиск остаётся мгновенным.

Что это значит для вас

Когда FST — хороший выбор

Если вы разрабатываете офлайн‑инструмент или десктопное приложение с большим статическим словарём строк, FST даёт несколько практических плюсов:

Резкая экономия памяти и диска. Пример tsk показывает, что можно ужать индекс с гигабайт до десятков мегабайт. Это критично для:
- словарей и лингвистических приложений;
- офлайн‑поиска по большому каталогу товаров или документов;
- справочников и энциклопедий, которые должны работать без сети.
Поиск по мере ввода без лагов. FST хорошо подходит для:
- автодополнения по префиксу;
- быстрого поиска по словоформам с переходом к базовой записи;
- сценариев, где пользователь не готов ждать даже доли секунды.
Упрощённая доставка. Автор tsk изначально ставил цель: один бинарник без внешних зависимостей. FST‑файл на 10 МБ гораздо проще встроить в поставку, чем 3‑гигабайтную SQLite‑БД.

Если вы пишете:

настольный словарь;
офлайн‑переводчик;
утилиту для поиска по логам или коду с предсобранным индексом;

— стоит посмотреть в сторону fst для Rust и похожих реализаций на других языках.

Когда лучше остаться на SQLite или trie

FST в таком виде — не серебряная пуля. Есть сценарии, где он не подойдёт:

Данные часто меняются. Если вы постоянно вставляете и удаляете записи, FST будет неудобен. Его нужно перестраивать целиком.
Нужны сложные запросы. SQLite с FTS даёт привычный SQL, булевы запросы, ранжирование по релевантности. FST — это скорее про быстрый поиск по ключу, префиксу или похожим операциям.
Маленький объём данных. Если у вас несколько тысяч записей, выгода от FST будет минимальной. Проще и быстрее оставить trie или SQLite.

Для учебных и pet‑проектов вывод из истории tsk такой:

Не бойтесь «плохих, но быстрых» решений на старте. Автор сначала прикрутил SQLite с FTS, потому что это он умел и это работало.
Это дало ему возможность позже спокойно поэкспериментировать с Rust и FST и найти более компактное решение.

Доступность и ограничения

Taskusanakirja — настольное приложение, которое разработчик распространяет как единый бинарник. В исходном материале нет деталей по магазинам приложений или региональным ограничениям, но архитектура не зависит от облака и не требует VPN: весь поиск идёт локально.

Место на рынке

По задаче tsk конкурирует не с GPT‑5 или Claude 4, а с более классическими подходами к поиску по строкам:

Trie:
- Плюс: простая реализация, поддержка динамических вставок.
- Минус: плохо масштабируется по памяти при десятках миллионов ключей.
- В tsk trie держал около 400 000 слов и занимал 50–60 МБ. Масштабировать до 40–60 млн словоформ на тех же ресурсах не получилось.
SQLite + FTS:
- Плюс: привычный SQL, мощный полнотекстовый поиск, хорошая скорость.
- Минус: крупные индексы легко раздуваются до гигабайт.
- В tsk полнотекстовая БД со словоформами весила около 3 ГБ, хотя работала без ощутимой задержки.
FST (fst crate для Rust):
- Плюс: компактное хранение огромных наборов строк, особенно при большом числе общих префиксов и суффиксов.
- Плюс: быстрый поиск по префиксу и смежным операциям.
- Минус: ориентирован на статические наборы данных, обновление требует перестройки.
- В tsk FST‑индекс занял 10 МБ, что дало примерно 300‑кратное уменьшение по сравнению с SQLite‑вариантом.

Числовых сравнений по времени отклика автор не приводит, но подчёркивает, что и SQLite‑решение, и FST‑индекс обеспечивают поиск «без заметной задержки» даже на старом студенческом ноутбуке.

Как запустить: общая схема

Автор не публикует полный исходный код, но по описанию можно восстановить базовый рабочий процесс для собственного проекта на Rust с использованием fst:

Подготовить данные.
- Экспортировать строки (например, словоформы) и связанные с ними значения (ID базового слова) из существующей БД.
- Отсортировать их лексикографически.
Собрать FST.
- Написать утилиту на Rust, которая читает отсортированные пары ключ → значение и строит FST через fst::MapBuilder или аналогичный API.
Встроить FST в приложение.
- Поставлять FST‑файл рядом с бинарником или вшивать его в ресурсы.
- При запуске загружать FST в память и выполнять запросы по мере ввода пользователя.

Один из источников вдохновения для автора — статья Andrew Gallant «Index 1,600,000,000 Keys with Automata and Rust», где показано, как индексировать 1,6 миллиарда ключей с помощью автоматов и Rust. Для детальной реализации стоит опираться именно на неё и на документацию к fst.

Главный вывод из истории tsk: если у вас огромный, но статический словарь строк и жёсткие требования к размеру и скорости офлайн‑поиска, FST даёт шанс радикально сократить объём хранимых данных без потери отзывчивости интерфейса.