Cây tiền tố trong ruby

Cây tiền tố (prefix tree hay còn gọi là trie) là một cấu trúc dữ liệu giúp bạn tổ chức một danh sách các từ và cho phép tìm kiếm nhanh chóng một từ bắt đầu bằng một tiền tố cụ thể. Ví dụ bạn có thể tìm kiếm tất cả các từ trong từ điển mà bắt đầu bởi ca như cat hay cape. Hãy xem hình mẫu dưới đây: Đây là một cây tiền tố. Chúng ta có thể lần từ root đến các nốt đánh dấu để tìm kiếm từ. Trong bài viết này chúng ta sẽ tìm cách để triển khai cây tiền tố trong ruby và cách sử dụng nó để giải quyết vấn đề.

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

Để triển khai cây tiền tố trong ruby, tôi quyết định sử dụng class Node với một vài thuộc tính sau:

• Giá trị (một kí tự)
• Biến số word. Với giá trị true/false cho chúng ta biết có phải là một từ đúng hay không
• Mảng next. Lưu tất cả các kí tự (là Node) đứng sau đối tượng trong cây tiền tố

Đây là code:

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 một class để giữ gốc (root) và method để làm việc với các node trong cây. Hãy xem class Trie sau đây:

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

Trong class, chúng ta có các method 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ả 2 method để trả về một trong các kí tự của word. Chúng ta sử dụng cây hướng bắt đầu từ root, sau đó có thể tìm kiếm và thêm kí tự vào cây. Sau đây là các method hỗ trợ cho việc tìm kiếm và thêm kí tự.

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

Khi thêm một từ, chúng ta cần kiểm tra xem từ đó đã có trong cây chưa, nếu có rồi thì sẽ return ra node đó, nếu chưa thì tạo và return node mới. Vì vậy chúng ta cần thêm method include?

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

Bây giờ chúng ta đã có thể sử dụng cấu trúc dữ liệu mới, hãy xem chúng ta có thể làm được những gì với nó.

Sử dụng Trie và ví dụ

Chúng ta bắt đầu 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")

Chúng ta có thể check xem từ đó đã tồn tại trong cây hay chưa như sau:

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

Vậy chúng ta có thể ứng dụng cấu trúc trên vào những việc gì?

• Solving word games
• Spell checking
• Autocomplete

Trước hết, chúng ta cần một bộ từ điển tốt để load data cho cây. Sau đây là một số bộ dữ liệu có thể phù hợp:

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

Tìm kiếm prefixed word

Trong đoạn code ví dụ, chúng tôi sẽ cho bạn thấy cách mà trước đây chúng tôi triển khai việc thêm và tìm từ. Chúng tôi cũng sử dụng method find_words_starting_with. Chúng tôi thực hiện bằng cách sử dụng thuật toán DFS.

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 tôi sử dụng 2 ngăn xếp ở đây, 1 để chứa các node chưa được thăm (stack) và 1 để chứa các node hiện tại (prefix_stack). Chúng tôi lặp để thăm tất cả các node và thêm giá trị vào prefix_stack. Mỗi node chứa 1 kí tự và cần tìm các kí tự của một từ. Khi guard_node được thêm vào prefix_stack cho biết thời điểm chúng ta quay ngược lại. Chúng ta cần remove các node không thỏa mãn. Và khi node.word có giá trị true tức là chúng ta đã tìm được từ đầy đủ và thêm từ đó vào danh sách. Ví dụ khi sử dụng method này:

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

t.find_words_starting_with("b")
# []

Chúng ta có thể ứng dụng vào tính năng autocomplete Reference