المستوى: متوسط. لازم تكون مرتاح مع class في Python، dict، recursion، وعارف يعني إيه Big-O. لو خلصت أي كورس Python أساسي وعارف الفرق بين O(n) و O(1)، هتفهم المقال كله من غير مشكلة.
Trie من الصفر: ابنِ autocomplete بيخدم 5 مليون كلمة في 300 ميكروثانية
لو search box عندك بياخد 80 مللي ثانية يرجّع 10 اقتراحات من جدول فيه 5 مليون كلمة، المشكلة مش في السيرفر ولا في الـ network. المشكلة إنك بتستخدم LIKE 'prefix%' على PostgreSQL أو list comprehension على array. Trie بينزّل الزمن ده لـ 300 ميكروثانية (أسرع 266 مرة) في 480MB ذاكرة، بدون أي query للـ DB.
المشكلة باختصار
autocomplete على dataset كبير (>1 مليون كلمة) بيتحوّل لمشكلة أداء حقيقية لمّا الـ traffic يعدّي 200 طلب/ثانية. الحلول الشائعة بتفشل:
LIKE 'pre%'مع B-tree index في Postgres: 80ms متوسط، بيقع تحت ضغط.- Elasticsearch: شغّال بس بيكلّف 4GB RAM لكل node + شبكة + تشغيل cluster.
[w for w in words if w.startswith(p)]في Python: 1200ms على 5 مليون كلمة.
الـ Trie بيحل ده في 300 ميكروثانية ثابتة، مهما كبر الـ dataset.
للمبتدئ: تخيّل درج فهرس مكتبة قديمة
افتراضي إنك بتدوّر على كتاب اسمه يبدأ بـ "تار-" في مكتبة فيها 50 ألف كتاب. مش هتقعد تقرا اسم كل كتاب من الأول للآخر — ده بياخد ساعات. بدل ما تعمل كده، بتمشي على الـ catalog: تروح على درج "ت"، تفتحه تلاقي 4 أدراج جوّاه: "تا"، "تب"، "تج"، "تر". تختار "تا"، تلاقي درج صغيّر مكتوب عليه "تار". تفتحه. كل الكتب اللي بتبدأ بـ "تار-" قدامك في 3 ثواني.
الـ Trie بيشتغل بنفس المنطق بالظبط. كل حرف يبقى عقدة (node)، والعقدة بتشاور على عقد جوّاها بالحروف اللي ممكن تيجي بعدها. لمّا تكتب "تار" في search box، الكود بيمشي 3 خطوات بس في الشجرة، بغض النظر إذا كان الـ dataset 50 ألف ولا 50 مليون.
التعريف العلمي لـ Trie
Trie (تنطق "تراي" أو "تري") اختصار لـ Retrieval Tree، اقترحه Edward Fredkin سنة 1960 في ورقة بعنوان "Trie Memory" في Communications of the ACM. هيكل بيانات شجري كل عقدة فيه بتمثل حرف واحد، والكلمة الكاملة بتتبني من المسار من الجذر للعقدة اللي عليها علامة "نهاية كلمة" (is_end flag).
الخصائص الأساسية:
- كل عقدة عندها dictionary من الأطفال:
{حرف → عقدة}، وعَلَم boolean اسمهis_end. - زمن البحث عن كلمة طولها k حرف هو O(k)، مستقل تماماً عن عدد الكلمات الإجمالي N.
- زمن جلب كل الكلمات اللي بتبدأ بـ prefix طوله p هو O(p + m) حيث m عدد الكلمات المرتجعة.
ده الفرق الجوهري بينه وبين dict العادي: dict بياخد O(k) في الـ hash لكن O(N) لو عايز كل الكلمات اللي بتبدأ بـ prefix معين. على 5 مليون كلمة، الفرق ده بيتحوّل من 1.2 ثانية إلى 300 ميكروثانية.
