전이 기반 탐색(Transition-based Search)

💡 개념 정의

전이 기반 탐색이란, 오토마톤(automaton)의 상태(state) 간 전이(transition)를 따라가며 입력 문자열을 탐색하거나 일치 여부를 판별하는 방식입니다. 여기서 전이란, 현재 상태에서 특정 문자를 읽었을 때 이동해야 할 다음 상태를 정의하는 규칙이며, 일반적으로 딕셔너리(또는 해시맵) 형태로 구현됩니다.

⚙️ 동작 방식

1. 초기 상태에서 입력 문자열의 첫 문자를 읽습니다.
2. 해당 문자가 정의된 전이를 통해 다음 상태로 이동합니다.
3. 이후 문자를 하나씩 처리하면서 상태를 전이해 갑니다.
4. 마지막 상태까지 도달했을 때 특정 조건(예: 문자열 일치, 패턴 발견 등)을 확인합니다.

이 과정은 상태 간 전이만으로 이루어지므로 인덱스 기반 비교 없이도 효율적인 탐색이 가능합니다.

🆚 배열 기반 탐색과의 차이점

구분	전이 기반 탐색	배열 기반 탐색
탐색 방법	상태 전이를 따라 이동	배열 인덱스를 순차적으로 비교
구조	오토마톤 (그래프 구조)	배열 또는 문자열
대표 예시	Suffix Automaton, Aho-Corasick, KMP 실패 함수	Brute-force, Rabin-Karp 등
장점	다중 패턴, 빠른 탐색, 전처리 기반	구현 간단, 메모리 절약
특징	상태와 전이 딕셔너리를 활용	문자열 인덱스를 직접 비교

🔍 대표 알고리즘

✅ Suffix Automaton (SAM)

주어진 문자열의 모든 접미사를 상태로 표현하며, 서브스트링 존재 여부, 중복 횟수 등을 빠르게 계산할 수 있는 자동 기계입니다.

stateDiagram
  direction LR
  S0 --> S1: 'a'
  S1 --> S2: 'b'
  

문자열 "ab"는 S0 → S1 → S2 로 전이됨으로 존재함을 확인할 수 있습니다.

sam = SuffixAutomaton()
sam.build("ababa")
print(sam.contains("aba"))  # True
  

✅ Aho-Corasick Automaton

트라이 기반의 다중 문자열 탐색 알고리즘으로, 실패 링크(failure link)를 통해 빠르게 여러 패턴을 동시에 탐색할 수 있습니다.

patterns = ["he", "she", "his", "hers"]
text = "ushers"
matches = ac.search(text)
for pos, word in matches:
    print(f"{word} found at index {pos}")
  

출력:
she found at index 2
he found at index 3
hers found at index 2

✅ KMP (Knuth-Morris-Pratt)

실패 함수(failure function)를 통해 불일치 시 돌아갈 위치를 전이로 미리 정의해 놓는 방식입니다. 전이 기반 탐색의 단순한 형태로 볼 수 있습니다.

🧠 요약

• 전이 기반 탐색은 입력 문자열을 상태 전이를 통해 구조적으로 탐색합니다.
• SAM은 부분 문자열 탐색에 강하며, Aho-Corasick은 다중 패턴에 특화되어 있습니다.
• KMP는 간단한 실패 전이 기반 탐색으로 효율적인 부분 문자열 검색을 지원합니다.

 

---

🔍 Suffix Automaton에서 전이 기반 탐색의 장점

✅ 1. 빠른 부분 문자열 탐색

• SAM은 모든 부분 문자열을 포함하도록 설계되어 있으므로,
• 어떤 문자열이 주어졌을 때, 각 문자를 전이 딕셔너리에서 O(1)에 확인하면서 다음 상태로 이동할 수 있습니다.
• 결국 길이가 m인 문자열에 대해 O(m) 시간에 포함 여부를 판단할 수 있습니다.

📌 예: 문자열 "ababa"에 대해 "bab"이 존재하는지 확인할 때
S0 --'b'--> S2 --'a'--> S3 --'b'--> S4 경로 탐색

✅ 2. 트리 기반 구조보다 메모리와 효율성 개선

