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 מבצעות את אותו מעבר בלי ליצור דבר. אם קישור חסר, אף מילה שמורה לא מתחילה באותיות האלה, ולכן שתיהן מחזירות שקר: tex נעצרת בצומת של te, שאין לו קישור ל-x. אם המעבר מגיע לסופו, הצומת שבו הוא מסתיים הוא הקידומת ששאלת עליה. startsWith מחזירה אמת, ו-search מחזירה את ערך הדגל של אותו צומת. הצומת של te קיים, אבל הדגל שלו כבוי, כי המילים שעוברות דרכו מסתיימות בהמשך המסלול. לכן startsWith te מחזירה אמת ו-search te מחזירה שקר.

הדגל הוא שמבדיל בין מילה לקידומת. בדוגמה הראשונה, לאחר הוספת card, המסלול c, a, r קיים. בלי הדגל, search car הייתה מחזירה בטעות אמת. הוספת 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 היא true.
להמשיך לקרוא מעבר לסוף הנתיב. תחילית ארוכה מכל מילה, כמו sunny כששמורה רק sun, חייבת לעצור בקישור הראשון שחסר ולהחזיר false.
להחזיר ערכים בוליאניים או להשמיט הוספות מהתשובה. לכל פעולה יש מחרוזת אחת, כולל "null" עבור הוספה.

שאלות נפוצות4

מהי סיבוכיות הזמן של טרייה?

הפעולות Insert, search ו-startsWith עוקבות כל אחת אחר קישור אחד לכל אות בארגומנט שלהן, ולכן כל אחת מהן דורשת זמן O(L) עבור מילה באורך L, ללא תלות במספר המילים המאוחסנות. ה-trie מכיל לכל היותר צומת אחד לכל אות שהוכנסה, ולכן המקום הנדרש הוא O(T) צמתים עבור T אותיות שהוכנסו בסך הכול, וכל צומת מאחסן עד 26 קישורים לצמתים-ילדים.

למה להשתמש בטרייה במקום בקבוצת גיבוב?

קבוצת גיבוב עונה על חיפושים של מילים שלמות ב־O(L), אבל היא לא יכולה לענות על שאלה לגבי קידומת בלי לסרוק כל מילה. אפשר להוסיף קבוצה שנייה שמכילה כל קידומת של כל מילה, אבל אז מילה בת 20 אותיות תאחסן 20 קידומות, שאורכן הכולל 210 אותיות. טרייה מאחסנת כל קידומת משותפת פעם אחת ועונה על שתי השאלות באותה הליכה. עם 26 משבצות במערך לכל צומת, הליכה מתחת לקידומת פוגשת גם את המילים לפי סדר האותיות, כפי שנדרש להשלמה אוטומטית.

האם צומת בטרייה צריך להשתמש במערך של 26 קישורים או במפת גיבוב?

מערך מספק את חיפוש הצאצאים המהיר ביותר, עם אינדקס אחד לכל אות, אבל כל צומת תופס מקום ל־26 משבצות גם כשהוא משתמש רק באחת. מפה מאחסנת רק את הצאצאים הקיימים ומתאימה לכל אלפבית, במחיר של שלב גיבוב אחד לכל אות. למילים באנגלית באותיות קטנות מתאימות שתי האפשרויות; עבור טקסט Unicode או טריים דלילים, מפה חוסכת הרבה זיכרון.

היכן משתמשים בטריות בפועל?

השלמה אוטומטית והצעות חיפוש עוברות לאורך עץ Trie עד לקידומת שהוקלדה ומציגות את המילים שמתחתיה. בודקי איות, משחקי מילים שמחפשים בלוח מילים מהמילון ונתבים שמוצאים את הקידומת הארוכה ביותר שתואמת לכתובת משתמשים באותו מבנה. בכל פעם שמחרוזות רבות חולקות התחלה ואתם מחפשים לפי התחלה, עץ 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"]