Implement Trie (Prefix Tree)

Q: لماذا نستخدم شجرة بادئة بدلًا من مجموعة تجزئة؟

تجيب مجموعة التجزئة عن عمليات البحث عن الكلمات الكاملة في O(L) ، لكنها لا تستطيع الإجابة عن سؤال البادئة دون فحص كل كلمة. يمكنك إضافة مجموعة ثانية تحتوي على كل بادئة لكل كلمة، لكن كلمة مكوّنة من 20 حرفًا ستخزّن عندئذٍ 20 بادئة بإجمالي 210 أحرف بينها. تخزّن شجرة البادئات كل بادئة مشتركة مرة واحدة، وتجيب عن كلا السؤالين باتباع المسار نفسه. ومع وجود 26 خانة مصفوفة لكل عقدة، فإن السير أسفل بادئة يمر أيضًا بالكلمات بترتيب الحروف، وهذا ما تحتاج إليه ميزة الإكمال التلقائي.

متوسطشجرة البادئات

+10

تخزّن شجرة البادئات، أو شجرة البادئة، الكلمات بحيث تكون الاستفسارات عن بداياتها سريعة. أنشئ واحدة للكلمات ذات الأحرف الصغيرة بثلاث عمليات: تضيف insert w الكلمة w، وتُخبرك search w ما إذا كانت w نفسها قد أُضيفت، وتُخبرك startsWith p ما إذا كانت هناك كلمة مُضافة تبدأ بـ p. تُعد الكلمة بادئةً لنفسها.

تتلقى العمليات بالترتيب في ops، وwords[i] هي الكلمة أو البادئة الخاصة بـ ops[i]. نفّذها على شجرة بادئات واحدة تبدأ فارغة، وأعِد سلسلة واحدة لكل عملية: "null" للإضافة، و"true" أو "false" للبحث أو startsWith.

الدالة

trieOps(ops: string-array, words: string-array) → string-array

opsstring-array: العمليات، بالترتيب الذي تُنفَّذ به
wordsstring-array: الكلمة أو البادئة لكل عملية
تُرجعstring-array: إجابة واحدة لكل عملية، كنص

القيود

1 ≤ ops.length ≤ 2000
words.length == ops.length
كل ops[i] هي insert أو search أو startsWith.
1 ≤ words[i].length ≤ 20
words[i] يحتوي على أحرف إنجليزية صغيرة فقط.

أمثلة

المدخلات: ops = ["insert", "search", "startsWith", "insert", "search"]words = ["card", "car", "car", "car", "car"]
المخرجات: ["null", "false", "true", "null", "true"]
الشرح: في البداية، لا تُخزَّن سوى card، لذا فإن البحث عن car يُرجع "false": فلم تُدرَج قط بوصفها كلمة. إنها بداية card، لذا يُرجع startsWith car القيمة "true". بعد إدراج car، يعثر البحث عليها.

المدخلات: ops = ["insert", "insert", "startsWith", "search", "startsWith", "search", "startsWith"]words = ["tea", "ten", "te", "te", "tex", "ten", "tea"]
المخرجات: ["null", "null", "true", "false", "false", "true", "true"]
الشرح: تبدأ كلتا الكلمتين بـ te، لذا فإن startsWith te هي "true"، لكن لا توجد كلمة تساوي te تمامًا، لذا يفشل البحث. لا تبدأ أي كلمة بـ tex. أُدرجت ten، وtea بادئة لنفسها، لذا فإن الإجابتين الأخيرتين هما "true".

المدخلات: ops = ["search", "startsWith", "insert", "search", "startsWith", "startsWith"]words = ["dog", "d", "dog", "dog", "dogs", "do"]
المخرجات: ["false", "false", "null", "true", "false", "true"]
الشرح: تبدأ شجرة البادئات فارغة، لذا تكون الإجابتان الأوليان "false". بعد إدراج dog، يعثر البحث عليه، ولا تبدأ أي كلمة بـ dogs، كما أن do هي بداية dog.

