기술 요약: 파리크 예산(Parikh Budgets) 하에서의 순열 매칭

1. 문제 정의

본 논문은 일반적인 알파벳 $\Sigma$에 대한 순열(Permutation, Jumbled/Abelian) 패턴 매칭 문제를 다룬다. 길이 $m$인 패턴 $P$와 길이 $n$인 텍스트 $T$가 주어졌을 때, 고전적인 과제는 $T$ 내에 $P$의 기호 다중집합(multiset)과 일치하는 기호 구성을 가진 길이 $m$의 부분 문자열이 존재하는지 판별하는 것이다. 이는 $T$의 윈도우(window)의 파리크 벡터(Parikh vector, 빈도 벡터)가 $P$의 파리크 벡터와 일치하는지 확인하는 것과 같다.

단순한 탐지를 넘어, 저자들은 이를 두 가지 최적화 변형으로 확장한다:

1. 패턴 공급량 하의 최대 가용 부분 문자열 (MFSP): $P$의 기호 개수를 자원 예산(공급 벡터)으로 취급할 때, $P$의 기호 개수에 의해 성분별로 제한되는(즉, $freq(S) \preceq freq(P)$) $T$의 가장 긴 부분 문자열 $S$를 찾는 것이 목표이다.
2. 비중복 선택 (Non-overlapping Selection): $T$ 내의 모든 순열 매치 집합이 주어졌을 때, 서로 중복되지 않는 매치들로 구성된 최대 카디널리티(cardinality)의 부분 집합을 선택한다. 모든 매치는 길이 $m$을 가지므로, 이는 구간 패킹(interval packing) 문제로 모델링된다.

2. 방법론 및 알고리즘

본 논문은 슬라이딩 윈도우 알고리즘과 **파리크 벡터 차이 유지(Parikh-vector difference maintenance)**에 기반한 통합 프레임워크를 제안한다.

2.1 선형 시간 순열 매칭 (기초)

저자들은 $O(n + \sigma)$ 시간과 $O(\sigma)$ 공간 복잡도($\sigma = |\Sigma|$)로 순열 발생을 탐지하는 알고리즘을 제시한다.

• 메커니즘: 모든 윈도우에 대해 빈도 벡터를 재계산하는 대신, 알고리즘은 현재 윈도우 $W_i$에 대한 차이 벡터 $\Delta_i(c) = freq(W_i)(c) - freq(P)(c)$를 유지한다.
• 최적화: 단일 정수 카운터 $nz_i$가 $\Delta_i$의 0이 아닌 엔트리(entry) 개수를 추적한다. 윈도우는 $nz_i = 0$일 때만 매치로 간주된다.
• 업데이트: 윈도우가 슬라이딩할 때, $\Delta$의 두 좌표만 변경된다(한 문자가 나가고 한 문자가 들어옴). 알고리즘은 좌표가 0을 통과하는지 여부에 따라 상수 시간 내에 $nz$를 업데이트한다.

2.2 MFSP: 최대 가용 부분 문자열

패킹 변형 문제를 해결하기 위해, 저자들은 또한 $O(n + \sigma)$ 시간에 실행되는 투 포인터(two-pointer, 슬라이딩 윈도우) 알고리즘을 도입한다.

• 메커니즘: 알고리즘은 윈도우 $T[\ell..r]$과 현재 윈도우에 대한 카운트 배열 cnt를 유지한다. 위반 카운터 viol은 $freq(P)$에 의해 정의된 예산을 초과하는 기호의 개수를 추적한다.
• 로직: 오른쪽 포인터 $r$이 윈도우를 확장한다. 문자를 추가함으로써 위반이 발생하면(즉, cnt가 sup를 초과하면), 왼쪽 포인터 $\ell$은 가용성이 회복될 때까지 전진한다.
• 정당성: 알고리즘은 가용성의 단조성(monotonicity)에 의존한다: 왼쪽에서 윈도우를 축소하는 것은 기호 개수를 증가시키지 않는다. 증명에 따르면, 모든 오른쪽 끝점 $r$에 대해 이 알고리즘은 $r$에서 끝나는 가장 긴 가용 부분 문자열을 찾아내어 전역적 최적성을 보장한다.

2.3 구간 패킹을 통한 비중복 선택

모든 순열 매치가 열거되면(기초 알고리즘을 사용하여), 선택 문제는 **그리디 전략(greedy strategy)**을 통해 해결된다.

