Thành thạo Cây tiền tố (Prefix Trees/Tries) trong Ruby: Triển khai & Ứng dụng thực tế

Cây tiền tố (còn gọi là trie) là cấu trúc dữ liệu giúp bạn tổ chức danh sách từ & nhanh chóng tìm các từ bắt đầu bằng tiền tố cụ thể.

Ví dụ, bạn có thể tìm tất cả từ trong từ điển bắt đầu bằng “ca”, như “cat” hoặc “cape”.

Nhìn hình này:

Đây là cây tiền tố.

Bạn có thể đi từ gốc (*) đến node được đánh dấu (như e và t) để tìm từ.

Trong bài viết này bạn sẽ học cách triển khai cây tiền tố riêng trong Ruby & cách dùng nó giải quyết bài toán!

Triển khai Cây tiền tố

Để triển khai trong Ruby tôi quyết định dùng class Node với vài thuộc tính:

• Giá trị (một ký tự)
• Biến “word”. Giá trị true/false cho biết đây có phải từ hợp lệ không
• Mảng “next”. Lưu trữ tất cả ký tự (dưới dạng đối tượng Node) đến sau nó trong cây

Đây là mã:

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

Bây giờ chúng ta cần class giữ node gốc & các phương thức làm việc với node.

Hãy xem class Trie:

class Trie
  def initialize
    @root = Node.new("*")
  end
end

Bên trong class này chúng ta có các phương thức sau:

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

Cả hai phương thức đều chia từ đã cho thành mảng ký tự (dùng phương thức chars).

Sau đó duyệt cây bắt đầu từ gốc & hoặc tìm ký tự hoặc thêm nó.

Đây là các phương thức hỗ trợ (cũng trong class Trie):

def add_character(character, trie)
  trie.find { |n| n.value == character } || add_node(character, trie)
end

def find_character(character, trie)
  trie.find { |n| n.value == character }
end

def add_node(character, trie)
  Node.new(character).tap { |new_node| trie << new_node }
end

Để thêm ký tự chúng ta kiểm tra nếu nó đã tồn tại (dùng find). Nếu có thì trả về node.

Ngược lại tạo mới & trả về node mới.

Sau đó cũng có phương thức include?:

def include?(word)
  find_word(word) { |found, base| return found && base.word }
end

Bây giờ chúng ta sẵn sàng dùng cấu trúc dữ liệu mới & xem có thể làm gì 🙂

Ứng dụng & Ví dụ Trie

Bắt đầu bằng thêm từ vào cây:

trie = Trie.new
trie.add_word("cat")
trie.add_word("cap")
trie.add_word("cape")
trie.add_word("camp")

Bạn có thể kiểm tra từ có trong cây không:

p trie.include?("cape") # true
p trie.include?("ca") # false

Vậy có những dùng途 gì cho cấu trúc này?

• Giải trò chơi từ
• Kiểm tra chính tả (spell checking)
• Tự động hoàn thành (autocomplete)

Bạn sẽ cần từ điển tốt để nạp vào cây.

Tôi tìm thấy những thứ này có thể hữu ích:

• https://raw.githubusercontent.com/first20hours/google-10000-english/master/20k.txt
• https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt

Tìm từ có tiền tố (Prefixed Words)

Trong ví dụ mã trước chúng ta đã triển khai thao tác add & find.

Nhưng chúng ta cũng muốn phương thức find_words_starting_with.

Chúng ta có thể làm điều này dùng thuật toán “Depth First Search” (DFS - Tìm kiếm theo chiều sâu). Chúng ta cũng cần cách theo dõi từ đang xem.

Nhớ rằng node của chúng ta chỉ giữ một ký tự, vì vậy cần tái tạo chuỗi thực bằng cách đi qua cây.

Đây là phương thức làm tất cả:

def find_words_starting_with(prefix)
  stack = []
  words = []
  prefix_stack = []
  stack << find_word(prefix)
  prefix_stack << prefix.chars.take(prefix.size-1)
  return [] unless stack.first
  until stack.empty?
    node = stack.pop
    prefix_stack.pop and next if node == :guard_node
    prefix_stack << node.value
    stack << :guard_node
    words << prefix_stack.join if node.word
    node.next.each { |n| stack << n }
  end
  words
end

Chúng ta dùng hai stack, một theo dõi node chưa thăm (stack) & một theo dõi chuỗi hiện tại (prefix_stack).

Lặp cho đến khi thăm hết node & thêm giá trị node vào prefix_stack. Mỗi node giữ giá trị cho một ký tự, nên cần thu thập ký tự để hình thành từ.

Symbol :guard_node được thêm vào prefix_stack để biết khi nào backtrack (quay lui). Cần thiết để xóa ký tự khỏi buffer (prefix_stack) đúng lúc.

Sau đó nếu node.word true nghĩa là tìm thấy từ hoàn chỉnh & thêm vào danh sách từ.

Ví dụ dùng phương thức này:

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

Nếu không tìm thấy từ bạn nhận mảng rỗng:

t.find_words_starting_with("b") # []

Phương thức này có thể dùng triển khai tính năng autocomplete.

Tóm tắt

Bạn đã học về cây tiền tố (còn gọi là tries), cấu trúc dữ liệu tổ chức danh sách từ thành cây. Bạn có thể truy vấn nhanh cây này để kiểm tra từ hợp lệ & tìm từ chia sẻ cùng tiền tố.

Đừng quên chia sẻ bài viết để nhiều người hơn học hỏi!