• Suffix Tree는 포인터 기반으로 구성되므로 탐색 시 분기점 비교가 복잡해질 수 있음
• 반면, SAM은 DAG(유향 비순환 그래프) 구조로 중복 부분 문자열 상태를 통합하여 탐색이 효율적입니다.

---

🆚 전이 기반 vs 정렬 기반 비교

기준	Suffix Array	Suffix Automaton
탐색 방식	이진 탐색 + 접두사 비교	상태 전이 따라 이동
시간 복잡도	O(m log n)	O(m)
활용 구조	정렬된 배열 + LCP	상태 + 전이 딕셔너리
특징	정렬 기반이지만 중간 비교 발생	문자마다 딕셔너리 전이

---

🧑‍💻 구현 예시: SAM 전이 기반 탐색

def contains(sam, pattern):
    current = 0
    for c in pattern:
        if c in sam.states[current].next:
            current = sam.states[current].next[c]
        else:
            return False
    return True

---

✅ 요약

• 전이 기반 탐색은 현재 상태에서 다음 문자의 전이 정보를 따라가는 방식입니다.
• Suffix Automaton에서는 이 방식 덕분에 모든 부분 문자열 포함 여부를 O(m)에 탐색할 수 있습니다.
• Suffix Array의 정렬 기반 이진 탐색보다 빠르고 직관적입니다.

📈 Mermaid.js 시각화 1: "ababa"에서 "bab" 탐색

flowchart LR
    %% 강조 스타일 정의
    classDef highlight fill:#ffd,stroke:#f66,stroke-width:2px

    %% 상태 정의
    S0((S0<br>len=0))
    S1["S1<br>len=1"]
    S2["S2<br>len=2"]
    S3["S3<br>len=3"]
    S4["S4<br>len=4"]
    S5["S5<br>len=5"]

    %% 전이 (Transition)
    S0 -->|a| S1
    S0 -->|b| S2
    S1 -->|b| S2
    S2 -->|a| S3
    S3 -->|b| S4
    S4 -->|a| S5

    %% 링크 (Suffix Link)
    S1 -.->|link| S0
    S2 -.->|link| S0
    S3 -.->|link| S1
    S4 -.->|link| S2
    S5 -.->|link| S3

    %% 탐색 경로 강조: "bab"
    class S2,S3,S4 highlight

📈 Mermaid.js 시각화 2: "banana"에서 "ana" 탐색

flowchart LR
    %% 강조 스타일 정의
    classDef highlight fill:#ffd,stroke:#f66,stroke-width:2px

    %% 상태 정의
    S0((S0<br>len=0))
    S1["S1<br>'b'<br>len=1"]
    S2["S2<br>'a'<br>len=1"]
    S3["S3<br>'n'<br>len=1"]
    S4["S4<br>'ba'<br>len=2"]
    S5["S5<br>'an'<br>len=2"]
    S6["S6<br>'na'<br>len=2"]
    S7["S7<br>'ana'<br>len=3"]
    S8["S8<br>'nana'<br>len=4"]

    %% 전이 (Transition)
    S0 -->|b| S1
    S0 -->|a| S2
    S0 -->|n| S3
    S1 -->|a| S4
    S2 -->|n| S5
    S5 -->|a| S7
    S3 -->|a| S6
    S6 -->|n| S8

    %% 링크 (Suffix Link)
    S1 -.->|link| S0
    S2 -.->|link| S0
    S3 -.->|link| S0
    S4 -.->|link| S2
    S5 -.->|link| S3
    S6 -.->|link| S3
    S7 -.->|link| S5
    S8 -.->|link| S6

    %% 탐색 경로 강조: "ana"
    class S2,S5,S7 highlight

설명:
"S0 --'a'→ S2 --'n'→ S5 --'a'→ S7"로 따라가며 "ana"의 존재를 빠르게 확인할 수 있습니다.


https://celbeing.tistory.com/120

결정적 유한 오토마타(DFA, Deterministic Finite Automata)

https://ko.wikipedia.org/wiki/%EC%98%A4%ED%86%A0%EB%A7%88%ED%83%80_%EC%9D%B4%EB%A1%A0

오토마타 이론 - 위키백과, 우리 모두의 백과사전