「アルゴリズムとデータ構造」トライ木の美しさ

[[349418]]

序文

今回紹介するトライ辞書ツリーは、データ構造トピックの分岐です。トライのツリーデータ構造を理解することは、アルゴリズムとデータ構造の知識体系の構築に役立ちます。

トライツリーについての私の理解は、すべての文字列を連結して不要なストレージを排除し、文字列の共通プレフィックスを使用するというものです。

実際、それを理解するには、この文を理解するだけで十分です👇

文字列の共通プレフィックスを使用してクエリ時間を短縮し、不要な文字列比較を最小限に抑えます。クエリ効率はハッシュ ツリーよりも高くなります。

Trie データ構造が何であるか分からない場合、または少しは知っているが単純な Trie ツリーを実装する方法が分からない場合は、この記事を読むのが適切かもしれません。

それでは、以下の点を中心にトライ木を紹介しましょう👇

• 基本概念
• 基本的なプロパティ
• アプリケーションシナリオ
• 2つの例

基本概念

まず、トライ木についての基本的な理解が必要です。トライ木の中国語名は辞書木、接頭辞木などです。これからは辞書木と呼ぶことにします。

Wikipediaの説明を見てみましょう⬇️

コンピュータ サイエンスにおいて、トライ (接頭辞ツリーまたは辞書ツリーとも呼ばれる) は、キーが通常は文字列である連想配列を格納するために使用される順序付けられたツリーです。バイナリ検索ツリーとは異なり、キーはノードに直接格納されるのではなく、ツリー内のノードの位置によって決定されます。ノードのすべての子孫は同じプレフィックスを持ちます。プレフィックスはノードに対応する文字列ですが、ルート ノードは空の文字列に対応します。一般的に、すべてのノードに対応する値があるわけではありません。リーフ ノードと一部の内部ノードに対応するキーにのみ関連する値があります。

わかりやすくてシンプルな説明。実は写真を見ればわかるんですよ～。ネットでいい写真を​​見つけました。原作者が見つからないので具体的な出典はここでは書きません～

辞書ツリー図 1

ここで説明する必要があるのは、一般的に言えば、文字を表すには点を使用する必要があるということです。わかりやすくするために、私はエッジを使用して文字を記述します。

この辞書ツリーはエッジを使用して文字を表し、ルート ノードからツリー内のノードまでのパスが文字列を表していることがわかります。たとえば、1→2→6 は文字列 aba を表します。

たとえば、1→4→8 で構成される文字列は ca です。これをさらに展開すると、caa や cab になる場合があります。これらはすべて 1→4→8 を経由します。これらのパスは、共通のプレフィックスである ca があることを示しています。この時点で、辞書ツリーは文字列のプレフィックスを使用して問題を解決していることがわかります。

では、その具体的な特性とはどのようなものでしょうか？以下で紹介します～

基本的なプロパティ

上記の概念をある程度理解した後、トライツリーの基本的な特性を見てみましょう。

これを踏まえると、大きく分けて3つのポイントに分けられます。

1. ルート ノードには文字が含まれず、ルート ノード以外の各ノードには 1 文字のみが含まれます。
2. ルートノードから特定のノードまで、パス上の文字が接続され、ノードに対応する文字列が形成されます。
3. 各ノードのすべての子ノードには異なる文字列が含まれます。

次に少し分析してみましょう。写真で見てみましょう👇

how、hi、her、hello、so、see の 6 つの文字列を使用して、次の図を作成します。

トライ木の図

最初のプロパティ:

図から、ルート ノードは / であり、これは空のコンテンツを表すこともわかります。他のノード、たとえばルート ノードの次のレベルには、それぞれ 2 つの文字を表す h と s があります。

2番目のプロパティ:

ルートノードから特定のノードまで、パス上の文字が接続され、ノードに対応する文字列が形成されます。

たとえば、 how は文字列を表し、 hi も文字列を表しますが、なぜ he と hel は文字列を表せないのか疑問に思います。

これについて考えるということは、あなたがこれを注意深く読み、習得しようとしていることを意味します。確かに、図から、いくつかのノードが異なる色になっていることがわかります。これは、この暗いノードが現在の文字列の終わりを表すことを事前に決定したためです。考えてみてください。これの目的は何でしょうか?

では、実際のコードでどのように合意したりマークを付けたりすればよいのでしょうか? 実際には、マーク ビットを設定するだけで済みます。

たとえば、次のようになります。

 const TrieNode =関数() {
  this.next = Object.create ( null )
  this.isEnd = false  
 };

現在の isEnd 変数は、現在のノードが終了文字列であるかどうかを示します。isEnd が True の場合、ルート ノードからこの文字までの文字列が存在し、完全な文字列であることを意味します。

3番目のプロパティ:

各ノードのすべての子ノードには異なる文字列が含まれます。

明らかに、ルート ノードから始めて 1 つずつ下っていくと、各ノードの下のノードが異なることがわかるので、順番に構成される文字列は同じにはなり得ません。

アプリケーションシナリオ

トライ木についてある程度理解した後、その実際の応用シナリオを見てみましょう。

インターネットで提供されているポイントの参考資料をいくつか紹介します👇

検索エンジンにキーワードプロンプトがある場合、エンジンは一致するキーワードのドロップダウンボックスを自動的にポップアップ表示します。このアプリケーションシナリオは誰もがよく知っているはずです。

では、効率的なデータ構造をストレージに使用するにはどうすればよいでしょうか。これは辞書ツリーの特性と一致しており、辞書ツリーを使用して特定のデータを構築し、より高速な検索効果を実現できます。

