Học cách triển khai và sử dụng cây tiền tố trong Ruby

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

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

Nhìn vào hình ảnh này:

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

Bạn có thể theo dõi từ thư mục gốc (* ) đến một nút đượ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ố của riêng bạn trong Ruby và cách sử dụng nó để giải quyết vấn đề!

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

Để thực hiện điều này trong Ruby, tôi quyết định sử dụng Node lớp có một số thuộc tính:

• Giá trị (một ký tự)
• Biến "từ". Giá trị true / false cho bạn biết đây có phải là từ hợp lệ không
• Mảng "tiếp theo". Điều này lưu trữ tất cả các ký tự (dưới dạng Node vật thể) xuất hiện sau vật thể này trên 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 một lớp để giữ nút gốc và các phương thức để làm việc với các nút này.

Hãy xem Trie lớp:

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

Bên trong lớp 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 pháp chia nhỏ một từ nhất định thành một mảng ký tự (sử dụng các ký tự chars phương pháp).

Sau đó, chúng tôi điều hướng cây bắt đầu từ gốc và tìm một ký tự hoặc thêm nó.

Dưới đây là các phương pháp hỗ trợ (cũng có trong Trie lớp):

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 một ký tự, chúng tôi kiểm tra xem nó đã tồn tại chưa (sử dụng find phương pháp). Nếu đúng thì chúng tôi trả về nút.

Nếu không, chúng tôi tạo nó và trả về nút mới.

Sau đó, chúng tôi cũng có include? phương pháp:

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

Bây giờ chúng tôi đã sẵn sàng để bắt đầu sử dụng cấu trúc dữ liệu mới của mình và xem chúng tôi có thể làm gì với nó 🙂

Sử dụng Trie &Ví dụ

Hãy bắt đầu bằng cách thêm một số từ vào cây của chúng ta:

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ó được bao gồm trong cây như thế này không:

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

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

Vì vậy, một số công dụng cho cấu trúc dữ liệu này là gì?

• Giải các trò chơi đố chữ
• Kiểm tra chính tả
• Tự động hoàn thành

Bạn sẽ cần một từ điển tốt để tải vào cây của mình.

Tôi thấy những điều này có thể hữu ích cho bạn:

• 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ừ có tiền tố

Vì vậy, trong ví dụ mã mà tôi đã cho bạn thấy trước khi chúng tôi triển khai add &find hoạt động.

Nhưng chúng tôi cũng muốn có find_words_starting_with phương pháp.

Chúng tôi có thể làm điều này bằng cách sử dụng thuật toán "Tìm kiếm đầu tiên theo chiều sâu" (DFS). Chúng tôi cũng cần một cách để theo dõi từ chúng tôi đang xem.

Hãy nhớ rằng mỗi nút của chúng ta chỉ có một ký tự, vì vậy chúng ta cần tạo lại các chuỗi thực tế bằng cách đi qua cây.

Đây là một phương pháp thực hiện tất cả những điều đó :

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 hai ngăn xếp ở đây, một ngăn xếp để theo dõi các nút chưa được truy cập (stack ) và một chuỗi khác để theo dõi chuỗi hiện tại (prefix_stack ).

Chúng tôi lặp lại cho đến khi chúng tôi đã truy cập tất cả các nút và thêm giá trị của nút vào prefix_stack . Mỗi nút chỉ giữ giá trị cho một ký tự, vì vậy chúng ta cần thu thập các ký tự này để tạo thành một từ.

:guard_node biểu tượng được thêm vào prefix_stack vì vậy chúng tôi biết khi nào chúng tôi quay trở lại. Chúng tôi cần điều này để xóa các ký tự khỏi bộ đệm chuỗi của chúng tôi (prefix_stack ) vào đúng thời điểm.

Sau đó, nếu node.word là đúng, điều đó có nghĩa là chúng tôi đã tìm thấy một từ đầy đủ và chúng tôi thêm nó vào danh sách các từ của mình.

Ví dụ về việc sử dụng phương pháp này :

t.find_words_starting_with("cap")

# ["cap", "cape"]

Nếu không tìm thấy từ nào, bạn sẽ nhận được một mảng trống:

t.find_words_starting_with("b")

# []

Phương pháp này có thể được sử dụng để triển khai tính năng tự động hoàn thành.

Tóm tắt

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

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