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）アルゴリズムを使用して実行できます。また、見ている単語を追跡する方法も必要です。
 
 ノードにはそれぞれ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  ）＆現在の文字列を追跡するための別の文字列（ prefix_stack  。
 
 すべてのノードにアクセスするまでループし、ノードの値を prefix_stackに追加します 。各ノードは1文字の値のみを保持するため、これらの文字を収集して単語を形成する必要があります。
 
 ：guard_node  シンボルがprefix_stackに追加されます ですから、いつバックトラックしているのかがわかります。文字列バッファ（ prefix_stack ）から文字を削除するためにこれが必要です ）適切なタイミングで。
 
 次に、 node.wordの場合 本当です。それは、完全な単語を見つけて、それを単語のリストに追加することを意味します。
 
 この方法の使用例 ：
 t.find_words_starting_with("cap")

# ["cap", "cape"]
 
 単語が見つからない場合は、空の配列を取得します：
 t.find_words_starting_with("b")

# []
 
 このメソッドは、オートコンプリート機能を実装するために使用できます。
 概要
 
 単語のリストをツリーに編成するために使用されるデータ構造であるプレフィックスツリー（トライとも呼ばれます）について学習しました。このツリーをすばやくクエリして、単語が有効かどうかを確認し、同じプレフィックスを共有する単語を見つけることができます。
 
 より多くの人が学ぶことができるように、この投稿を共有することを忘れないでください！



            

                
            

            
                
                    
                    Rubyはあなたからエラーを隠しています！        
                
                
                    Atomエディター：Ruby開発者のためのトリック、プラグイン、ショートカット！     
                    
                
             

             
                 
                    
 
                         
                         
                             
                                 Rubyエイリアスキーワードの使用方法 
                             
                             
                               Rubyメソッドに別の名前を付けるには、次の2つの方法があります。  エイリアス（キーワード）  alias_method    彼らはわずかに異なる方法で同じことをするので、これは紛らわしいトピックになる可能性があります。  この画像は違いの要約です ：     しっかりと理解するために、これらの違いをさらに詳しく調べてみましょう！ エイリアスキーワード  まず、aliasがあります 、これはRubyキーワードです（ifなど） 、def 、class 、など）  このように見えます ： 
alias print_something puts

print_something 1
  prin                             
                         
                     
 
                         
                         
                             
                                 RubyでStructとOpenStructを使用する方法 
                             
                             
                               Rubyの構造体とは何ですか？  構造体は組み込みのRubyクラスであり、値オブジェクトを生成する新しいクラスを作成するために使用されます。値オブジェクトは、関連する属性を一緒に格納するために使用されます。  ここに例があります ：  Point 2つの座標（x ＆y 。  このデータはさまざまな方法で表すことができます。  いいね ：  配列[10, 20]  ハッシュ{ x: 10, y: 10 }  オブジェクトPoint.new(10, 20)    複数のPointを使用する場合 、オブジェクトアプローチを使用することをお勧めします。  しかし…   これら2つの値を一緒に格納するた