5

The Algorithm Design Manualのデータ構造の章を読んでいて、Suffix Trees に出会いました。

例は次のように述べています。

入力：

XYZXYZ$
 YZXYZ$
  ZXYZ$
   XYZ$
    YZ$
     Z$
      $

出力：

ここに画像の説明を入力

指定された入力文字列からそのツリーがどのように生成されるのか理解できません。接尾辞ツリーは、特定の文字列内の特定の部分文字列を見つけるために使用されますが、特定のツリーはそれに対してどのように役立つのでしょうか? 以下に示すトライの別の例は理解できますが、下のトライが接尾辞ツリーに圧縮されると、どのように見えるでしょうか?

ここに画像の説明を入力

4

3 に答える 3

5

接尾辞木を構築するための標準的な効率的なアルゴリズムは、間違いなく重要です。そのための主なアルゴリズムはUkkonenのアルゴリズムと呼ばれ、2つの追加の最適化を使用した単純なアルゴリズムの修正です。ビルド方法の詳細については、この以前の質問を読むのがおそらく最善です。

基数で標準の挿入アルゴリズムを使用して接尾辞ツリーを構築できますが、各接尾辞をツリーに挿入しようとすると、時間O（n 2）がかかり、大きな文字列ではコストがかかる可能性があります。

高速な部分文字列検索を行う場合、接尾辞木は元の文字列のすべての接尾辞（およびいくつかの特別な文字列の終わりマーカー）の圧縮されたトライであることに注意してください。文字列Sが最初の文字列Tのサブ文字列であり、Tのすべての接尾辞のトライがある場合は、検索を実行して、Tがそのトライ内の文字列のいずれかのプレフィックスであるかどうかを確認できます。その場合、TはSのサブストリングである必要があります。これは、そのすべての文字がTのどこかに順番に存在するためです。接尾辞ツリーのサブストリング検索アルゴリズムは、圧縮されたトライに適用されるこの検索で​​あり、各ステップで適切なエッジをたどります。

お役に立てれば！

于 2012-06-13T17:03:00.963 に答える
1

指定された入力文字列からそのツリーがどのように生成されるのか理解できません。

基本的に、リストしたすべてのサフィックスを使用してパトリシア トライを作成します。パトリシア トライに挿入する場合、入力文字列の最初の文字から始まる子のルートを検索します。子が存在する場合はツリーをたどりますが、存在しない場合はルートから新しいノードを作成します。ルートには、入力文字列 ($、a、e、h、i、n、r、s、t、w) 内の一意の文字と同じ数の子があります。入力文字列の文字ごとにそのプロセスを続行できます。

接尾辞ツリーは、特定の文字列内の特定の部分文字列を見つけるために使用されますが、特定のツリーはそれに対してどのように役立ちますか?

部分文字列「hen」を探している場合は、ルートから「h」で始まる子の検索を開始します。子 "h" の文字列の長さが、文字列の最後に到達するか、入力文字列と子 "h" 文字列の文字の不一致が発生するまで、子 "h" の処理を​​続行します。子 "h" のすべてに一致する場合、つまり、入力 "hen" が子 "h" の "he" に一致する場合、"n" に到達するまで "h" の子に進みます。 "n" の場合、部分文字列は存在しません。

コンパクト サフィックス トライ コード:

└── (black)
    ├── (white) as
    ├── (white) e
    │   ├── (white) eir
    │   ├── (white) en
    │   └── (white) ere
    ├── (white) he
    │   ├── (white) heir
    │   ├── (white) hen
    │   └── (white) here
    ├── (white) ir
    ├── (white) n
    ├── (white) r
    │   └── (white) re
    ├── (white) s
    ├── (white) the
    │   ├── (white) their
    │   └── (white) there
    └── (black) w
        ├── (white) was
        └── (white) when

サフィックスツリーコード:

String = the$their$there$was$when$
End of word character = $
└── (0)
    ├── (22) $
    ├── (25) as$
    ├── (9) e
    │   ├── (10) ir$
    │   ├── (32) n$
    │   └── (17) re$
    ├── (7) he
    │   ├── (2) $
    │   ├── (8) ir$
    │   ├── (31) n$
    │   └── (16) re$
    ├── (11) ir$
    ├── (33) n$
    ├── (18) r
    │   ├── (12) $
    │   └── (19) e$
    ├── (26) s$
    ├── (5) the
    │   ├── (1) $
    │   ├── (6) ir$
    │   └── (15) re$
    └── (29) w
        ├── (24) as$
        └── (30) hen$
于 2012-06-13T17:04:49.780 に答える
0

接尾辞木は、基本的に、選択の余地がない場合に文字の実行をまとめるだけです。たとえば、質問のトライの右側を見ると、を確認した後、w実際には2つの選択肢しかありません。wasとwhen。トライでは、asinwasとheninにはwhen、文字ごとに1つのノードがあります。as接尾辞木では、とを保持する2つのノードにそれらをまとめるhenので、トライの右側は次のようになります。

ここに画像の説明を入力してください

于 2012-06-13T17:03:24.307 に答える