114

トライと基数トライのデータ構造は同じですか？

それらが同じでない場合、基数トライ（別名パトリシアトライ）の意味は何ですか？

4

4 に答える 4

146

基数ツリーは、トライの圧縮バージョンです。トライでは、各エッジに 1 つの文字を書きますが、PATRICIA ツリー (または基数ツリー) では単語全体を格納します。

ここで、 、 、 という単語helloがあるhatとしhaveます。それらをtrieに格納するには、次のようになります。

    e - l - l - o
  /
h - a - t
      \
       v - e

そして、9 つのノードが必要です。ノードに文字を配置しましたが、実際にはエッジにラベルを付けています。

基数ツリーには、次のものがあります。

            *
           /
        (ello)
         /
* - h - * -(a) - * - (t) - *
                 \
                 (ve)
                   \
                    *

必要なノードは 5 つだけです。上の図では、ノードはアスタリスクです。

したがって、全体として、基数ツリーはより少ないメモリを必要としますが、実装が難しくなります。それ以外の場合、両方の使用例はほとんど同じです。

于 2013-02-05T13:45:40.657 に答える
78

私の質問は、Trieデータ構造とRadix Trieが同じものかどうかです。

要するに、いいえ。カテゴリRadix TrieはTrieの特定のカテゴリを表しますが、それはすべての試行が基数試行であることを意味しません。

それらが同じでない場合、Radix trie (別名 Patricia Trie) の意味は何ですか?

あなたが書くつもりだったのはあなたの質問ではないと思いますので、私の訂正です。

同様に、PATRICIA は基数トライの特定のタイプを示しますが、すべての基数トライが PATRICIA トライであるとは限りません。

トライとは？

「トライ」は連想配列として使用するのに適したツリー データ構造を表します。分岐またはエッジはキーの一部に対応します。ここでは、部分の定義はかなりあいまいです。なぜなら、try の実装が異なると、エッジに対応するために異なるビット長が使用されるからです。たとえば、バイナリ トライにはノードごとに 0 または 1 に対応する 2 つのエッジがありますが、16 ウェイ トライにはノードごとに 4 ビット (または 16 進数: 0x0 から 0xf) に対応する 16 のエッジがあります。

ウィキペディアから取得したこの図は、(少なくとも) キー「A」、「to」、「tea」、「ted」、「ten」、「i」、「in」、および「inn」を持つトライを描いているようです。挿入:

基本トライ

このトライがキー 't' または 'te' の項目を格納する場合、nullary ノードと実際の値を持つノードを区別するために、各ノードに存在する追加情報 (図の数字) が必要になります。

基数トライとは？

Ivaylo Strandjev が彼の回答で説明したように、「Radix trie」は、共通の接頭辞部分を凝縮した trie の形式を表しているようです。次の静的な割り当てを使用して、キー「smile」、「smiled」、「smiles」、および「smiling」にインデックスを付ける 256 通りのトライがあるとします。

root['s']['m']['i']['l']['e']['\0'] = smile_item;
root['s']['m']['i']['l']['e']['d']['\0'] = smiled_item;
root['s']['m']['i']['l']['e']['s']['\0'] = smiles_item;
root['s']['m']['i']['l']['i']['n']['g']['\0'] = smiling_item;

各添え字は内部ノードにアクセスします。つまりsmile_item、 を取得するには、7 つのノードにアクセスする必要があります。8 つのノード アクセスは と に対応しsmiled_item、smiles_item9つのノード アクセスは に対応しsmiling_itemます。これら 4 つの項目には、合計 14 のノードがあります。ただし、最初の 4 バイト (最初の 4 つのノードに対応) はすべて共通です。これらの 4 バイトを圧縮しrootて に対応する を作成することにより['s']['m']['i']['l']、4 つのノード アクセスが最適化されなくなりました。これは、メモリとノード アクセスが少ないことを意味し、非常に良い兆候です。最適化を再帰的に適用して、不要なサフィックス バイトにアクセスする必要性を減らすことができます。最終的には、検索キーと、トライによってインデックス付けされた場所のインデックス付けされたキーの違いのみを比較するようになります。. これは基数トライです。

root = smil_dummy;
root['e'] = smile_item;
root['e']['d'] = smiled_item;
root['e']['s'] = smiles_item;
root['i'] = smiling_item;

アイテムを取得するには、各ノードに位置が必要です。「smiles」という検索キーと 4 の aを使用して、たまたま であるroot.positionにアクセスします。これを という変数に格納します。はとの差の場所である 5 であるため、次のアクセスは になります。これにより、文字列の最後に到達します。検索が終了し、8 回ではなく 3 回のノード アクセスでアイテムが取得されました。root["smiles"[4]]root['e']currentcurrent.position"smiled""smiles"root["smiles"[5]]smiles_item

パトリシアトライとは？