+16 اختبارات مخفية عند الإرسال

سؤال إضافي

كيف ستضيف عملية countPrefix p تُرجع عدد الكلمات المخزّنة المميّزة التي تبدأ بـ p، مع الحفاظ على زمن تنفيذ O(L)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تُجيب مجموعة التجزئة عن search فورًا، لكن startsWith يسأل عن كل كلمة تبدأ بطريقة معيّنة، والمجموعة لا مفهوم لديها عن البدايات. تخزّن الشجرة البادئات نفسها: فكل كلمة عبارة عن مسار من الحروف يبدأ من الجذر، والكلمات التي تبدأ بالطريقة نفسها تتشارك بداية مسارها، وتُشير علامة على إحدى العقد إلى موضع انتهاء كلمة مخزّنة. عندئذٍ تتطلّب الإجابة عن كلا السؤالين اجتياز مسار واحد لا يتجاوز L وصلة، حيث إن L هو طول الاستعلام، مهما كان عدد الكلمات المخزّنة.

احتفِظ بقائمة من الكلمات وافحصها

الفكرة

احتفِظ بكل كلمة مُدخلة في قائمة. بالنسبة إلى search w، قارن w بكل كلمة مخزّنة. بالنسبة إلى startsWith p، تحقّق مما إذا كانت أي كلمة مخزّنة تبدأ بـ p. في المثال الثاني، يفحص startsWith te كلمة tea أولًا ويتوقف عندها؛ أما startsWith tex فعليه فحص الكلمتين قبل أن يجيب "false".

هذا صحيح، وضمن الحدود هنا ينتهي، لكن كل استعلام يتطلب فحص كل كلمة مخزّنة. عند تخزين n كلمات، قد يتطلب الاستعلام ما يصل إلى n مقارنات، يصل طول كل منها إلى L حرفًا. إن تخزين 1,000 كلمة وإجراء 1,000 استعلام يعني مليون مقارنة بين السلاسل النصية، ويستمر العمل في الازدياد مع حجم القاموس. ولا يوجد شيء مشترك أيضًا: إذ تخزّن كل من tea وten الحرفين t وe خاصين بها.

الخوارزمية

ابدأ بقائمة كلمات فارغة.
عند insert w: أضف w إلى القائمة.
عند search w: أعد ما إذا كانت هناك كلمة مخزنة تساوي w.
عند startsWith p: أعد ما إذا كانت هناك كلمة مخزنة تبدأ بـ p.
سجّل كل إجابة كنص وأعِد القائمة.

def trieOps(ops, words):
    stored = []
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            stored.append(word)
            result.append("null")
        elif op == "search":
            found = any(s == word for s in stored)
            result.append("true" if found else "false")
        else:
            found = any(s.startswith(word) for s in stored)
            result.append("true" if found else "false")
    return result

شجرة البادئات: روابط الأبناء وعلامة النهاية

الفكرة

تمثّل كل عقدة في شجرة البادئات بادئةً واحدة: الأحرف الموجودة على المسار من الجذر إليها. يمثّل الجذر البادئة الفارغة. تحتوي العقدة على شيئين: رابطًا لكل حرف يمكن أن يأتي تاليًا (مصفوفة من 26 خانة، أو خريطة من الحرف إلى العقدة) وعلامة isEnd تشير إلى ما إذا كانت كلمة مخزّنة تنتهي عند هذه العقدة تمامًا.

تسير insert عبر الكلمة بدءًا من الجذر. تتبع لكل حرف رابط الابن، وتنشئ العقدة أولًا إذا كان الرابط مفقودًا، وعند الحرف الأخير تضبط isEnd. في المثال الثاني، يؤدي إدراج tea إلى إنشاء العقد للأحرف t وte وtea ووضع علامة على tea. أما إدراج ten فيعيد استخدام t وte ويضيف ten فقط. تشترك الكلمتان في المسار الخاص بـ te، ومن هنا جاءت تسمية شجرة البادئات.

