Ruby에서 접두사 트리를 구현하고 사용하는 방법 배우기

접두사 트리(트라이라고도 함)는 단어 목록을 구성하고 특정 접두사로 시작하는 단어를 빠르게 찾는 데 도움이 되는 데이터 구조입니다.

예를 들어, "cat" 또는 "cape"와 같이 "ca"로 시작하는 모든 단어를 사전에서 찾을 수 있습니다.

이 사진을 보세요:

이것은 접두사 트리입니다.

루트(* ) 표시된 노드(예:e 및 t ) 단어를 찾습니다.

이 기사에서는 Ruby에서 고유한 접두사 트리를 구현하는 방법과 이를 사용하여 문제를 해결하는 방법을 배울 것입니다!

접두사 트리 구현

Ruby에서 이것을 구현하기 위해 Node를 사용하기로 결정했습니다. 몇 가지 속성을 가진 클래스:

값(1자)
"단어" 변수. 이것이 유효한 단어인지 알려주는 참/거짓 값
"다음" 배열. 이것은 모든 문자를 저장합니다(Node로 트리에서 이 개체 다음에 오는 개체)

코드는 다음과 같습니다. :

class Node
  attr_reader   :value, :next
  attr_accessor :word

  def initialize(value)
    @value = value

    @word  = false
    @next  = []
  end
end

이제 루트 노드를 보유할 클래스와 이러한 노드로 작업하기 위한 메서드가 필요합니다.

Trie를 살펴보겠습니다. 클래스:

class Trie
  def initialize
    @root = Node.new("*")
  end
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

두 방법 모두 주어진 단어를 문자 배열로 나눕니다(chars 방법).

그런 다음 루트에서 시작하여 트리를 탐색하고 문자를 찾거나 추가합니다.

다음은 지원 방법입니다(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

시도

문자를 추가하기 위해 이미 존재하는지 확인합니다(find 사용 방법). 그렇다면 노드를 반환합니다.

그렇지 않으면 생성하고 새 노드를 반환합니다.

그런 다음 include?도 있습니다. 방법:

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

이제 우리는 새로운 데이터 구조를 사용하기 시작할 준비가 되었고 우리가 그것으로 무엇을 할 수 있는지 볼 준비가 되었습니다 🙂

사용 및 예시

트리에 몇 가지 단어를 추가하는 것으로 시작하겠습니다.

trie = Trie.new

trie.add_word("cat")
trie.add_word("cap")
trie.add_word("cape")
trie.add_word("camp")

다음과 같이 트리에 단어가 포함되어 있는지 확인할 수 있습니다.

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

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

그렇다면 이 데이터 구조의 용도는 무엇입니까?

단어 게임 해결
맞춤법 검사
자동 완성

트리에 로드하려면 좋은 사전이 필요합니다.

귀하에게 유용할 수 있는 다음 항목을 찾았습니다.

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

접두어 찾기

따라서 add를 구현하기 전에 보여드린 코드 예제에서 &find 작업.

하지만 find_words_starting_with도 필요합니다. 방법.

DFS(Depth First Search) 알고리즘을 사용하여 이 작업을 수행할 수 있습니다. 또한 우리가 보고 있는 단어를 추적할 수 있는 방법이 필요합니다.

노드에는 각각 하나의 문자만 있으므로 트리 위를 걸어가며 실제 문자열을 재구성해야 합니다.

이 모든 작업을 수행하는 방법은 다음과 같습니다. :

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

여기서는 두 개의 스택을 사용합니다. 하나는 방문하지 않은 노드를 추적하기 위한 것입니다(stack ) 및 현재 문자열을 추적하는 다른 것(prefix_stack ).

모든 노드를 방문할 때까지 반복하고 노드의 값을 prefix_stack에 추가합니다. . 각 노드는 하나의 문자에 대한 값만 보유하므로 단어를 구성하려면 이러한 문자를 수집해야 합니다.

:guard_node 기호가 prefix_stack에 추가됩니다. 그래서 우리는 우리가 언제 역추적하는지 압니다. 문자열 버퍼(prefix_stack)에서 문자를 제거하려면 이것이 필요합니다. ) 적시에.

그렇다면 node.word 사실이라면 전체 단어를 찾아서 단어 목록에 추가한다는 의미입니다.

이 방법 사용의 예 :

t.find_words_starting_with("cap")

# ["cap", "cape"]

단어가 발견되지 않으면 빈 배열이 표시됩니다.

t.find_words_starting_with("b")

# []

이 방법은 자동 완성 기능을 구현하는 데 사용할 수 있습니다.

요약

단어 목록을 트리로 구성하는 데 사용되는 데이터 구조인 접두사 트리(try라고도 함)에 대해 배웠습니다. 이 트리를 빠르게 쿼리하여 단어가 유효한지 확인하고 동일한 접두어를 공유하는 단어를 찾을 수 있습니다.

더 많은 사람들이 배울 수 있도록 이 게시물을 공유하는 것을 잊지 마세요!