아호-코라식 알고리즘
아호-코라식 알고리즘은 여러 패턴을 하나의 트라이와 실패 링크로 결합하여 텍스트를 한 번에 검색한다 다중 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순...
| 분류 | 알고리즘 · 다중 문자열 패턴 검색 |
|---|---|
| 핵심 문제 | 여러 패턴을 하나의 트라이와 실패 링크로 결합하여 텍스트를 한 번에 검색한다 |
| 방법 | 패턴 집합으로 트라이를 만들고 BFS로 실패 링크를 구성한다 |
| 계산 비용 | 트라이 구축과 실패 링크 O(총 패턴 길이×문자 집합 표현), 검색 O(텍스트 길이+발견 수) 형태 |
| 적용 조건 | 패턴 집합과 문자 인코딩·중복 출력 정책을 정해야 한다 |
| 관련 활용 | 악성 서명 탐지·사전 필터링·다중 키워드 검색에 사용한다 |
| 관련 이론 | 자료구조, 계산 복잡도 |
| 참고 자료 | CP-Algorithms |
아호-코라식 알고리즘은 여러 패턴을 하나의 트라이와 실패 링크로 결합하여 텍스트를 한 번에 검색한다 다중 문자열 패턴 검색 분야의 대표적인 알고리즘 또는 핵심 계산 문제로, 자료 표현과 입력 조건에 맞는 계산 절차를 사용한다. 명시적인 수학적 불변식·상태 정의를 바탕으로 구현하므로 단순한 명령어 조합과는 구별된다.[1]
계산 절차는 패턴 집합으로 트라이를 만들고 BFS로 실패 링크를 구성한다. 텍스트의 각 문자를 따라 상태를 이동하면서 그 상태에 매달린 패턴과 실패 링크가 나타내는 출력들을 보고한다. 각 단계의 상태가 무엇을 의미하는지 정의하고 초기값과 경계 입력을 검사하면 결과의 정확성을 증명하거나 테스트할 수 있다.
복잡도는 트라이 구축과 실패 링크 O(총 패턴 길이×문자 집합 표현), 검색 O(텍스트 길이+발견 수) 형태 적용 전제는 패턴 집합과 문자 인코딩·중복 출력 정책을 정해야 한다 실제 연산량·메모리 사용은 구현의 자료구조와 정수·실수 표현, 전처리 및 입력 크기에 따라 달라진다.
응용과 관련 기법을 보면 악성 서명 탐지·사전 필터링·다중 키워드 검색에 사용한다. 하나의 패턴만 있다면 KMP도 적합하다. 같은 문제라도 최악 시간 보장, 메모리 요구 사항과 정밀도·확률적인 실패 가능성에 따라 적합한 알고리즘이 달라진다.[2]