PATRICIA トライは、アイテムnを含むために使用されるノードのみが存在する基数トライの変形です。n上記の大雑把に示した基数トライ擬似コードでは、合計で 5 つのノードがあります: root(これは nullary ノードです。実際の値は含まれません)、root['e']、root['e']['d']、root['e']['s']およびroot['i']。PATRICIA トライでは、4 つだけにする必要があります。PATRICIA はバイナリ アルゴリズムであるため、これらのプレフィックスがバイナリでどのように異なるかを見てみましょう。

smile:   0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0000 0000  0000 0000
smiled:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0110 0100  0000 0000
smiles:  0111 0011  0110 1101  0110 1001  0110 1100  0110 0101  0111 0011  0000 0000
smiling: 0111 0011  0110 1101  0110 1001  0110 1100  0110 1001  0110 1110  0110 0111 ...

ノードが上に示した順序で追加されると考えてみましょう。smile_itemこのツリーのルートです。識別しやすいように太字で示した違いは、 の最後のバイトの"smile"ビット 36 にあります。この時点まで、すべてのノードは同じプレフィックスを持っています。smiled_nodeに属しsmile_node[0]ます。との違いはビット 43"smiled"で"smiles"発生します。ここで"smiles"は「1」ビットを持っているので、 もそうsmiled_node[1]ですsmiles_node。

NULL検索がいつ終了するかを示すために枝や追加の内部情報として使用するのではなく、枝はどこかでツリーをバックアップするため、テストするオフセットが増加するのではなく減少すると検索が終了します。以下に、そのようなツリーの簡単な図を示します(ただし、後で説明するように、PATRICIA は実際にはツリーというよりは循環グラフです)。これは、以下で説明する Sedgewick の本に含まれています。

簡単なパトリシア図

バリアント長の鍵を含むより複雑な PATRICIA アルゴリズムが可能ですが、その過程で PATRICIA の技術的特性の一部が失われます (つまり、任意のノードがその前のノードと共通のプレフィックスを含む)。

複雑なパトリシア図

このように分岐することにより、多くの利点があります。すべてのノードに値が含まれます。それにはルートが含まれます。その結果、コードの長さと複雑さが大幅に短くなり、実際にはおそらく少し速くなります。アイテムを見つけるために、少なくとも 1 つの分岐と最大でk分岐 (kは検索キーのビット数) がたどられます。ノードはそれぞれ 2 つのブランチのみを格納するため、非常に小さいため、キャッシュの局所性の最適化に非常に適しています。これらの特性により、PATRICIA はこれまでのところ私のお気に入りのアルゴリズムになっています...

差し迫った関節炎の重症度を軽減するために、ここではこの説明を短くしますが、PATRICIA について詳しく知りたい場合は、Donald Knuth 著の「The Art of Computer Programming, Volume 3」などの本を参照してください。 、または Sedgewick による「{your-favorite-language} のアルゴリズム、パート 1-4」のいずれか。

于 2013-04-09T15:39:58.803 に答える
24

TRIE:
検索キー全体を既存のすべてのキー (ハッシュ スキームなど) と比較する代わりに、検索キーの各文字を比較する検索スキームを使用できます。この考えに従って、「<em>dad」、「<em>dab」、および「<em>cab」という 3 つの既存のキーを持つ構造 (以下に示す) を構築できます。

         [root]
     ...// | \\...
           |  \
           c   d
           |    \
          [*]    [*]
      ...//|\.  ./|\\...        Fig-I
        a       a
       /       /
     [*]      [*]
 ...//|\..  ../|\\...
    /        /   \
   B        b     d
  /        /       \
 []       []       []

(cab)   (dab)     (dad)

これは基本的に、[ * ] で表される内部ノードと [ ] で表されるリーフ ノードを持つ M-ary ツリーです。この構造はトライと呼ばれます。各ノードでの分岐決定は、アルファベットの一意の記号の数、たとえば R に等しく保つことができます。小文字の英語のアルファベット az の場合、R=26; 拡張 ASCII アルファベットの場合は R=256、2 進数/文字列の場合は R=2 です。

コンパクト TRIE:
通常、トライ内のノードはsize=R の配列を使用するため、各ノードのエッジが少ないとメモリの浪費が発生します。メモリの問題を回避するために、さまざまな提案がなされました。これらのバリエーションに基づいて、トライは「<em>コンパクト トライ」および「<em>圧縮トライ」とも呼ばれます。一貫した命名法はめったにありませんが、コンパクトトライの最も一般的なバージョンは、ノードが単一のエッジを持つ場合にすべてのエッジをグループ化することによって形成されます。この概念を使用すると、「dad」、「dab」、および「cab」というキーを使用した上記 (図-I) のトライは、次の形式をとることができます。

         [root]
     ...// | \\...
           |  \
          cab  da
           |    \
          [ ]   [*]                Fig-II
               ./|\\...
                 |  \
                 b   d
                 |    \
                []    []

「c」、「a」、および「b」のそれぞれは、対応する親ノードの唯一のエッジであるため、単一のエッジ「cab」に集約されることに注意してください。同様に、「d」と「a」は、「da」とラベル付けされた単一のエッジにマージされます。