تسلك search وstartsWith المسار نفسه من دون إنشاء أي شيء. إذا كان أحد الروابط مفقودًا، فهذا يعني أن لا كلمة مخزّنة تبدأ بتلك الأحرف، لذا تعيد كلتاهما false: تتوقف tex عند العقدة الخاصة بـ te، التي لا تملك رابطًا لـ x. إذا وصلت عملية السير إلى النهاية، فالعقدة التي تقف عندها هي البادئة التي سألت عنها. تعيد startsWith القيمة true، بينما تعيد search قيمة العلامة الخاصة بتلك العقدة. العقدة الخاصة بـ te موجودة، لكن علامتها غير مفعّلة، لأن الكلمات التي تمر عبرها تنتهي في مستوى أدنى. لذا فإن startsWith te تعيد true، وsearch te تعيد false.

العلامة هي ما يميّز الكلمة عن البادئة. في المثال الأول، بعد إدراج card يصبح المسار c, a, r موجودًا. ومن دون العلامة، كانت search car ستعيد true خطأً. لا يؤدي إدراج car لاحقًا إلى إنشاء أي عقدة؛ بل يقتصر الأمر على تفعيل العلامة.

يتبع كل إجراء L رابطًا على الأكثر، حيث إن L هو طول الكلمة، لذا تبلغ كلفته O(L) مهما كان عدد الكلمات المخزّنة. تحتوي شجرة البادئات على عقدة واحدة لكل بادئة متميزة، ولا يتجاوز عددها مطلقًا العدد الإجمالي للأحرف المُدرجة.

الخوارزمية

عرّف عقدة بروابط إلى الأبناء (26 خانة أو خريطة) وعلامة isEnd، وأنشئ جذرًا فارغًا.
بالنسبة إلى insert w: ابدأ من الجذر، واتبع الرابط الخاص بكل حرف من w، وأنشئ عقدة إذا كان الرابط مفقودًا. اضبط isEnd في العقدة الأخيرة.
اكتب دالة مساعدة find(p): ابدأ من الجذر، واتبع الرابط الخاص بكل حرف من p، وتوقّف فورًا إذا كان أحدها مفقودًا. أعد العقدة التي وصلت إليها.
بالنسبة إلى search w: أجب بـ true عندما تصل find(w) إلى عقدة تم ضبط isEnd فيها.
بالنسبة إلى startsWith p: أجب بـ true عندما تصل find(p) إلى عقدة.
نفّذ العمليات بالترتيب، وسجّل "null" أو "true" أو "false" لكل منها.

class TrieNode:
    def __init__(self):
        self.children = {}   # letter -> TrieNode
        self.is_end = False  # does a stored word end at this node?


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        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 _find(self, prefix):
        # Follow the letters from the root; None as soon as a link is missing.
        node = self.root
        for ch in prefix:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None


def trieOps(ops, words):
    trie = Trie()
    result = []
    for op, word in zip(ops, words):
        if op == "insert":
            trie.insert(word)
            result.append("null")
        elif op == "search":
            result.append("true" if trie.search(word) else "false")
        else:
            result.append("true" if trie.starts_with(word) else "false")
    return result

أخطاء شائعة وحالات حدّية

تنشأ معظم الأخطاء من الخلط بين «تنتهي الكلمة هنا» و«تمرّ كلمة من هنا».

