เชี่ยวชาญ Prefix Trees (Tries) ใน Ruby: Implementation & Practical Uses

Prefix tree (Trie) = data structure จัดระเบียบ word list หาคำที่ขึ้นต้นด้วย prefix เร็ว (เช่น "ca" → "cat", "cape")

Prefix Tree Implementation

Node class: value (char), word (true/false = valid word), next (array ของ Node ถัดไป)

class Node
  attr_reader :value, :next
  attr_accessor :word
  def initialize(value)
    @value = value; @word = false; @next = []
  end
end

Trie class จัดการ root node และ operations:

class Trie
  def initialize; @root = Node.new("*"); end
  def add_word(word)
    letters = word.chars; base = @root
    letters.each { |letter| base = add_character(letter, base.next) }
    base.word = true
  end
  def find_word(word)
    letters = word.chars; base = @root
    word_found = letters.all? { |letter| base = find_character(letter, base.next) }
    yield word_found, base if block_given?
    base
  end
  # helper methods: add_character, find_character, add_node, include?
end

Trie Uses & Examples

ใช้งาน:

trie = Trie.new
trie.add_word("cat"); trie.add_word("cap"); trie.add_word("cape"); trie.add_word("camp")
trie.include?("cape")  # true
trie.include?("ca")    # false

Use cases: Word games, Spell checking, Autocomplete ต้องมี dictionary ดี (ลิงก์ในบทความ)

Finding Prefixed Words

find_words_starting_with ใช้ DFS algorithm ต้อง reconstruct string จาก nodes (แต่ละ node = 1 char) ใช้ 2 stacks: nodes stack และ prefix_stack (string buffer) มี :guard_node สำหรับ backtracking

t.find_words_starting_with("cap")  # ["cap", "cape"]
t.find_words_starting_with("b")    # []

ประยุกต์ทำ autocomplete feature

Summary

Prefix trees (tries) จัดระเบียบคำเป็นต้นไม้ Query เร็ว: ตรวจสอบคำถูกต้อง, หาคำที่ share prefix เหมือนกัน