Cây tiền tố là một cấu trúc dữ liệu được sử dụng để lưu trữ danh sách các từ và giúp cho việc tìm kiếm các từ với một tiền tố cụ thể trở nên nhanh hơn. Ví dụ bạn có thể tìm tất cả những từ trong từ điên của bạn mà bắt đầu với "ca", ví dụ như "cat" hoặc "cape". Để dễ hình dung hơn thì bạn có thể quan sát hình ảnh sau: Hình ảnh trên chính là một cây tiền tố đơn giản. Bạn có thể đi từ nút gốc ( * ) đến những nút được đánh dấu (ví dụ như "e" hoặc "t") để tìm ra những từ thỏa mãn. Những nút đánh dấu này cho biết đấy là kết thúc của một từ hoàn chỉnh.

Implement cây tiền tố

Để implement cây tiền tố với Ruby, tôi sẽ sử dụng class Node (tương ứng với "nút" được nhắc tới bên trên) với một số các thuộc tính sau:

• value:char , thể hiện giá trị của nút
• word:boolean, biến này cho biết nút này có phải là kết thúc của một từ hợp lệ không
• next:array , mảng này sẽ lưu trữ tất cả các ký tự liền sau của nút hiện tại trong một từ và các phần tử của mảng này chính là các object Node

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

Tiếp theo chúng ta sẽ cần một class để thể hiện cây tiền tố và các method thao tác với cây. Ở đây tôi sẽ xây dựng class Trie như sau:

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

2 method rất quan trọng khi thao tác với cây tiền tố đó là thêm một từ vào cây và tìm một từ trong cây.

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ên đều nhận tham số đầu vào là một từ word, sau đó tách chúng ra thành 1 mảng các ký tự bằng method chars . Sau đó chúng ta sẽ duyệt cây tiền tố từ nút gốc theo mảng ký tự vừa nhận được và thực hiện các thao tác tìm ký tự hoặc thêm ký tự. Ngoài ra chúng ta cũng cần thêm một vài method bổ sung 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 1 ký tự vào cây, chúng ta sẽ kiểm tra xem ký tự đó đã tồn tại ở vị trí hiện tại chưa bằng method find (trong mảng next). Nếu đã tồn tại thì ta sẽ trả về nút chứa ký tự đó, trong trường hợp ngược lại thì ta sẽ tạo một nút mới và thêm vào cây. Cuối cùng là method include?

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

Như vậy chúng ta đã hoàn thành việc implement cây tiền tố, trong phần tiếp theo chúng ta sẽ cùng sử dụng nó cho một vài ví dụ

Sử dụng cây tiền tố và các ví dụ

Hãy bắt đầu bằng việc tạo mới 1 cây tiền tố và thêm một vài 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 xem một từ có tồn tại trong cây không bằng method include? đã được implement phía trên

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

Cây tiền tố trên có thể rất hữu ích trong một số bài toán sau:

• Giải quyết các trò chơi chữ
• Kiểm tra lỗi chính tả
• Chức năng Autocomplete

Tất nhiên chúng ta sẽ phải một bộ từ điển tốt để import vào cây tiền tố trên. Tuy nhiên bạn cũng không cần phải quá lo lắng vì tôi đã tìm được một số bộ từ điển khá hữu ích như dưới đây:

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

Tìm các từ với tiền tố xác định

Để giải quyết bài toán này, tôi sẽ phải implement thêm method find_words_starting_with Với method này, tôi sẽ sử dụng thuật toán khá quen thuộc đó là duyệt theo chiều sâu (Depth First Search - 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 ta sẽ sử dụng 2 stack, một để theo dõi các nút chưa được thăm (stack) và stack còn lại để theo dõi chuỗi hiện tại (prefix_stack) Việc lặp sẽ được thực hiện tới khi chúng ta đã duyệt hết tất cả các nút và thêm chúng vào prefix_stack. Mỗi một nút chỉ chứa giá trị của 1 ký tự, vậy nên chúng ta sẽ phải ghép các nút lại với nhau để tạo thành một từ hợp lệ. Symbol :guard_node được thêm vào prefix_stack để giúp chúng ta biết được khi nào chúng ta đang quay lại và cần loại bỏ đi những ký tự từ prefix_stack ngay lập tức. Sau đó, nếu gặp một nút được đánh dấu (node.word là true) thì điều đó có nghĩa là chúng ta đã tìm được một từ hợp lệ, công việc rất đơn giản là thêm từ này vào mảng kết quả words

Ví dụ về việc sử dụng:

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

Nếu không tìm được từ nào thỏa mãn thì kết quả trả về sẽ là một mảng rỗng

t.find_words_starting_with("b")
 
# []

Summary

Bài viết của tôi đến đây là kết thúc. Trong bài viết này, tôi đã giới thiệu với các bạn về việc implement một cấu trúc dữ liệu rất hữu ích đó là cây tiền tố cũng như những ứng dụng của nó. Cảm ơn các bạn đã theo dõi.

Bài viết được dịch từ http://www.rubyguides.com/2017/11/prefix-trees-in-ruby/