جعل search تُرجع true كلما كان المسار موجودًا. بعد إدراج card، يكون مسار car موجودًا، لكن car لم تُدرج قط.
تعيين isEnd على العُقد الجديدة فقط. عند إدراج card بعد cards، لا يُنشأ شيء، ومع ذلك تظل العُقدة الأخيرة بحاجة إلى علامتها.
إنشاء ابن جديد حتى عندما يكون الرابط موجودًا. يؤدي ذلك إلى قطع كل ما هو مخزّن تحته: فإدراج ten بعُقدة t جديدة يُفقد tea.
نسيان أن الكلمة بادئة لنفسها. بعد إدراج tea، تكون startsWith tea صحيحة.
تجاوز نهاية المسار. يجب أن تتوقف البادئة الأطول من كل الكلمات، مثل sunny عندما تكون sun وحدها مخزّنة، عند أول رابط مفقود وتُرجع false.
إرجاع قيم منطقية أو إغفال عمليات الإدراج من الإجابة. لكل عملية سلسلة نصية واحدة، بما في ذلك "null" لعملية الإدراج.

أسئلة شائعة4

ما هو التعقيد الزمني لشجرة البادئات (Trie)؟

تتبع كل من insert وsearch وstartsWith رابطًا واحدًا لكل حرف من وسيطها، لذا يستغرق كل منها زمنًا قدره O(L) لكلمة طولها L، بصرف النظر عن عدد الكلمات المخزنة. تحتوي شجرة البادئات على عقدة واحدة كحد أقصى لكل حرف مُدرج، لذا يكون استهلاك المساحة O(T) من العقد، حيث يمثّل T إجمالي عدد الأحرف المُدرجة، وتخزّن كل عقدة ما يصل إلى 26 رابطًا للأبناء.

لماذا نستخدم شجرة بادئة بدلًا من مجموعة تجزئة؟

تجيب مجموعة التجزئة عن عمليات البحث عن الكلمات الكاملة في O(L)، لكنها لا تستطيع الإجابة عن سؤال البادئة دون فحص كل كلمة. يمكنك إضافة مجموعة ثانية تحتوي على كل بادئة لكل كلمة، لكن كلمة مكوّنة من 20 حرفًا ستخزّن عندئذٍ 20 بادئة بإجمالي 210 أحرف بينها. تخزّن شجرة البادئات كل بادئة مشتركة مرة واحدة، وتجيب عن كلا السؤالين باتباع المسار نفسه. ومع وجود 26 خانة مصفوفة لكل عقدة، فإن السير أسفل بادئة يمر أيضًا بالكلمات بترتيب الحروف، وهذا ما تحتاج إليه ميزة الإكمال التلقائي.

هل ينبغي أن تستخدم عقدة في شجرة البادئات مصفوفة من 26 رابطًا أم خريطة تجزئة؟

توفّر المصفوفة أسرع طريقة للبحث عن الأبناء، بفهرس واحد لكل حرف، لكن كل عقدة تتحمّل تكلفة 26 خانة حتى عندما تستخدم خانة واحدة. تخزّن الخريطة الأبناء الموجودين فقط وتعمل مع أي أبجدية، مقابل تكلفة خطوة تجزئة لكل حرف. بالنسبة إلى الكلمات الإنجليزية المكتوبة بأحرف صغيرة، كلا الخيارين مناسب؛ أما مع النصوص التي تتضمن محارف Unicode أو أشجار البادئات المتفرقة، فتوفّر الخريطة الكثير من الذاكرة.

أين تُستخدم أشجار المحاولات عمليًا؟

تتبع الإكمال التلقائي واقتراحات البحث بنيةَ الشجرة (trie) حتى تصل إلى البادئة المكتوبة، ثم تعرض الكلمات المتفرعة منها. وتستخدم المدققات الإملائية وألعاب الكلمات التي تبحث في لوحة عن كلمات القاموس والموجّهات التي تعثر على أطول بادئة مطابقة للعنوان البنية نفسها. كلما تشاركت سلاسل كثيرة بداياتٍ واستعلمتَ عنها بحسب بداياتها، كانت شجرة البادئات مناسبة.

Python

def trieOps(ops, words):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

ops = ["insert", "search", "startsWith", "insert", "search"]
words = ["card", "car", "car", "car", "car"]

المتوقع

["null", "false", "true", "null", "true"]