本記事は、「データ構造とアルゴリズム Advent Calendar 2018」 23日目の記事です。
22日目の記事は @MatsuTaku 氏による「Numbered Automaton による文字列の完全ハッシュ」でした。
24日目の記事は @yasufumy 氏による「ヒープをわかりやすく解説してみた」です。
23日が空いていたので、急遽書くことにしました。
推敲が足りない部分もあるかと思いますので、気づいた点は是非ご指摘ください。
本記事では、「Shortest Unique Substring Query」という問題についてお話します。
本アドベントカレンダーシリーズ3年目にして、初めて文字列っぽい記事を書きます。。。
よろしくお願いします。
問題定義
SUS の定義
ここでは Shortest Unique Substring (以下 SUS) を定義します。
SUS は、文字列 $T$ と区間 $[s, t]$ に対して定義されます1。$T$ の部分文字列 $w = T[x..y]$ が以下をすべてみたすとき、$w$ は $[s, t]$ に対する SUS であるといいます。
- 区間 $[x, y]$ は区間 $[s, t]$ を包含している
- $T$ 中の $w$ の出現回数はちょうど 1 回（= Unique）である
- $w$ は、上記 1., 2. を満たす文字列の中で最短(= Shortest)である
文字列 $T$ 中の区間 $[s, t]$ に対するすべての SUS からなる集合2 $SUS_T([s, t])$ で表すことにします。SUS Query は、 $SUS_T([s, t])$ を求める問題です。
SUS Query
事前入力： 長さ $N$ の文字列 $T$
クエリ入力： 区間 $[s, t]$
出力： $[s, t]$ に対するすべての SUS , 即ち $SUS_T([s, t])$
例
$T = $aabaabbaabaaabb, $[s, t] = [4, 6]$ の場合の例を下図に示します。
ここで、$w = T[2..6]$ が $[4, 6]$ に対する SUS になっていることを定義に沿って確認しましょう。
- 区間 $[2, 6]$ は区間 $[4, 6]$ を包含しています。
- $T$ 中の $w = $abaab の出現回数はちょうど 1 回です。
- $w = $abaab は、上記 1., 2. を満たす文字列の中で最短です。具体的には、区間 $[4, 6]$ を包含する長さ 4 の文字列 baab, aabb を見ると、どちらも $T$ 中で 2 回以上出現しています。
同様に、$T[3..7], T[4..8]$ も SUS であることが確認できます。
提案アルゴリズムの計算量
結論から言うと、SUS Query は以下の計算量で解くことができます。
前処理時間：$O(N)$ time
領域：$O(N)$ words
クエリ時間：$O(k)$ time ($k$ は出力する解の個数)
以下では、上記の計算量を達成するアルゴリズムの概要を紹介します。
準備
MUS の定義
アルゴリズムの説明に入る前に、Minimul Unique Substring (以下 MUS） という概念を定義します。
文字列 $T$ の部分文字列 $T[x.. y]$ がユニーク（出現回数が1回）であり
、かつ $T[x+1.. y]$ と $T[x.. y−1]$ がともにユニークでない（出現回数が2回以上）であるとき、$T[x.. y]$ を $T$ 中の
MUS といいます。
ひとことでいうと、MUS はユニークな部分文字列のうち極小なものです。
例
SUS の例と同じ文字列 $T = $aabaabbaabaaabb の場合の MUS を下図に示します。
ここでは、$T[6..8] = $bba が MUS になっていることを定義に沿って確認しましょう。
まず、bba は $T$ 中でユニークです。そして、左1文字を削った ba は、$T$ 中で2回以上出現しています。さらに、右1文字を削った bb も、$T$ 中で2回以上出現しています、よって、bba は MUS であることがわかります。
MUS の性質
一般に、$T$ 上のユニークな部分文字列 $T[i,,j]$ は $[1, N]$ 上の部分区間 $[i, j]$ と 1:1 に対応付けることができます3。この対応付けにより、MUS の集合は対応する区間の集合と同一視することができます。
また、定義より、任意の 2 つの MUS は互いにネストしません。これはほぼ自明4な性質ですが、かなり重要な性質です。この性質からは、MUS の個数は $N$ 以下ということも言えます。
SUS と MUS の関係
MUS の定義から、ユニークな部分文字列は必ずある MUS を含みます。そして逆に、 任意の MUS を 1 つでも含んでいればその部分文字列はユニークと言えます。
これを踏まえて、前述の SUS の定義を思い出してみましょう。
2. の条件(ユニークか否か)は、MUS との包含関係を調べることで判定ができそうです。また、1.の条件(区間同士の包含関係)は明らかに定数時間で判定できます。3. の条件(最短性)はちょっと骨が折れそうですが、MUS の長さ列に対する RmQ などを駆使すると実は効率よく最短を見つけることができます。
アルゴリズム
前処理ではまず、MUS の集合を計算します。
これは Suffix Array / LCP Array を利用することで $O(N)$ 時間で求めることができます。詳細は割愛します。論文5をご参照くださいませ。
---2019/02/13 追記---
MUS に関する資料をgoogle drive で公開しています．MUS を求めるアルゴリズムについて詳細を知りたい方はぜひご覧ください．
---追記ここまで---
さて、MUS 集合は区間集合と同一視できました。さらに MUS は互いにネストしないという性質も持っていました。さらにさらに、SUS は必ず MUS を含むということ、 ある条件下での最短文字列であることという性質もありました。
本アドベントカレンダーの読者でかつ勘のいい方は気づいたかもしれませんが、SUS Query は最終的に最短包含区間問題に帰着できます。最短包含区間問題については私が11日目に書いた記事をご参照ください。どのように帰着するかの詳細は、またの機会に...
従って(投げやり)、SUS Query は以下の計算量で解くことができます。
前処理時間：$O(N)$ time
領域：$O(N)$ words
クエリ時間：$O(k)$ time ($k$ は出力する解の個数)
また、最短包含区間問題の記事で言及したように、既知の簡潔データ構造を利用すると以下の計算量を達成できます。
前処理時間：$O(N)$ time
領域：$2N + 2m + o(N)$ bits ($m$ はMUSの個数)
クエリ時間：$O(k)$ time ($k$ は出力する解の個数)
めでたしめでたし
おわりに
今回は「Shortest Unique Substring Query」という問題についてお話しました。
後半は「はい帰着！おわり！詳細は論文で！」って感じになってしまいました。需要があれば修正・追記していこうと思います。
なお、本記事のほとんどの内容は、いくつかの論文5 6 7 の結果を参考にしつつ説明を再構築したものです。詳細部分に興味がある方はどうぞ。
これを機に、SUS について少しでも興味を持っていただけたら幸いです。
余談
私が Qiita でアイコンにしているカニは「サスガニくん」というオリジナルキャラクターで、SUS (さす) から生まれました。顔に S U S の文字が刻まれていることがわかります。わかりますよね、さすがに。
-
部分文字列 $T[s..t]$ ではなく、区間 $[s, t]$ に対して定義されていることに注意してください。 ↩
-
陽にすべての文字列を出力すると長さ分の時間がかかってしまうため、実際には例にあるように、SUS に対応する区間の集合を求めます。 ↩
-
$T[i,,j]$ がユニークでない場合、$[i, j]$ 以外の位置にも出現するため、前述の方法では 1:1 対応を作ることはできません。 ↩
-
ある 2 つの MUS が包含関係にあると仮定すると、「長い MUS の中に短い MUS が包含されている」という状態になってしまうため、極小性に矛盾します。 ↩
-
K. Tsuruta, S. Inenaga, H. Bannai, and M. Takeda. Shortest unique substrings queries in optimal time. In Proc. SOFSEM 2014, pages 503–513, 2014. ↩ ↩2
-
X. Hu, J. Pei, and Y. Tao. Shortest unique queries on strings. In Proc. SPIRE 2014, pages 161–172, 2014. ↩
-
T. Mieno, S. Inenaga, H. Bannai, and M. Takeda. Shortest unique substring queries on run-length encoded strings. In Proc. MFCS 2016, pages 69:1–69:11, 2016. ↩