기술 요약: 거의 최적의 내부 사전 매칭 (Nearly Optimal Internal Dictionary Matching)

문제 정의

본 논문은 내부 사전 매칭 (Internal Dictionary Matching, IDM) 문제를 다룬다. 이 설정에서는 선형 정렬 가능한 알파벳 위에 놓인 길이 $n$인 거대한 텍스트 $T$가 사전에 주어진다. 사전 $D$는 $T$의 부분 문자열 $d$개로 구성된다. 목표는 $T$와 $D$를 전처리하여, 임의의 $T[l, r]$ 부분 문자열 내에서 $D$에 속하는 패턴들의 발생을 효율적으로 질의하는 것이다.

본 논문은 다섯 가지 특정 질의 유형에 초점을 맞춘다:

1. Exists($l, r$): $D$의 패턴 중 적어도 하나가 $T[l, r]$에 존재하는지 결정한다.
2. Report($l, r$): $T[l, r]$ 내에 존재하는 모든 $D$ 패턴의 발생 위치를 보고한다.
3. ReportDistinct($l, r$): $T[l, r]$에 존재하는 모든 서로 다른(distinct) $D$ 패턴을 보고한다.
4. Count($l, r$): $D$에 속한 모든 패턴의 총 발생 횟수를 센다.
5. CountDistinct($l, r$): $T[l, r]$에 존재하는 서로 다른 $D$ 패턴의 개수를 센다.

이 문제는 고전적인 사전 매칭과 내부 패턴 매칭(IPM)을 일반화한 것이다. 이는 특히 패턴의 총 길이 $L$이 패턴의 개수 $d$보다 훨씬 큰 "내부" 사전(예: 모든 팰린드롬, 제곱, 또는 비원시적 부분 문자열의 사전)의 경우에 매우 유용하며, 솔리의 복잡도는 $L$이 아닌 $n$과 $d$에 의존해야 한다.

방법론: 기본 부분 문자열 구조 (Basic Substring Structure, BASS)

본 논문의 핵심 기여는 **기본 부분 문자열 구조 (Basic Substring Structure, BASS)**라고 명명된 새로운 $O(n)$ 크기의 데이터 구조를 제안하는 것이다. BASS는 2차원 그리드와 동치 클래스(equivalence classes)를 사용하여 $T$의 부분 문자열들을 조직한다.

1. 그리드와 동치 클래스

이 구조는 모든 부분 문자열 $T[l, r]$을 2D 그리드 상의 점 $(l, r)$로 매핑한다.

• 동치 클래스: 두 부분 문자열은 그들의 "확장(extensions)"이 동일할 때 동치이다. 부분 문자열 $t$의 확장 $ext(t)$는$t$가 부분 문자열이고$|occ(t)| = |occ(s)|$를 만족하는 가장 긴 문자열$s$를 의미한다. 이 개념은 **압축 순환 단어 그래프(Compact Acyclic Word Graph, CDAWG)**의 노드와 대응된다.
• 블록(Blocks): 그리드 내에서 각 동치 클래스는 계단 모양의 경계를 가진 "블록"을 형성한다. 블록 $B$는 파라미터인 행 범위 $[left_B, right_B]$, 상단 경계 $top_B$, 그리고 비감소 수열인 하단 경계 $b_{left_B}, \dots, b_{right_B}$에 의해 정의된다.
• 특성: 본 논문은 동일한 동치 클래스 내의 모든 블록이 (평행 이동을 제외하고) 동일한 형태를 공유함을 증명한다. 또한, 모든 서로 다른 블록들의 왼쪽 및 상단 경계 길이의 합은 $O(n)$이다.

2. 트리 매핑

BASS는 블록 간의 관계를 공식화하기 위해 두 가지 변형된 접미사 트리(suffix tree)를 통합한다:

• PreTree($T$): $T$의 접미사 트리. 열을 공유하는 블록들 사이의 관계(조상-자손 관계)를 포착한다.
• SufTree($T$): 역순 문자열 $rev(T)$의 접미사 트리. 행을 공유하는 블록들 사이의 관계를 포착한다.
  이 트리들은 그리드 좌표를 노드로 효율적으로 매핑하여, 특정 부분 문자열의 동치 클래스와 블록 내 위치를 $O(1)$ 시간에 찾을 수 있게 한다.

3. 질의 처리 전략

