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

プレフィックスツリー（トライ）は、文字列の集合を効率的に管理するためのデータ構造です。特に、文字列の検索や補完、辞書の実装において非常に役立ちます。このガイドでは、Rubyを使用してプレフィックスツリーを実装する方法を詳しく説明します。

プレフィックスツリーとは？

プレフィックスツリーは、各ノードが文字を表し、ルートからリーフノードまでのパスが文字列を形成する木構造です。以下のような特徴があります：

各ノードは、子ノードを持つことができ、これにより文字列のプレフィックスを表現します。
文字列の挿入、検索、削除が効率的に行えます。
特に、同じプレフィックスを持つ文字列のグループ化が得意です。

プレフィックスツリーの基本構造

プレフィックスツリーを実装するためには、まずノードを表すクラスを作成します。以下は、ノードクラスの基本的な実装です：

class TrieNode
  attr_accessor :children, :is_end_of_word

  def initialize
    @children = {}
    @is_end_of_word = false
  end
end

このクラスでは、子ノードを格納するためのハッシュと、単語の終端を示すブール値を持っています。

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

次に、プレフィックスツリー全体を表すクラスを作成します。このクラスには、単語の挿入、検索、削除のメソッドを実装します。

class Trie
  def initialize
    @root = TrieNode.new
  end

  def insert(word)
    node = @root
    word.each_char do |char|
      node.children[char] ||= TrieNode.new
      node = node.children[char]
    end
    node.is_end_of_word = true
  end

  def search(word)
    node = @root
    word.each_char do |char|
      return false unless node.children[char]
      node = node.children[char]
    end
    node.is_end_of_word
  end

  def delete(word)
    delete_helper(@root, word, 0)
  end

  private

  def delete_helper(node, word, depth)
    return false if node.nil?

    if depth == word.length
      return false unless node.is_end_of_word
      node.is_end_of_word = false
      return node.children.empty?
    end

    char = word[depth]
    should_delete_current_node = delete_helper(node.children[char], word, depth + 1)

    if should_delete_current_node
      node.children.delete(char)
      return node.children.empty? && !node.is_end_of_word
    end

    false
  end
end

メソッドの説明

上記のコードには、以下のメソッドが含まれています：

insert(word): 単語をツリーに挿入します。
search(word): 単語がツリーに存在するかどうかを確認します。
delete(word): 単語をツリーから削除します。

プレフィックスツリーの使用例

それでは、実際にプレフィックスツリーを使用してみましょう。以下のコードは、単語の挿入、検索、削除の例です：

trie = Trie.new
trie.insert("apple")
trie.insert("app")

puts trie.search("apple") # => true
puts trie.search("app")   # => true
puts trie.search("ap")    # => false

trie.delete("apple")
puts trie.search("apple") # => false
puts trie.search("app")   # => true

プレフィックスツリーの利点

プレフィックスツリーを使用することには、いくつかの利点があります：

効率的な検索: プレフィックスツリーは、特に長い文字列の集合に対して効率的な検索を提供します。
メモリの最適化: 同じプレフィックスを持つ単語を共有することで、メモリの使用を最適化できます。
補完機能: プレフィックスツリーを使用すると、ユーザーが入力した文字列に基づいて候補を提示する補完機能を簡単に実装できます。

補完機能の実装

プレフィックスツリーを使用して、文字列の補完機能を実装することもできます。以下は、補完機能を追加するためのメソッドの実装例です：

def autocomplete(prefix)
  node = @root
  prefix.each_char do |char|
    return [] unless node.children[char]
    node = node.children[char]
  end
  collect_words(node, prefix)
end

private

def collect_words(node, prefix)
  words = []
  if node.is_end_of_word
    words << prefix
  end
  node.children.each do |char, child_node|
    words.concat(collect_words(child_node, prefix + char))
  end
  words
end

このメソッドは、指定されたプレフィックスに基づいて、ツリー内のすべての単語を収集します。

まとめ

プレフィックスツリーは、文字列の管理に非常に便利なデータ構造です。Rubyを使用して簡単に実装でき、検索や補完機能を効率的に行うことができます。この記事を参考にして、ぜひ自分のプロジェクトにプレフィックスツリーを取り入れてみてください。

プレフィックスツリーの実装を通じて、データ構造の理解が深まることを願っています。質問やコメントがあれば、ぜひお知らせください！