【Ruby】プレフィックスツリー（トライ）の実装方法と活用例を徹底解説

プレフィックスツリー（別名：トライ／Trie）は、単語のリストを効率的に整理し、特定の接頭辞（プレフィックス）で始まる単語を高速に検索できるデータ構造です。

例えば、「ca」という2文字で始まる単語をすべて探したい場合、「cat」や「cape」といった候補を瞬時に見つけることができます。

まずは下の図をご覧ください。

これがプレフィックスツリーです。

ルート（*）から、単語の終端を示すマーク済みノード（e や t など）へと枝を辿っていくことで、1つずつ単語を読み取ることができます。

この記事では、Rubyで独自のプレフィックスツリーを実装する方法と、それを活用して問題を解く方法を詳しく解説します。

プレフィックスツリーの実装

Rubyでの実装には、いくつかの属性を持つ Node クラスを使用します。

• value：1文字分の値
• 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

では、このデータ構造にはどのような用途があるのでしょうか？

• 単語ゲームの解答支援
• スペルチェッカー
• オートコンプリート（入力補完）機能

これらを実現するには、ツリーに読み込むための質の良い辞書データが必要です。

以下の辞書データは役立つでしょう。

• 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）」アルゴリズムを使用します。あわせて、現在走査中の単語を追跡する仕組みも必要です。

各ノードが保持しているのは1文字だけなので、ツリーを辿りながら文字をつなぎ合わせ、元の文字列を復元する必要があります。

その処理を行うメソッドがこちらです：

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

ここでは2つのスタックを使用しています。1つは未訪問のノードを管理する stack、もう1つは現在組み立て中的な文字列を保持する prefix_stack です。

すべてのノードを訪問し終えるまでループを回しながら、ノードの値を prefix_stack に追加していきます。各ノードは1文字しか持たないため、これらの文字を集めて単語を形成する必要があるのです。

:guard_node というシンボルは、バックトラック（探索の巻き戻し）のタイミングを検知するためにスタックに挿入されます。これにより、文字列バッファ（prefix_stack)から文字を適切なタイミングで取り除けるようになります。

そして、node.word が true であれば完全な単語が見つかったことになるので、結果リストに追加します。

このメソッドの使用例：

t.find_words_starting_with("cap")

# => ["cap", "cape"]

該当する単語が見つからない場合は、空の配列が返ります。

t.find_words_starting_with("b")

# => []

このメソッドを応用すれば、オートコンプリート機能を実装することも可能です。

まとめ

この記事では、単語のリストを木構造として整理するデータ構造「プレフィックスツリー（トライ）」について学びました。このツリーを使えば、ある単語が有効かどうかの高速な判定や、同じ接頭辞を持つ単語の一括検索が実現できます。

ぜひこの記事をシェアして、より多くの人が学べるようにしてください！