2

Lempel-Ziv 圧縮を実装していて、疑問が頭に浮かびました。

「辞書」と文字列が与えられます。辞書に含まれている、文字列の最長のプレフィックスを計算できるようにしたいと考えています。

それは文字列を与えられます:

0 : AABB
1 : ABA
2 : AAAB

およびクエリ文字列 'AABBABA' '0' を返すルックアップを実行できるようにしたいと考えています。これは、プレフィックスの長さに比例して時間内に実行する必要があります。

次に、新しい接頭辞「AABBAB」を辞書に一定時間で追加できるようにしたいと考えています。

これを行うための標準的で簡単な方法/アルゴリズムはありますか?

私の最初のアイデアは、ポインターのリストを使用して標準の n 方向ツリーを構築し、これを検索することでしたか?

4

1 に答える 1

3

余分な文字がある場合でもリーフノードを返すことを除いて、単純なトライルックアップについて説明しています。

n-wayツリーで何を考えているかはわかりませんが、明らかな解決策であるため、おそらくまったく同じです：v）。より効率的にしたい場合は、さまざまな種類の試行を調べることができます。

于 2012-04-14T11:54:37.943 に答える