2

サフィックス配列自体の定義は、文字列のすべてのサフィックスのソートされた配列であることを知っています。しかし、ここでこの並べ替え操作の重要性を理解しようとしていますか? 文字列のすべての接尾辞の配列を作成し、それを並べ替えずに LCP 配列の構築に進むとします。この状況で、最長回文部分文字列などの一般的な問題を解決しようとすると、何が失われるのでしょうか。最長の繰り返し部分文字列?

4

1 に答える 1

7

サフィックス配列内ですべてのサフィックスをソートする必要がある主な理由は 2 つあります。

まず、S と T が文字列の場合、次のことがわかります。

T は、S の接尾辞の接頭辞である場合にのみ、S の部分文字列です。

たとえば、S が「回避」で、T が「ida」の場合、T は接尾辞「idance」の接頭辞であるため、S の部分文字列です。したがって、S の部分文字列に関する迅速なクエリを必要とするアプリケーションは、S の接尾辞のプレフィックスを検索するという観点で言い換えることができます。

これを考えると、S のサフィックスのプレフィックスを検索することに興味がある場合は、これらのサフィックスをデータ構造に格納して、すばやく検索できるようにすることが理にかなっています。サフィックスを配列に入れると、それらをソートしたままにしておくと、さまざまなプレフィックスがどこにある必要があるかを効率的に調べることができます。したがって、接尾辞配列を S のすべての接尾辞をソート順に格納した配列にすることで、接尾辞の接頭辞、つまり S の部分文字列をすばやく検索できます。

LCP 配列に関する 2 番目の質問については、接尾辞がソートされていない場合にそれらを計算できますか? また、ソートすると何が失われますか? -ソートされていない接尾辞の配列であっても、任意の配列に対してそれらを絶対に計算できるため、これを実行できなかった根本的な理由はありません。ただし、ソートされたサフィックス配列の LCP 配列には、ソートされていないサフィックス配列の LCP 配列にはない優れたプロパティが多数あります。たとえば、接尾辞配列内の LCP 配列を使用して、対応する接尾辞ツリー内の内部ノードの深さを決定したり、最長共通拡張などを計算したりできます。

並べ替えられたサフィックス配列と LCP の非常に重要なプロパティの 1 つは、すべての文字列のペアワイズ LCP 情報を計算すると、LCP 配列に対して範囲最小クエリを実行することで、任意の文字列ペアに対して LCP を計算できることです。これが機能する理由は、サフィックスがソートされている場合、隣接する文字列間のオーバーラップの最大量が保持されるためです。これは、配列がソートされていない場合には機能しません (これについては、最後にもう一度説明します)。

具体的にどこで問題が発生するかを確認するために、最も長く繰り返される部分文字列の問題を考えてみましょう。接尾辞配列を使用した通常の線形時間アルゴリズムは次のとおりです。

  • 文字列 T のサフィックス配列を作成します。
  • 一般化されたサフィックス配列の LCP 配列を構築します。
  • 接尾辞配列全体を反復処理し、LCP 値が最大である文字列を見つけます。

この最後のステップが機能する理由を考えることが重要です。2 回繰り返される部分文字列を考えて、それを S と呼びます。どの部分文字列もサフィックスのプレフィックスであるため、これは文字列 Sα と Sβ が文字列 T のサフィックスでなければならないことを意味します。サフィックス配列をソートされた順序で格納すると、すべての文字列が接頭辞 S で始まる は、接尾辞配列に連続して表示されます (理由がわかりますか?)。したがって、S が最も長く繰り返される部分文字列である場合、S で始まる最初の接尾辞には、長さ |S| の次の文字列を持つ LCP があります。

ここで、配列をソートせずにこれを行うとどうなるかを考えてみましょう。その場合、S が最も長く繰り返される部分文字列である場合、文字列 Sα と Sβ は引き続き文字列 T の接尾辞になります。それらを見つけるための時間アルゴリズム。たとえば、文字列を考えてみましょう

abracadabra

ソートされていないサフィックス配列は

abracadabra$
bracadabra$
racadabra$
acadabra$
cadabra$
adabra$
dabra$
abra$
bra$
ra$
a$
$

LCP情報で注釈を付けた後、取得します

0 abracadabra$
0 bracadabra$
0 racadabra$
0 acadabra$
0 cadabra$
0 adabra$
0 dabra$
0 abra$
0 bra$
0 ra$
0 a$
  $

したがって、このアルゴリズムでは「abra」が検出されないことがわかります。これらは連続していないからです。すべてのペアを試してみれば、それが「abra」であることがわかる可能性はありますが、大きな文字列の場合は効率的ではありません。

ソートされた接尾辞配列内の文字列の隣接ペアに関する LCP 情報を使用して、ソートされた接尾辞配列内の任意の文字列ペアに関する LCP 情報を計算できることを前に述べました。文字列がソートされていない場合、これは当てはまりません。上記のように、文字列の一部にはゼロ以外の共通プレフィックスが確かにあるにもかかわらず、すべての文字列の隣接ペアワイズ LCP が 0 であることがわかります。

お役に立てれば！

于 2014-06-14T17:22:19.450 に答える