[작성 중단] On Shortest Unique Substring Queries

On Shortest Unique Substring Queries

- Jian Pei, Wush Chi-Hsuan Wu, Mi-Yen Yeh.

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6544887&tag=1

과제 때문에 찾았던... 논문입니다.

뭐, 정리해보죠.

처음 적는 학문적인 글이 전공이 아닌건 아쉽... 지 않네요.

제목에 심플하게 적혀있듯이 Shortest Unique Substring(최단 유일 부분문자열)에 대한 내용입니다.

문자열 S가 주어졌을 때, S의 부분 문자열은 S의 길이 n에 대해 n(n+1)/2개 존재합니다.

단순한 방법으로 모든 substring을 탐색하기 위해서는 O(n²)번의 연산을 필요로 하죠.

엄청 느리네요...

그래서, 리뷰하고자 하는 논문에서는 suffix tree를 이용하여 O(n) 만에 Shortest Unique Substring을 구하는 방법을 소개한다고 이야기하고 있습니다.

이 논문이 2013년에 게재되었는데 그 전에는 O(n²) 보다 빠른 방법이... 없었을까요?

있었겠죠? 안찾아봐서 모르겠지만.

II. SHORTEST UNIQUE SUBSTRING QUERIES

A. Shortest Unique Substring Queries

S: String.

n: length of S, |S| = n.

S[i]: S의 i번째(i-th position) 문자 (1 ≤ i ≤ n).

S[i, j]: S[i]부터 S[j]까지의 문자열 (1 ≤ i ≤ j ≤ n). 부분문자열.

설명에 필요한 기본적인 표기입니다.

이걸 이용한 정의와 정리를 짚고 넘어가겠습니다.

S[i, j]의 길이 |S[i, j]| 는 j-i+1 입니다.

S[i, j]는 i ≤ p ≤ j 일 때, p-th position을 포함하고 있습니다.

또한 i ≤ i' ≤ j' ≤ j 일 때, S[i, j]는 S[i', j']을 포함하고 있습니다.

어렵지 않은 이야기네요.

i = 2, j = 10인 부분 문자열 S[2, 10]이 있다면 S[2, 10]은 p = 5인 S[5] 문자도 포함하고 있을테고, S[4, 8] 같은 부분 문자열도 포함하고 있습니다.

두 문자열 X, Y에 대하여

(1) |X| = |Y| 이고 1 ≤ i ≤ |X|인 모든 i에 대해 X[i] - Y[i]를 만족하면 X와 Y는 같은 문자열 X = Y 입니다. 

(2) |X| ≤ |Y| 이고 1 ≤ i ≤ |Y| - |X| + 1인  어떤 i에 대해 X = Y[i, i + |X| - 1]을 만족하면 X는 Y의 substring(부분문자열)이고 X ⊆ Y 로 표현됩니다. 

(3) X ⊆ Y 이고 X와 Y가 다르다면 X는 Y의 proper substring(진부분문자열)이고 X ⊂ Y 로 표현됩니다.

두 문자열에 대한 관계를 나타냈는데...

(1)은 동등관계, (2)와 (3)은 종속관계에 대해 나타냈네요.

(3)은 진부분집합(proper set)처럼 자기 자신이 아닌 부분문자열을 proper substring이라고 표현하였기에 진부분문자열이라고 쓰면 바로 알 수 있습니다.

정의 1. Minimal unique substring (MUS)

문자열 S의 substring S[i, j] 와 똑같은 S[i', j']가 존재하지 않으면 S[i, j]는 유일(unique)합니다. ( i ≠ i', j ≠ j' )

S[i, j]가 unique하고 S[i, j]의 proper substring인 S[i', j'] 들 중 unique한 문자열이 존재하지 않으면 (i ≤ i' ≤ j' ≤ j' and j - i > j' - i')

S[i, j]는 minimal unique substring(MUS)라고 합니다.

예시 (MUS).

문자열 S = abbbcabb

S의 길이 |S| = 8 일 때,

S[3, 6] = bbca는 unique하지만 minimal 하지는 않습니다.

S[4, 6] = bca, S[4, 5] = bc, S[5, 6] = ca 역시 unique합니다.

이 중에 S[4, 5], S[5, 6]은 minimal 하다고 표현할 수 있습니다.

minimal은 최소의 라는 뜻을 가지고 있어서 MUS를 최소 유일 부분문자열이라고 표현... 하고싶지만!

바로 다음에 나올, 그리고 논문 제목에서도 사용되는 Shortest unique substring의 Shortest와 혼동하는 경우가 생길 수 있기 때문에

어떻게 표현할지는 미루도록 하겠습니다.

그런데 예시에서 이상한 점이 있습니다.

S[5, 5] = c 가 unique한데 어떻게 S[4, 5]와 S[5, 6]이 minimal 하다고 표현할 수 있을까요?

저자가 실수한 것 같습니다.

정의 2. Shortest unique substring (SUS)

문자열 S와 S에 포함되는 position p가 주어졌을 때,

p를 포함한 S[i, j]가 unique하고 p를 포함한 다른 unique substring S[i', j'] (j' - i' < j - i) 가 존재하지 않는다면

S[i, j]를 position p에서의 shortest unique substring(SUS)라고 합니다.

예시 (SUS).

문자열 S = aabccabbcb

position p = 3 일 때, p를 포함한 SUS는 3개 존재합니다.

S[1, 3] = aab

S[2, 4] = abc

S[3, 5] = bcc

흥미롭게도 S[2, 4]는 MUS인 반면 S[1, 3], S[3, 5]는 MUS가 아닙니다.

S[1, 3]의 proper substring S[1, 2] = aa 가 unique하고

S[3, 5]의 proper substirng S[4, 5] = cc 가 unique하기때문에요.

예시에서 볼 수 있듯이, position p에 대해 하나 이상의 SUS가 존재할 수도 있습니다.

앞으로 position p에서 SUS의 집합(set)을 SUS(p) 라고 나타낼 것입니다.

마찬가지로 position p에 대해 p를 포함한 MUS의 집합을 MUS(p)로 나타낼 것입니다.