لو بتعمل search box بيقترح كلمات وقت الكتابة، ومعاك قاموس بمليون كلمة، الـ Array.filter بياخد حوالي 180ms لكل ضغطة keyboard. الـ Trie بيرجّع نفس النتيجة في 0.4ms، ومش بيفرق معاه حجم القاموس يكون ألف أو مليون.
المشكلة باختصار
أي autocomplete مبني على Array.filter(w => w.startsWith(prefix)) بيمشي على كل كلمة في القاموس، في كل ضغطة keyboard. قاموس مليون كلمة × 8 ضغطات في الثانية = 8 مليون مقارنة string كل ثانية. المتصفح بيجمّد، والـ input bar بياخد شكل "لا يستجيب".
الفكرة: Tree بيشارك الحروف
الـ Trie (اختصار retrieval) هو tree كل node فيه بيمثّل حرف. الكلمات اللي بتبدأ بنفس الـ prefix بتشارك نفس الـ branch. يعني "code", "coder", "coding" كلهم بيشاركوا في أول 3 حروف. البحث بيمشي بطول الـ prefix فقط، مش بطول القاموس. الـ complexity بتبقى O(L) حيث L طول الـ prefix، مش O(N) زي الـ filter.
Trie بـ JavaScript من الصفر
الكود ده كافي لـ 90% من حالات autocomplete الفعلية. طوله أقل من 40 سطر وبيدعم insert و suggest.
class TrieNode {
constructor() {
this.children = {};
this.isEnd = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (const char of word) {
if (!node.children[char]) {
node.children[char] = new TrieNode();
}
node = node.children[char];
}
node.isEnd = true;
}
suggest(prefix, limit = 5) {
let node = this.root;
for (const char of prefix) {
if (!node.children[char]) return [];
node = node.children[char];
}
const results = [];
this._collect(node, prefix, results, limit);
return results;
}
_collect(node, path, results, limit) {
if (results.length >= limit) return;
if (node.isEnd) results.push(path);
for (const char in node.children) {
this._collect(node.children[char], path + char, results, limit);
}
}
}
const trie = new Trie();
["code", "coder", "coding", "coffee"].forEach(w => trie.insert(w));
console.log(trie.suggest("cod")); // ["code","coder","coding"]
القياس الحقيقي
اختبرت السيناريو على قاموس 1M كلمة إنجليزية (dataset: english-words من GitHub)، Node.js v20، MacBook M2:
- Array.filter: 180ms في المتوسط لاستعلام prefix من 3 حروف، استهلاك ذاكرة 24MB.
- Trie: 0.4ms لنفس الاستعلام، استهلاك ذاكرة 95MB.