基数トライ:基数
という用語は、数学では数体系の基数を意味し、基本的に、その数を表すために必要な一意の記号の数を示します。たとえば、10 進法は基数 10、2 進法は基数 2 です。同様の概念を使用して、基礎となる表現システムの一意のシンボルの数によってデータ構造またはアルゴリズムを特徴付けることに関心がある場合、その概念に「基数」という用語を付けます。たとえば、特定のソート アルゴリズムの「基数ソート」。ロジックの同じ行で、trieのすべてのバリアントその特性 (深さ、メモリの必要性、検索ミス/ヒットの実行時間など) は、基になるアルファベットの基数に依存します。基数を「トライ」と呼ぶ場合があります。たとえば、 a ～ z のアルファベットを使用するときの圧縮されていないトライと圧縮されたトライは、基数 26 のトライと呼ぶことができます。2 つのシンボル (伝統的には「0」と「1」) のみを使用するトライは、基数 2 のトライと呼ばれます。ただし、どういうわけか、多くの文献では、「基数トライ」という用語の使用は圧縮されたトライのみに制限されていました。

PATRICIA Tree/Trie への序曲:
キーとしての文字列でさえ、バイナリ アルファベットを使用して表現できることに注目すると興味深いでしょう。ASCII エンコーディングを仮定すると、キー「dad」は、バイナリ形式の「d」、「a '、および 'd' の順に。この概念を使用して、(基数 2 の)トライを形成できます。以下では、文字「a」、「b」、「c」、および「d」が ASCII ではなく、より小さなアルファベットに由来するという単純化された仮定を使用して、この概念を示します。

Fig-III の注: 前述のように、描写を簡単にするために、{a、b、c、d} の 4 文字だけのアルファベットと、それに対応する 2 進数表現が「00」、「01」、「10」、およびそれぞれ「11」。これにより、文字列キー「dad」、「dab」、および「cab」は、それぞれ「110011」、「110001」、および「100001」になります。このためのトライは、以下の図 III に示すようになります (文字列が左から右に読み取られるように、ビットは左から右に読み取られます)。

          [root]
             \1               
              \
              [*]
             0/ \1               
             /   \
           [*]   [*]         
           0/     /               
           /     /0
         [*]    [*]      
        0/      /               
        /      /0
      [*]    [*]
     0/     0/ \1                Fig-III
     /      /   \
    [*]   [*]   [*]
     \1     \1    \1
      \      \     \
      []     []    []
    (cab)   (dab) (dad)

PATRICIA Trie/Tree:
シングル エッジ圧縮を使用し て上記のバイナリトライ(図-III) を圧縮すると、ノードは上記よりもはるかに少なくなりますが、それでもノードは含まれるキーの数である 3 より多くなります。 . Donald R. Morrisonは (1968 年に) バイナリトライを使用して N 個のノードのみを使用して N 個のキーを表す革新的な方法を発見し、このデータ構造をPATRICIAと名付けました。. 彼のトライ構造は本質的に単一のエッジ (一方向の分岐) を取り除きました。そうすることで、彼は 2 種類のノードの概念も取り除きました。内部ノード (キーを表示しないノード) とリーフ ノード (キーを表示するノード) です。上で説明した圧縮ロジックとは異なり、彼のトライは異なる概念を使用しており、各ノードには、分岐の決定を行うためにキーの何ビットをスキップするかの指示が含まれています。彼のパトリシア トライのもう 1 つの特徴は、キーを保存しないことです。つまり、そのようなデータ構造は、特定のプレフィックスに一致するすべてのキーを一覧表示するなどの質問に答えるのには適していませんが、キーが存在するかどうかを調べるには適しています。トライではありません. それにもかかわらず、パトリシア ツリーまたはパトリシア トライという用語は、それ以来、コンパクト トライを示す [NIST]、または基数 2 の基数トライを示す [微妙に示されているように] など、多くの異なるが類似した意味で使用されてきました。 WIKIの方法]など。

基数トライではない可能性のあるトライ:
三分探索トライ(別名三分探索ツリー)は、 TSTが3 方向分岐を持つトライに非常によく似たデータ構造 ( J. BentleyとR. Sedgewickによって提案された) であるため、しばしば省略されます。このようなツリーの場合、各ノードには特徴的なアルファベット「x」があるため、キーの文字が「x」より小さいか、等しいか、大きいかによって分岐の決定が行われます。この固定された 3 方向分岐機能により、特に Unicode アルファベットのように R (基数) が非常に大きい場合に、trie のメモリ効率の良い代替手段が提供されます。興味深いことに、TST は (R-way) trieとは異なり、その特性が R の影響を受けません。たとえば、TST の検索ミスはln(N)です。R-way Trie のlog R (N)とは対照的です。TST のメモリ要件は、R-wayトライとは異なり、Rの関数でもありません。したがって、TST を基数トライと呼ぶには注意が必要です。個人的には、基数トライと呼ぶべきではないと思います。なぜなら、(私が知る限り)その特性のどれも、基になるアルファベットの基数 R の影響を受けないからです。

于 2016-11-12T20:50:16.750 に答える