از ۳ گیگابایت به ۱۰ مگابایت با FST و Rust
خلاصهٔ کاملتر
نویسنده روی یه پروژهی شخصی به اسم Taskusanakirja (یا به اختصار tsk) کار میکنه — یه دیکشنری فنلاندی-انگلیسی با قابلیت جستجوی لحظهای. از اول هدف این بوده که کل برنامه بهصورت یه فایل اجرایی واحد شیپ بشه؛ یعنی باید روی لپتاپهای قدیمی هم راحت اجرا بشه.
مشکل اصلی اینه که فنلاندی یه زبان پیوندی (agglutinative) خیلی پیشرفتهست. هر ریشه میتونه بیش از صد شکل مختلف داشته باشه — بهخاطر پسوندهای متعدد، حالتهای دستوری مختلف (۱۵ حالت!)، و پدیدههایی مثل «تبدیل صامت» که مثلاً katu (خیابان) در حالت مضافالیه میشه kadun نه katun. این یعنی برای پوشش کامل صرفونحو، باید ۴۰ تا ۶۰ میلیون آیتم ذخیره بشه.
نسخهی اول با یه trie (درخت پیشوندی) در Go پیادهسازی شده بود و با بهینهسازیهایی مثل کش کردن ترکیبهای ۱ تا ۳ حرفی، حدود ۶۰ مگابایت رم میخورد — برای ۴۰۰ هزار آیتم قابل قبول بود. ولی برای ۴۰-۶۰ میلیون آیتم این روش جواب نمیداد. راهحل موقت هم این شد که اطلاعات صرفی زبان در یه پایگاه داده SQLite جداگانه با افزونه FTS5 (جستجوی متن کامل) ذخیره بشه — که کار میکرد، ولی یه دانلود یکباره ۳ گیگابایتی نیاز داشت!
نه ماه بعد، نویسنده با تجربهی بیشتر به سراغ راهحل بهتری رفت: FST یا Finite State Transducer. این ساختار داده توسط Andrew Gallant (معروف به BurntSushi، سازندهی ابزار ripgrep) در کتابخانهی fst برای Rust پیادهسازی شده. FST برخلاف trie، هم پیشوندها و هم پسوندها رو فشرده میکنه. این برای فنلاندی یعنی اینکه هزاران کلمه که همه به -ssa-mme-kin ختم میشن فقط یه بار ذخیره میشن.
نتیجه؟ همون ۳ گیگابایت داده به ۱۰ مگابایت تبدیل شد — کاهشی حدود ۳۰۰ برابری. نسخه Pro از tsk v2 داره شکل میگیره و احتمالاً کل برنامه حول ۲۰ مگابایت بشه؛ یعنی ۳ برابر کوچکتر از نسخهی رایگان اول.
نکتهی جالب داستان اینه که نویسنده تأکید میکنه راهحل بد قبلی (SQLite) ارزشش رو داشت — چون کار میکرد، قابل فهم بود، و فرصت داد که ۹ ماه بعد با دانش بیشتر یه راهحل واقعی پیدا بشه. گاهی «کار بد انجام دادن» بهتر از «هیچکاری نکردن» است.
نکات کلیدی:
- FST (Finite State Transducer) یه ساختار دادهست که مجموعههای بزرگ رشته رو فشرده میکنه و جستجوی سریع پیشوندی، پسوندی و fuzzy رو پشتیبانی میکنه
- برخلاف trie که فقط پیشوند مشترک رو فشرده میکنه، FST پسوندهای مشترک رو هم به اشتراک میذاره
- کتابخانهی
fstدر Rust توسط سازندهیripgrepنوشته شده - برای دادههای استاتیک (که در زمان اجرا تغییر نمیکنن) FST بهترین عملکرد رو داره
- زبانهای پیوندی مثل فنلاندی بهخاطر پسوندهای تکراری زیاد، بیشترین بهره رو از FST میبرن
