2

独自の AVL ツリーを実装し、それを辞書として使用しています。文字列で始まるすべての単語を数える最速の方法は何だろうと思っています。

例えば：

string prefix = "fa";

ここに画像の説明を入力

output: 4

私は O(n) で動作していますが、はるかに高速に実行できると聞きました。もちろん、下にあるノードなどの追加情報をノードに保持することもできます。

4

4 に答える 4

2

データ構造を変更したい場合は、 triから優れたパフォーマンスを得ることができます。トライに静的データが含まれている場合、(動的プログラミングで生成された) サブツリー カウントのサイズで分岐に注釈を付けることで、さらに優れたパフォーマンスを得ることができます。

例 [ハープ、帽子、ハイ]

           h(3)
      a(2)     i()
  r(1)    t()
p()
于 2012-12-19T13:11:20.063 に答える
1

AVLツリーは、各ノードがその「インデックス」1も認識できるように変更できます（コレクションがソートされた配列の場合、インデックスは要素番号です）。

あなたが今しなければならないのは：

  1. を検索し、ツリー内で最も近いが大きい（または等しい）要素"FA"のインデックスを取得しますi1
  2. を検索し、ツリー内で最も近いが小さい"FB"要素のインデックスを取得します。i2
  3. i1との差がある要素の数を見つけますi2（「FA」が1で見つかった場合と見つからなかった場合を区別します）。

1,2は両方ともO(logn)-3は一定であるため、全体の複雑さはO(logn)（実際O(logn * |S|)には、各比較はO（| S |）自体であり、O(logn)比較があるため）です。

（1）各ノードに息子の数を「記憶」させることで行われ、この情報を使用して最終的にインデックスを抽出できます。

于 2012-12-19T13:17:42.010 に答える
1

同じ漸近的な時間境界を維持しながらメモリ フットプリントを可能な限り削減したい場合は、ノードごとに 1 つの整数で十分であり、それでも時間を達成できますO(log n) (一定時間のキー比較を想定)。

サブツリーのサイズを各ノードに格納します。これは、ツリーの変更中に簡単に更新できます。

指定された範囲のキーの数を見つけるには:

  • この範囲で一番上の要素を見つけます。つまり、範囲内にあるが、その祖先のいずれも含まれていない一意のノードです。要素を「トップ」と呼びます。
  • そのような要素が存在しない場合は、0 を返します
  • 合計を初期化 = 1 (トップを表す)。
  • "top" の左側のサブツリーで範囲の開始を見つけます。
    • ノードから左に降りる場合は、その右サブツリー全体のサイズを合計に追加し、さらに 1 を追加します。
    • 右に下降する場合は、何も追加しません。
  • "top" の右側のサブツリーで範囲の終わりを見つけます。
    • ノードから右に降りる場合は、その左サブツリー全体のサイズを合計に追加し、さらに 1 を追加します。
    • 左に下降する場合は、何も追加しません。
  • 合計を返します。

特定のプレフィックスの範囲には、プレフィックスを持つすべての要素が含まれます。特定のプレフィックスを持つ文字列のセットは、その並べ替え順序に関して連続していることに注意することが重要です。つまり、実際には範囲です。

プレフィックス範囲の開始は、プレフィックス自体の直前の位置です。

接頭辞範囲の終わりは、この接頭辞の後の辞書編集的に最初のばらばらな接頭辞の直前の位置です ( FA=> FB;FZ=>GAのみA-Zがアルファベットにある場合)。

Unicode は、実際にはテキストに出現しない可能性がある「トップ」文字を導入することでこれを簡素化し、他のすべての文字の上で比較します。つまり、end = prefix + "\uFFFF".

于 2012-12-19T13:29:06.797 に答える
0

AVL ツリーは、目的を達成するための適切なデータ構造ではありません。基数ツリーと呼ばれる別のデータ構造があり、O(lg N) の複雑さでプレフィックス カウント クエリに答えることができます。基数ツリーの各ノードnには、0 ～ 26 の子があります。また、補助変数 もありprefix_count、基数ツリー内で で終わる接頭辞で始まる単語がいくつあるかを示しますn。たとえば、単語の基数ツリーabbabaとabbacba

        X <-- root node: it has no value
        |
        a <-- prefix count: 2
        |
        b <-- prefix count: 2
        |
        b <-- prefix count: 2
        |
        a <-- prefix count: 2
       / \
      b   c <-- prefix count: 1, 1
      |   |
      a   b <-- prefix count: 1, 1
          |
          a <-- prefix count: 1

したがって、たとえば、ツリー内のプレフィックスで始まる単語がいくつあるかを確認するには、ノードをabたどって、a --> bこのノードのプレフィックス数を返します。指定されたプレフィックスが見つからない場合は、0 を返します。

実装の秘訣:すべての操作の複雑さを改善するために、各ノードは 26 文字の配列を保持する必要があります。

psevdocode での実装:

struct node :
  let child -> array of 26 characters;
  let pc -> integer prefix counter;

struct radix-tree :
  node array[ MAXN ];
  let size -> integer size of the trie

init( rt ) :
  size := 1; // add the root

insert( rt, x ) :
  cn := 1; // root
  foreach i in x :
    if rt.array[ cn ].child[ i ] = null : // node doesn't exist
      rt.array[ cn ].child[ i ] := ++rt.size;
      cn := rt.size;
    else : // node exists
      cn := rt.array[ cn ].child[ i ];
    tr.array[ cn ].pc += 1;

関数の実装はprefix_count、挿入手順に似ています。

prefix-count( rt, x ) :
  cn := 1; // root
  foreach i in x :
    if rt.array[ cn ].child[ i ] = null :
      return 0; // 0 prefixes found
    else :
      cn := rt.array[ cn ].child[ i ];
  return rt.array[ cn ].pc;
于 2012-12-19T19:56:30.490 に答える