• 메커니즘: 모든 매치가 동일한 길이 $m$의 구간에 해당하므로, 이 문제는 서로 겹치지 않는 구간의 최대 개수를 선택하는 문제로 귀결된다.
• 전략: 알고리즘은 텍스트를 왼쪽에서 오른쪽으로 스캔하며, 첫 번째로 사용 가능한 매치를 선택한 후, 다음 비중복 매치를 찾기 위해 $m$ 위치만큼 건너뛴다.
• 증명: 교환 논증(exchange argument)을 통해 이러한 "가장 빨리 끝나는"(또는 동일한 길이를 고려할 때 가장 빨리 시작하는) 그리디 규칙이 최대 카디널리티 집합을 생성함을 입증한다.

3. 주요 기여

1. 통합 프레임워크: 파리크 차이 유지를 사용하여 탐지, 최적화(MFSP), 선택을 처리하는 간결한 슬라이딩 윈도우 접근 방식을 제공한다.
2. 최적 복잡도: 제안된 모든 알고리즘은 $O(n + \sigma)$ 시간과 $O(\sigma)$ 공간을 달성한다. 이는 입력을 읽는 데 필요한 하한선과 일치하며, 일반적인 알파벳에 대해 최적이다.
3. MFSP 정식화: 순열 매칭을 자원 제약이 있는 패킹 문제로 재구성하고, 이를 올바르게 작동하는 선형 시간 투 포인터 알고리즘으로 해결하는 MFSP 문제를 도입하였다.
4. 그리디 최적성: 모든 매치가 동일한 길이를 가질 때, 단순한 그리디 스캔이 비중복 순열 매치를 선택하는 데 최적임을 보여주는 공식적인 증명을 제공한다.

4. 결과 및 실험적 관찰

저자들은 이론적 경계치를 뒷받침하기 위해 경량 실험 관찰 결과를 보고한다:

• 확장성: 순열 매칭과 MFSP 모두 텍스트 길이 $n$에 대해 선형적으로 확장되며, 이는 $O(n + \sigma)$ 분석과 일치한다.
• 성능 요인: 실행 시간은 카운팅 배열/맵의 메모리 액세스 패턴과 매치의 밀도(출력량에는 영향을 미치지만 스캐닝 로직에는 영향을 주지 않음)에 의해 결정된다.
• 알파벳 처리: 큰 알파벳의 경우, 알파벳 압축(알파벳 $P$와 $T$에 등장하는 기호를 정수 $1 \dots \sigma'$로 매핑)은 메모리 사용량을 크게 줄이고 캐시 지역성(cache locality)을 개선하여, $\sigma$가 크더라도 $\sigma'$가 작을 때 효율성을 유지한다.
• MFSP 효율성: MFSP의 위반 카운터 메커니즘은 전체 가용성 체크를 피함으로써, 각 문자가 최대 한 번만 추가되거나 제거되도록 하여 표준 투 포인터의 분할 상환(amortization)을 준수한다.

5. 의의 및 범위

본 논문은 빈도 기반 문자열 매칭을 단순한 탐지 작업이 아니라 **조합 최적화 프리미티브(combinatorial optimization primitives)**의 기초로 자리매김한다.

• 이론적 기여: 고전적인 jumbled matching 문제를 패킹 스타일의 최적화 문제와 연결하여, 타이트한 경계와 간결한 알고리즘을 제공한다.
• 실용적 유용성: 제안된 알고리즘은 단일 패스 스캐닝(single-pass scanning)을 위해 설계되어, 실시간 처리나 자원 제약 하의 최적화(예: 텍스트 처리 시 토큰 예산)가 필요한 응용 분야에 적합하다.
• 한계 명시: 저자들은 자신들의 초점이 인덱스 구축이 아닌 탐지 및 최적화 프리미티브에 있음을 명시적으로 밝힌다. 향로 연구에서 MFSP의 가중치 부여 또는 근사 확장 가능성을 탐구할 수 있음을 인정하지만, 현재의 기여는 정의된 문제들에 대한 엄격한 선형 시간의 정확한 해법에 국한된다.

결론적으로, 본 연구는 파리크 벡터 차이를 유지하고 단순한 그리디 또는 투 포인터 전략을 활용함으로써, 복잡한 순열 매칭 변형 문제를 증명된 정확성과 최적의 선형 시간 복잡도로 해결할 수 있음을 보여준다.