String Matching & Automata

1. Overview

문자열 매칭 및 오토마타(String Matching & Automata, SMA)는 비정형 텍스트 데이터의 바다에서 유의미한 패턴이라는 바늘을 빛의 속도로 찾아내는 시스템의 '지능형 탐지기'입니다.

단순히 한 글자씩 비교하는 방식은 문서가 길어질수록 물리적으로 너무 느립니다. 학습자는 실패한 지점에서 다시 시작하지 않고 '이미 알고 있는 정보'를 활용해 건너뛰는 **KMP(Knuth-Morris-Pratt)**와, 뒤에서부터 비교하여 더 크게 점프하는 Boyer-Moore의 점프 수리 논리를 배웁니다. 또한, 입력 문자에 따라 상태를 옮겨가며 정규 표현식 등을 처리하는 **유한 오토마타(Finite Automata)**의 물리 전이 구조를 익칩니다. 이를 통해 수억 바이트의 로그나 유전체 서열 속에서 특정 키워드를 즉각 발췌하는 고가용성 문자열 엔진 설계 능력을 확보합니다.

2. Scope & Boundaries

In-Scope

• Exact Matching Algorithms: KMP의 실패 함수($\pi$), Boyer-Moore의 나쁜 문자/착한 접미사 규칙
• Multi-pattern Matching: 아호-코라식(Aho-Corasick)을 이용한 다중 패턴의 동시 탐지 물리
• Finite Automata Foundations: DFA(결정적)와 NFA(비결정적)의 상태 전이 및 수용 물리
• Rolling Hash: 라빈-카프(Rabin-Karp)를 이용한 수치 기반 고속 패턴 매칭

Out-of-Scope

• 자연어 처리(NLP) 수준의 의미론적 분석 (11-04-XX 인공지능 영역으로 위임)
• 정규 표현식 엔진의 구체적인 소스 코드 구현 상세

Boundaries

• SMA vs. HCS: 해시 테이블이 '고정 키'를 주소로 바꾼다면, SMA는 '임의 위치의 가변 패턴'을 텍스트 내부에서 물리적으로 훑어내는 동적 탐색에 집중하여 구분합니다.

3. Counterexample

• 단순히 "문자열 검색"이라 설명하는 것은 SMA 학습이 아닙니다. 왜 KMP 알고리즘이 수동적인 비교보다 물리적으로 우월한지 '$2n$번 이내의 연산 보장'이라는 수리적 근거로 증명할 수 있어야 하며, 오토마타의 상태 전이도가 어떻게 메모리 상에서 인덱스 테이블로 물리적 구현(Mapping)되어 분기문(If-else) 없이 정규식을 통과시키는지 분석하지 못한다면 SMA의 진정한 하드웨어 가속 원리를 놓친 것입니다.

4. Prerequisites

• Arrays, Strings & Memory Layout (Basic): 문자 배열 및 오프셋 기초가 필수입니다. (04-01-01 ASL)
• Tries & Suffix Trees (Recommended): 아호-코라식 이해를 위한 트라이 기초가 권장됩니다. (04-02-04 TST)

5. Learning Map

1. The Naive Waste: 일일이 비교하다 시간을 버리는 무차별 대입(Brute-force)의 한계를 목격합니다.
2. The Pi-Function Anchor: 틀렸을 때 어디서부터 다시 볼지 알려주는 '정보의 이정표'를 세웁니다.
3. The Automata State: 문자가 들어올 때마다 춤추듯 자리를 옮기는 상태 기계의 물리를 익힙니다.
4. Massive Jumping: 뒤에서부터 훑으며 불필요한 비교를 통째로 건너뛰는 물리적 도약을 완성합니다.

6. Learning Topics

Basic

Core: KMP와 실패 함수의 원리 (Knuth-Morris-Pratt)

• Why to Learn: 이미 비교한 문자를 다시는 뒤돌아보지 않는 효율적 이동 경로를 확보하기 위해서입니다.
• What to Learn:
  • Prefix & Suffix matching: 패턴 내부에서 겹치는 앞부분과 뒷부분의 수리적 관계
  • Failure Function ($\pi$ table): 불일치 발생 시 돌아갈 최적 위치 계산 물리학
  • Non-backtracking Physics: 텍스트 포인터를 뒤로 돌리지 않고 전진만 시키는 기법
• How to Learn:
  • "ABABAC"와 같은 패턴의 실패 함수 테이블을 직접 그리고, 텍스트 탐색 시 포인터가 어떻게 점프하는지 화살표 그리기 실습
  • KMP가 왜 최악의 경우에도 $O(N+M)$을 보장하는지 선형 시간 복잡도 증명
• Implement: 패턴 전처리를 통한 $\pi$ 배열 생성 및 KMP 탐색 함수

Recommended

Core: 보이어-무어와 고속 점프 (Boyer-Moore Strategy)

