1

http://marknelson.us/1996/08/01/suffix-trees/のサイトに基づいてJavaでサフィックスツリーを構築しましたが、問題が発生しました。接尾辞ツリーをうまく構築することはできますが、ツリーからすべての接尾辞のセットを構築しようとすることはできます。基本的にすべての「エンドノード」を見つけて、その「エンドノード」で表される文字列を返します

そのアルゴリズムは「簿記係」のような単語に対して機能します

├── (1) bookkeeper
├── (9) e
│   ├── (8) eper
│   ├── (10) per
│   └── (12) r
├── (6) k
│   ├── (7) eeper
│   └── (5) keeper
├── (3) o
│   ├── (4) kkeeper
│   └── (2) okkeeper
├── (11) per
└── (13) r

接尾辞：

[bookkeeper, ookkeeper, okkeeper, kkeeper, keeper, eeper, eper, er, per, r]

でも「ATATATATATA」みたいなものを使うと失敗します

├── (1) ATATATATATA
└── (2) TATATATATA

接尾辞：

[ATATATATATA, TATATATATA]

ただし、適切なサフィックスは次のようになります。

[A, ATA, ATATA, ATATATA, ATATATATA, ATATATATATA, TA, TATA, TATATA, TATATATA, TATATATATA]

各「エンドノード」文字列のすべてのサフィックスを見つけることで答えを見つけることができますが、それは正しいアプローチのようには思えません。他に何か提案はありますか？

編集：izomorphiusに感謝します！元の文字列にEND_CHARを追加すると、非常に役立ちました。

├── (21) #
├── (19) A
│   ├── (20) #
│   └── (15) TA
│       ├── (16) #
│       └── (11) TA
│           ├── (12) #
│           └── (7) TA
│               ├── (8) #
│               └── (3) TA
│                   ├── (4) #
│                   └── (1) TA#
└── (17) TA
    ├── (18) #
    └── (13) TA
        ├── (14) #
        └── (9) TA
            ├── (10) #
            └── (5) TA
                ├── (6) #
                └── (2) TA#

接尾辞：

[A, ATA, ATATA, ATATATA, ATATATATA, ATATATATATA, TA, TATA, TATATA, TATATATA, TATATATATA]
4

1 に答える 1

3

接尾辞木を作成する方法の一般的なヒントは、アルファベットにないことがわかっている人工文字をもう1つ追加することです。私は通常「＃」を追加してから、ATATATATATA＃のサフィックスツリーを作成します。そうすれば、この問題は発生しなくなります。

欠落しているサフィックスは実際には別のサフィックスのプレフィックスとして満たされているため、説明した問題が発生します。最後に人工的なキャラクターを追加すると、これが決して起こらないようになります。

于 2012-04-09T13:54:18.317 に答える