접두사 트리(prefix tree, 흔히 '트라이(trie)'라고도 불립니다)는 단어 목록을 체계적으로 정리하고, 특정 접두사로 시작하는 단어를 빠르게 찾아낼 수 있게 도와주는 자료구조입니다.
예를 들어 사전에 있는 단어 중 "ca"로 시작하는 모든 단어, 즉 "cat"이나 "cape" 같은 단어들을 손쉽게 찾을 수 있습니다.
다음 그림을 살펴보세요.
이것이 바로 접두사 트리입니다.
루트(*)에서 출발해 마킹된 노드(예: e, t)까지 경로를 따라가면 하나의 단어를 찾을 수 있습니다.
이 글에서는 루비로 직접 접두사 트리를 구현하는 방법과, 이를 활용해 실제 문제를 해결하는 방법까지 함께 알아보겠습니다.
접두사 트리 구현하기
루비로 구현하기 위해 저는 몇 가지 속성을 가진 Node 클래스를 사용하기로 했습니다.
- 값(value): 한 글자를 저장합니다.
- word 변수: 해당 노드가 완성된 단어의 끝인지를 나타내는 true/false 값입니다.
- next 배열: 트리에서 이 노드 다음에 오는 문자들(
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
그렇다면 이 자료구조는 어떤 용도로 쓰일까요?
- 단어 게임 풀이
- 맞춤법 검사
- 자동완성(Autocomplete)
이런 기능을 만들려면 트리에 넣어둘 좋은 사전 데이터가 필요합니다.
유용하게 쓸 수 있는 사전 파일 두 곳을 소개합니다:
- 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 메서드도 추가하고 싶습니다.
이 작업은 '깊이 우선 탐색(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
여기서는 스택 두 개를 사용합니다. 하나는 아직 방문하지 않은 노드를 추적하는 stack이고, 다른 하나는 현재까지 조합된 문자열을 관리하는 prefix_stack입니다.
모든 노드를 방문할 때까지 반복하면서, 노드의 값을 prefix_stack에 차곡차곡 쌓습니다. 각 노드는 한 글자만 담고 있으므로, 이 문자들을 모아야 완전한 단어가 됩니다.
:guard_node 심볼은 되돌아가는(backtracking) 시점을 알아내기 위해 스택에 넣어둡니다. 덕분에 적절한 타이밍에 문자열 버퍼(prefix_stack)에서 문자를 제거할 수 있습니다.
그리고 node.word가 true라면 완성된 단어를 찾았다는 의미이므로, 단어 목록에 추가합니다.
메서드 사용 예시:
t.find_words_starting_with("cap")
# ["cap", "cape"]
찾는 단어가 없으면 빈 배열이 반환됩니다:
t.find_words_starting_with("b")
# []
이 메서드를 활용하면 자동완성 기능도 손쉽게 구현할 수 있습니다.
정리
이번 글에서는 단어 목록을 트리 형태로 정리하는 자료구조인 접두사 트리(트라이)에 대해 배웠습니다. 이 트리를 조회하면 특정 단어가 유효한지 빠르게 확인할 수 있고, 같은 접두사를 공유하는 단어들도 손쉽게 찾아낼 수 있습니다.
더 많은 사람들이 학습할 수 있도록 이 글을 공유하는 것도 잊지 마세요!