• Why to Learn: 실제 'Ctrl+F' 기능 등 대부분의 텍스트 에디터에서 가장 물리적으로 빠르게 작동하기 때문입니다.
• What to Learn:
  • Right-to-Left Comparison: 패턴의 오른쪽 끝부터 비교를 시작하는 역방향 물리학
  • Bad Character Rule: 텍스트의 문자가 패턴에 없으면 통째로 옮기는 수리 규칙
  • Good Suffix Rule: 이미 일치한 뒷부분이 패턴 앞에 또 있는지 확인하여 도약하는 법
• How to Learn:
  • 보이어-무어의 두 가지 점프 규칙 중 더 큰 값을 선택하여 이동하는 논리를 실제 문구 탐색으로 비교 실습
  • $O(N/M)$이라는 경이로운 평균 성능이 어떻게 가능한지 물리적 건너뛰기 횟수 분석
• Implement: 나쁜 문자 테이블을 활용한 기본 Boyer-Moore 점프 엔진

Practical

Core: 아호-코라식과 다중 패턴 매칭 (Aho-Corasick Automata)

• Why to Learn: 스팸 필터나 침입 탐지 시스템처럼 한꺼번에 수천 개의 키워드를 찾아야 할 때의 필수 기술입니다.
• What to Learn:
  • Trie-based Automata: 트라이 구조 위에 실패 링크(Failure link)를 덧씌운 물리 모델
  • Dictionary Matching: 텍스트를 한 번 훑는 동안 모든 패턴의 출현을 잡아내는 선형성
  • Memory vs Speed: 상태 전이 테이블의 크기와 매칭 속도 사이의 트레이드-오프
• How to Learn:
  • "HIS", "SHE", "HE"를 담은 트라이를 만들고, 서로 다른 가지를 잇는 실패 링크의 물리적 의미(접미사 일치) 분석 실습
  • 수천 개의 금지어 목록을 아호-코라식으로 구성 시의 메모리 사용량 측정 실습
• Implement: 실패 링크를 포함한 트라이 기반의 다중 문자열 매칭 클래스

Advanced

Core: 유한 오토마타와 정규 표현식 (Regex Physics)

• Why to Learn: 단순 문자열을 넘어 복잡한 규칙(와일드카드, 반복 등)을 하드웨어 급으로 빠르게 처리하기 위함입니다.
• What to Learn:
  • DFA Strategy: 상충 없는 상태 전이를 통한 결정론적 고속 매칭
  • NFA to DFA Conversion: 비결정론적 규칙을 결정론적 테이블로 바꾸는 수리적 폭발 관리
  • Regex Optimization: 백트래킹 없는 정규식 엔진(예: RE2)이 왜 안전하고 물리적으로 빠른지 이해
• How to Learn:
  • 정규식 (a|b)*abb에 대응하는 NFA 상태 전이도를 그리고, 이를 DFA로 변환하는 부분집합 구성법(Subset construction) 실습
  • 폭발적인 복잡도를 유발하는 'ReDoS(Regex DoS)' 공격의 물리적 원리 분석
• Implement: 특정 패턴 규칙을 입력받아 문자열 유효성을 검사하는 기초 DFA 시뮬레이터

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Construction / Runtime Efficiency (Text Processing) — Search patterns.
• [P1] CS2023 - AL/Algorithms and Complexity (Advanced String Matching) — Core requirements.

Secondary

• [Algorithms on Strings] Maxime Crochemore — Theoretical string matching.
• [Compilers: Principles, Techniques, and Tools (Dragon Book)] Aho — Automata foundations.

Industry

• [Google RE2: A principled approach to regular expression matching] — Real-world industry standard.
• [Elasticsearch: Lucene Automata-based Search] — Search engine implementation.

9. Final Checklist

Primary

• 'KMP 알고리즘'의 실패 함수가 왜 패턴의 '가장 긴 경계(Border)' 정보와 물리적으로 일치하는지 설명 가능한가? (P1)
• 'Boyer-Moore'가 왜 텍스트가 무작위일수록(예: 영문 소설) 'Naive' 방식보다 물리적으로 수십 배 빠른지 입증할 수 있는 가? (P1)

Secondary

• 유한 오토마타에서 DFA와 NFA의 물리적 실행 메모리 차이와 검색 속도의 우열을 수리적으로 소통 가능한가?
• 라빈-카프(Rabin-Karp) 알고리즘에서 해시 충돌(Hash collision)이 발생했을 때의 물리적 대응 절차를 도출할 수 있는 가?

Industry

• 고성능 네트워크 방화벽 설계 시, 수천 개의 악성 시그니처를 실시간으로 탐색하기 위해 왜 아호-코라식이 물리적으로 필수적인지 기술할 수 있는 가? (SFIA)
• 정규 표현식 엔진 도입 시, 백트래킹으로 인한 '스택 오버플로우' 지연 공격을 방지하기 위한 보안적 최적화 방안을 제안할 수 있는 가?