Trie — พื้นฐาน & แนวคิด

Trie (อ่านว่า ไทร มาจากคำว่า reTRIEval) หรือ Prefix Tree (ต้นไม้คำนำหน้า) คือ data structure รูป tree (ต้นไม้) ที่ออกแบบมาเพื่อเก็บชุดของ string (คำ) โดยเฉพาะ จุดเด่นคือคำที่ขึ้นต้นเหมือนกันจะ share เส้นทางร่วมกัน ทำให้ search คำหรือ search ว่ามีคำไหนขึ้นต้นด้วย prefix (คำนำหน้า) ที่กำหนดได้เร็วมาก เหมาะกับงานอย่าง autocomplete และตรวจตัวสะกด

Trie หน้าตาเป็นยังไง

ลองนึกภาพว่าเราเก็บคำว่า cat, car, card ถ้าเก็บเป็น array (ลิสต์) ธรรมดา การ search ว่ามีคำที่ขึ้นต้นด้วย ca ไหมต้อง iterate (วน) ดูทุกคำ แต่ใน trie เราแตกคำออกเป็นตัวอักษรทีละตัว แล้วให้ตัวอักษรที่เหมือนกันตอนต้น share node (โหนด) ร่วมกัน หน้าตาจะเป็นแบบนี้

(root)
   |
   c
   |
   a
  / \
 t   r        <- cat, car จบตรงนี้
      \
       d      <- card จบตรงนี้

แต่ละ node เก็บสองอย่าง หนึ่งคือ children (โหนดลูก) ซึ่งเป็น hash map (dict) ที่ map จากตัวอักษรไปยัง child node และสองคือ flag บอกว่ามีคำจบตรงนี้ไหม (is_end) เหตุที่ต้องมี flag จบคำ เพราะ car เป็นทั้งคำจริง และเป็น prefix ของ card เราต้องแยกให้ออกว่า node ตัว r นั้นเป็นจุดจบคำจริง ๆ ไม่ใช่แค่ทางผ่าน

โครง TrieNode ใน Python

class TrieNode:
    def __init__(self):
        self.children = {}     # dict: ตัวอักษร -> TrieNode ลูก
        self.is_end = False    # True ถ้ามีคำจบที่ node นี้

# การ insert คำ: ไล่ทีละตัวอักษร ถ้ายังไม่มีเส้นทางก็สร้าง node ใหม่
def insert(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            node.children[ch] = TrieNode()
        node = node.children[ch]
    node.is_end = True   # ปักธงว่าคำจบที่นี่

ต้นทุนของแต่ละ operation

operation หลักคือ insert (เพิ่มคำ) และ search (ค้นคำ) ทั้งคู่ทำงานโดย traverse (เดินไล่) ตัวอักษรทีละตัวจาก root (ราก) ลงไป จึงใช้เวลาแค่ O(L) เมื่อ L คือความยาวของคำ ไม่ขึ้นกับจำนวนคำทั้งหมดที่เก็บไว้ นี่คือเหตุผลที่ trie เร็วกว่าการ iterate array ทีละคำ