المستوى المطلوب: مبتدئ
لو الـ search box في موقعك بياخد 80ms يكمل كلمة على قاموس فيه 100 ألف كلمة، المشكلة مش في السيرفر ولا في الـ CPU. المشكلة إنك بتدور سطر بسطر، والحل اسمه Trie. سطر واحد بيخلي الزمن دا ينزل لأقل من 1ms، حتى لو القاموس وصل لمليون كلمة.
Trie: الـ Data Structure اللي بتشغّل الـ Autocomplete
المشكلة باختصار
تخيّل عندك ليست فيها 100,000 كلمة، والمستخدم كاتب 3 حروف "برم". أنت عايز ترجّعله أول 10 كلمات بتبدأ بـ "برم". الطريقة الساذجة: لف على كل الكلمات وشوف اللي بيبدأ بالـ prefix دا. ده O(n)، وعلى 100K كلمة بياخد فعلياً 80–120ms في Python على لابتوب عادي. كل ما المستخدم يكتب حرف، السيرفر بيتحرق من الأول.
المثال البسيط: دفتر التليفون القديم
افتكر دفتر التليفون اللي كان عند جدك. مش كان مرتب أبجدياً وعلى الجنب فيه ألسنة بحروف؟ لو عايز رقم اسمه "محمد"، مكنتش بتقرا الدفتر من أوله. كنت بتفتح على لسان حرف "م" مباشرة، بعد كده تنزل عند "مح"، وبعدها "محم". الـ Trie هي نفس الفكرة بالظبط: شجرة كل عقدة فيها حرف، والمسار من الجذر للورقة بيكوّن كلمة كاملة.
لما المستخدم يكتب "برم"، إنت ما بتلفش على 100,000 كلمة. إنت بتنزل 3 خطوات في الشجرة بس: ب → ر → م. وبعدها بتاخد كل الكلمات اللي تحت العقدة دي. الزمن بيعتمد على طول الـ prefix فقط، يعني O(L) حيث L = عدد حروف الـ prefix. وده ثابت تقريباً.
التعريف العلمي الدقيق
الـ Trie (نُطقها "تراي" من كلمة retrieval) هي شجرة k-ary موجّهة، كل عقدة فيها بتمثّل حرف واحد، وكل مسار من الجذر لعقدة معيّنة بيمثّل prefix. العقدة بتحتوي عادة على:
- children: dictionary أو array من العقد الأبناء، مفتاحها الحرف.
- is_end: علامة بتقول إن المسار للعقدة دي كلمة كاملة (مش مجرد prefix).
الورقة الأصلية للفكرة دي نشرها René de la Briandais سنة 1959، وطوّرها Edward Fredkin سنة 1960 وسمّاها Trie. التعقيد الزمني للبحث والإدخال هو O(L)، والتعقيد المكاني في أسوأ الحالات هو O(n × L × Σ) حيث Σ هي حجم الأبجدية.
الكود الشغّال في 50 سطر Python
class TrieNode:
__slots__ = ("children", "is_end")
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def _walk_to(self, prefix: str):
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return node
def starts_with(self, prefix: str, limit: int = 10):
node = self._walk_to(prefix)
if node is None:
return []
results = []
stack = [(node, prefix)]
while stack and len(results) < limit:
cur, path = stack.pop()
if cur.is_end:
results.append(path)
for ch, child in cur.children.items():
stack.append((child, path + ch))
return results
if __name__ == "__main__":
trie = Trie()
for w in ["برمجة", "برنامج", "برسم", "بريد", "محمد", "محاسبة"]:
trie.insert(w)
print(trie.starts_with("بر", limit=5))