3

OK、試行はしばらく前から行われています。典型的な実装では、データセットのサイズ n (m はメッセージの長さ) とは無関係に、O(m) ルックアップ、挿入、および削除操作を提供する必要があります。ただし、この同じ実装は、最悪の場合、入力バイトごとに 256 ワードを使用します。

他のデータ構造、特にハッシュでは、O(m) ルックアップ、挿入、および削除が期待でき、一定時間のルックアップを提供する実装もあります。それにもかかわらず、最悪の場合、ルーチンは停止しないか、O(nm) 時間かかります。

問題は、O(m) ルックアップ、挿入、および削除時間を提供しながら、ハッシュまたは検索ツリーに匹敵するメモリ フットプリントを維持するデータ構造があるかどうかです。

時間的にも空間的にも、最悪の場合の動作にのみ関心があると言うのが適切かもしれません。

4

4 に答える 4

4

Patricia-(別名 critbit- または Radix-) は試しましたか? 最悪の場合のスペースの問題を解決すると思います。

于 2010-07-26T15:07:44.880 に答える
0

接尾辞配列と呼ばれる構造があります。この分野の研究は思い出せませんが、この構造ではO（m）ルックアップ時間にかなり近づいたと思います。また、一般的なツリーベースのインデックス作成方法よりもはるかにコンパクトです。

Dan Gusfieldの本は、文字列アルゴリズムの聖書です。

于 2010-07-26T15:18:08.033 に答える
0

次の2つの理由から、最悪のケースについて心配する理由はないと思います。

  1. 保存されたデータの合計サイズよりも多くのアクティブなブランチがすべてのトライノードの合計に含まれることはありません。
  2. ノードサイズが問題になるのは、並べ替え/保存しているデータに大きなファンアウトがある場合のみです。ニーモニックはその一例です。圧縮メカニズムとしてトライに依存している場合、ハッシュテーブルは役に立ちません。

圧縮する必要があり、一般的なサブシーケンスがほとんどないかまったくない場合は、文字列に関する一般的な仮定に基づくのではなく、データの特定の形状に基づいて圧縮アルゴリズムを設計する必要があります。たとえば、完全に/大量に入力されたニーモニックデータセットの場合、入力されたデータではなく、データの「穴」を追跡するデータ構造の方が効率的である可能性があります。

とは言うものの、中程度のファンアウトがある場合は、固定されたトライノードサイズを回避することで利益が得られる可能性があります。トライの各ノードをハッシュテーブルにすることができます。小さいサイズから始めて、要素が挿入されるにつれて大きくします。最悪の場合の挿入は、増加のためにすべてのハッシュテーブルを再編成する必要がある場合、c * mになります。ここで、cは可能な文字/一意のアトミック要素の数です。

于 2010-07-26T15:18:31.620 に答える