文字列検索

トライツリーに既知の文字列（辞書）の関連情報を事前に保存しておき、他の未知の文字列が出現したかどうか、またはその出現頻度を調べます。状況を説明するために例を挙げることができます👇

• 1,000 万個の文字列があり、その一部は重複しています。重複している文字列をすべて削除し、重複していない文字列を保持する必要があります。
• N 個の単語からなるよく使われる単語リストと、すべて小文字の英語で書かれた記事が与えられた場合、よく使われる単語リストにない新しい単語を、最初に登場した順にすべて書き出してください。

単語の頻度統計

非常に長い文字列が与えられた場合、最も頻繁に出現する頻度をカウントします。例:

• 1G のファイルがあり、各行は 1 ワードで、ワード サイズは 16 バイトを超えず、メモリ制限は 1M です。最も頻繁に使用される 100 個の単語を返します。
• 約 10,000 行のテキスト ファイルがあり、各行には 1 つの単語が含まれています。最も頻繁に出現する上位 10 個の単語を数える必要があります。ご意見と時間計算量の分析をお知らせください。

文字列の最長共通接頭辞

ここまでで、トライ木が複数の文字列の共通プレフィックスを使用してストレージ スペースを節約することがわかりました。トライ木に大量の文字列を格納すると、一部の文字列の共通プレフィックスをすばやく取得できるため、この機能を使用してプレフィックスの問題を解決できます。

例を挙げるとすれば、ここに例があります👇

• N 個の小文字の英語の文字列と Q 個のクエリがある場合、2 つの文字列の最長共通プレフィックスの長さはどれくらいでしょうか。

応用シナリオはまだたくさんあり、残りは自分で探求することができます。次に、実際の質問を通じて辞書ツリーを構築する方法を見てみましょう〜

2 例

次に、2つの質問を例にして、辞書ツリーが実際のアプリケーションでどのような問題を解決できるかを確認します👇

辞書の中で最も長い単語⭐

リンク: 辞書​​で最も長い単語

文字列配列の単語で構成される英語辞書が与えられます。単語辞書内の他の単語に 1 文字ずつ徐々に追加して構成される最長の単語を見つけます。複数の回答が考えられる場合は、回答の中で辞書順が最も小さい単語が返されます。

回答がない場合は空の文字列を返します。

例1:

入力：
単語 = [ "w" 、 "wo" 、 "wor" 、 "worl" 、 "world" ]
出力: "world"  
説明する：
 「world」という単語は、 「w」 、 「wo」 、 「wor」 、 「worl」に文字を追加することで形成されます。

例2:

入力：
単語 = [ "a" 、 "バナナ" 、 "アプリ" 、 "appl" 、 "ap" 、 "適用" 、 "リンゴ" ]
出力: "apple"  
説明する：
 「apply」と「apple」はどちらも辞書に載っている単語で作ることができます。しかし、 「apple」は辞書的には「apply」より下位です。

ヒント：

この問題は、単語配列の一部に分割できる最長の単語を見つけるだけです。最も過激なアイデアは各項目を列挙することですが、この方法の時間計算量は膨大です。この時点で、この問題の共通の特徴は何であるかについて考えてみましょう。

• そうです、プレフィックスは同じです。この観点から、このプレフィックス ツリーを使用してデータを保存できますか?
• 次に、辞書ツリーをトラバースします。ツリーにブランチが 1 つしかない場合は、解決策があることを意味します。ブランチが 2 つ以上ある場合は、答えはありません。

複雑性分析

この点は簡単に理解できるはずなので、ここでは省略します。

ここでの私の解決策は、辞書ツリーを構築することです。もちろん、他の解決策もありますが、ここでは詳しく説明しません。私のコードを見てください〜

コードはこちらをクリック☑️

実際、トライツリーの構築には多くのスペースが消費されます。これは、スペースと時間を交換しているようなものなので、実際の問題に基づいて問題を解決する必要があります。

トライ（プレフィックスツリー）を実装する ⭐⭐

リンク: Trie (プレフィックスツリー) の実装

挿入、検索、startsWith の 3 つの操作を持つ Trie (プレフィックス ツリー) を実装します。

例：

トライ trie = new Trie();
 trie.insert ( "リンゴ" );
 trie.search( "apple" ); // trueを返す 
 trie.search( "app" ); // falseを返す 
 trie.startsWith( "app" ); // trueを返す 
 trie.insert ( "アプリ" );
 trie.search( "app" ); // trueを返す 

例:

• すべての入力は小文字の a ～ z で構成されていると想定できます。
• すべての入力は空でない文字列であることが保証されます。

このトピックは、トライツリーの記述に関する典型的なものです。このトピックを初めて記述していて、何もわからない場合は、まず他の人のコードを見て、基本的なルーチンがどこにあるかを確認してください。

これ以上面倒なことはせずに、このコードを参照して辞書ツリーの構築方法を確認してください👇

コードはこちらをクリック☑️

残りの削除操作や、文字列の出現頻度のカウントは、自分で実装できます。これは基本的に難しくありません。図を描けば、実装方法がわかります。

答えるべき質問は無限にあります。これらの質問を終えた後、トライ辞書ツリーについての知識が少し得られ、より深く理解できるようになることを願っています。次に、4 つの質問セットを用意しました。これらが役立つことを願っています。

辞書の中で最も長い単語

トライ（プレフィックスツリー）の実装

ワードサーチ II

質問を読み込んでいます