• Count 질의: 알고리즘은 카운팅 문제를 2D 범위 카운팅 문제로 환원한다. 블록 경계를 따라 패턴 발생의 부분 합을 저장하고, Chan과 Pătraşcu의 연구에 기반한 정적 2D 범위 카운팅 데이터 구조를 활용함으로써 질의 시간을 최적화한다.
• CountDistinct 질의: 이는 가장 복잡한 질의이다. 저자들은 이 문제를 두 부분으로 분해한다:
  1. 전체 발생 횟수($A_1$)에서 "키 포지션"( $T[l, r]$의 가장 짧은 접미사 중 정확히 한 번 나타나는 접미사)에 의해 결정되는 특정 접미사 범위 내의 발생 횟수를 뺀다.
  2. 접미사 트라이(trie)의 구조에 기반하여 중복 계산된 패턴($A_2$)을 뺀다.
     이를 효율적으로 처리하기 위해, 본 논문은 쿼리 범위가 변함에 따라 발생 횟수의 변화를 추적하기 위해 Link-Cut Tree에서 유도된 **이벤트 세트(event sets)**를 도입하며, 이를 통해 영속적(persistent) 데이터 구조를 사용하여 $A_2$를 계산할 수 있게 한다.

주요 결과 및 기여

본 논문은 다섯 가지 모든 질의 유형에 대해 거의 최적인 질의 및 전처리 시간을 달하는 알고리즘을 제시한다. 결과는 다음과 같이 요약된다 (여기서 $\tilde{O}$는 다항 로그 인자를 생략한다):

질의 유형	전처리 시간	질의 시간	공간 복잡도
Exists	$O(n + d)$	$O(1)$	$O(n + d)$
Report	$O(n + d)$	$O(1 + x)$	$O(n + d)$
Count	$O(n + d\sqrt{\log n})$	$O(\frac{\log n}{\log \log n})$	$O(n + d)$
ReportDistinct	$O(n \log n + d)$	$O(1 + x)$	$O(n + d)$
CountDistinct	$O(n \log^2 n + d\sqrt{\log n})$	$O(\log n)$	$O(n \log^2 n + d)$

참고: $x$는 출력의 길이이다.

구체적 개선 사항

1. CountDistinct: 본 논문은 이전 연구 [16]의 미결 과제를 해결하여, $\tilde{O}(n+d)$ 전처리를 통해 CountDistinct 질의에 $\tilde{O}(1)$ 시간(구체적으로 $O(\log n)$) 내에 답하는 최초의 알고리즘을 제공한다. 기존의 최선 결과는 $\tilde{O}(n^2/m + d)$의 전처리가 필요한 $\tilde{O}(m)$ 질의 시간을 요구했다.
2. Count: 질의 시간이 $O(\frac{\log^2 n}{\log \log n})$에서 $O(\frac{\log n}{\log \log n})$으로 개선되었으며, 저자들은 이것이 2D 범위 카운팅의 하한(lower bound)에 근거하여 $\tilde{O}(n)$ 크기의 데이터 구조에 대해 최적임을 증명한다.
3. ReportDistinct: 질의 시간이 $O(\log n + x)$에서 $O(1 + x)$로 개선되었다.
4. 일반적 적용 가능성: 저자들은 BASS가 범위 최장 공통 부분 문자열 (Range Longest Common Substring, RLCS) 문제와 같은 다른 내부 질의 문제에도 적용될 수 있음을 보여주며, 기존의 $O(\log n)$ 질의 시간을 $O(1)$로 개선하였다.

의의 및 주장

본 논문은 BASS가 거의 최적의 질의 및 전처리 시간을 가지며 모든 유형의 IDM 질의를 처리할 수 있는 최초의 데이터 구조라고 주장한다. 서로 다른 질의 유형을 위해 별도의 맞춤형 접근 방식을 취했던 이전 연구들과 달리, BASS는 통합된 프레임워크를 제공한다.

본 연구의 의의는 다음과 같다:

• 최적성: 동적 사전 매칭에 대한 알려진 조건부 하한(subpolynomial factor까지 고려)과 일치하는 성능을 보이며, Count 질의에 대해 무조건적 최적성을 증명한다.
• 통합 프레임워크: 그리드 구조 내에 동치 클래스를 성공적으로 조직함으로써 CDAWG 개념과 효율적인 부분 문자열 질의 사이의 간극을 메우는 연결 고리를 구축하였는데, 이는 이전 문헌에서는 충분히 탐구되지 않은 부분이다.
• 대규모 사전 처리: 복잡한 내부 사전(예: 모든 팰린드롬 또는 제곱)에 적합하도록, 복잡도가 패턴의 총 길이 $L$이 아닌 패턴의 개수 $d$에 의존하는 솔루션을 제공한다.

저자들은 동적 사전(패턴이 추가되거나 삭제될 수 있는 환경)의 경우, $\tilde{O}(n^\alpha)$ 시간 내에 업데이트를 처리하고 $\tilde{O}(n^{1-\alpha})$ 시간 내에 CountDistinct 질의에 답하는 알고리즘을 구축할 수 있으며, 이는 해당 설정의 알려진 조건부 하한과 일치한다고 언급한다.