아호-코라식 알고리즘
Aho–Corasick algorithm컴퓨터 과학에서 아호-코라식 알고리즘은 알프레드 5세가 발명한 문자열 탐색 알고리즘이다. 1975년 아호와 마가렛 J. 코라식.[1]입력 텍스트 내에서 한정된 문자열 집합("사전")의 요소를 위치시키는 일종의 사전 매칭 알고리즘이다.그것은 모든 줄을 동시에 일치시킨다.알고리즘의 복잡성은 문자열 길이에 검색된 텍스트 길이에 일치하는 출력 수를 더한 선형이다.모든 일치 항목이 발견되기 때문에 모든 하위 문자열이 일치하는 경우 2차적으로 일치 항목 수가 있을 수 있다는 점에 유의하십시오(예: 사전 = 사전).a, aa, aaa, aaaaa, 입력 문자열은 aaaaa).
비공식적으로, 알고리즘은 다양한 내부 노드들 사이에 추가적인 링크가 있는 트라이를 닮은 유한 상태 기계를 구성한다.이러한 추가 내부 연결은 실패한 문자열 일치(예: 고양이를 포함하지는 않지만 카트를 포함하며 ca로 접두사가 붙은 노드에서 실패하는 3개의 노드에서 고양이 검색)를 공통 접두사를 공유하는 3개의 다른 분지(예: 이전 경우 속성에 대한 분기가 가장 좋은 측면 트랜스가 될 수 있음)로 빠르게 전환할 수 있도록 허용한다.이것은 역추적할 필요 없이 문자열 매칭 간에 자동이전을 가능하게 한다.
문자열 사전(예: 컴퓨터 바이러스 데이터베이스)이 미리 알려졌을 때, 오토매틱의 구축은 오프라인으로 한 번, 컴파일된 오토매틱은 나중에 사용하기 위해 저장될 수 있다.이 경우 실행 시간은 입력 길이에 일치하는 항목 수를 더한 선형이다.
아호-코라식 문자열 매칭 알고리즘은 원래의 유닉스 명령 fgrep의 기초를 형성했다.
예
이 예에서는 {a, ab, bab, bbc, bca, c, c, caa}라는 단어로 구성된 사전을 검토하겠다.
아래 그래프는 지정된 사전에서 생성된 아호-코라식 데이터 구조로 표의 각 행은 3개의 노드를 나타내며, 열 경로는 루트부터 노드까지의 (유일한) 문자 순서를 나타낸다.
데이터 구조는 사전에 있는 모든 문자열의 접두사마다 하나의 노드를 가진다.따라서 (bca)가 사전에 있으면 (bca), (bc), (b) 및 ()에 대한 노드가 있을 것이다.만약 노드가 사전에 있다면 그것은 파란색 노드다.그렇지 않으면 회색 노드가 된다.
각 노드마다 검은색 방향의 "차일드" 호가 있는데, 이 호는 한 문자를 추가하여 이름을 찾는다.그래서 (bc)부터 (bca)까지 검은 호가 있다.
각 노드에서 그래프에서 가장 긴 엄격한 접미사인 노드로 이어지는 파란색 방향의 "suffix" 호가 있다.예를 들어, 노드(caa)의 경우, 그것의 엄격한 접미사는 (aa)와 (a)와 ()이다.그래프에 존재하는 이들 중 가장 긴 것은 (a)이다.그래서 (caa)에서 (aa)까지 푸른 호가 있다.파란색 호는 루트에서 시작하여 넓이 첫 번째 검색[잠재 접미사 노드는 항상 낮은 수준에 있음]을 수행하여 선형 시간으로 계산할 수 있다.방문한 노드의 파란색 호에 대한 대상은 부모의 파란색 호를 따라 가장 긴 접미사 노드로 이동한 후 방문한 노드의 문자와 일치하는 문자를 가진 접미사 노드의 자식을 검색하면 찾을 수 있다.어린 시절 캐릭터가 존재하지 않는 경우 다음으로 긴 접미사(파란색 호에 다시 따라)를 찾은 다음 캐릭터를 검색할 수 있다.우리는 (노드의 자식으로서) 문자를 찾거나 루트(항상 모든 문자열의 접미사가 될)에 도달할 때까지 이것을 할 수 있다.
사전의 각 노드에서 다음 노드로 이어지는 녹색 "사전 접미사" 호가 있는데, 이 호는 다음과 같은 파란색 호로 도달할 수 있다.예를 들어 (bca)에서 (a)까지의 녹색 호가 있는데, (ca)는 (ca)로 청색 호를 따랐다가 (a)로 이어졌을 때 도달하는 사전의 첫 번째 노드(즉, 청색 노드)이기 때문이다.녹색 호는 파란색 노드가 발견될 때까지 반복적으로 파란색 호를 가로지르고 이 정보를 메모해 선형적으로 계산할 수 있다.
| 경로 | 사전에서 | 접미사 링크 | 받아쓰기 접미사 링크 |
|---|---|---|---|
| () | – | ||
| (a) | + | () | |
| (a,b) | + | (b) | |
| (b) | – | () | |
| (ba) | – | (a) | (a) |
| (밥) | + | (a,b) | (a,b) |
| (BC) | + | (c) | (c) |
| (bca) | + | (ca) | (a) |
| (c) | + | () | |
| (ca) | – | (a) | (a) |
| (caa) | + | (a) | (a) |
각 단계에서 현재의 노드는 자식을 찾아 확장되며, 그것이 존재하지 않으면 접미사의 자식을 찾고, 그것이 통하지 않으면 접미사의 자식 등을 찾아내고, 그 접미사의 자식 등을 찾아내는 등의 방법으로, 마침내 이전에 아무것도 보이지 않으면 루트 노드로 끝난다.
알고리즘이 노드에 도달하면 입력 텍스트의 현재 문자 위치에 끝나는 모든 사전 항목을 출력한다.이 작업은 사전 접미사 링크를 따라 해당 노드에서 시작하여 사전 접미사 링크가 없는 노드에 도달할 때까지 계속하여 도달한 모든 노드를 인쇄함으로써 수행된다.또한 사전 항목인 경우 노드 자체가 인쇄된다.
입력 문자열 abccab에서 실행하면 다음 단계가 나온다.
| 노드 | 나머지 문자열 | 출력:끝 위치 | 전이 | 출력 |
|---|---|---|---|---|
| () | abccab | 근본부터 시작하다 | ||
| (a) | bccab | a:1 | () ~ (a) | 현재 노드 |
| (a,b) | ccab | ab:2 | (a) ~ (ab) | 현재 노드 |
| (BC) | 택시 | BC:3, c:3 | (ab) ~ 접미사(b) ~ 하위(bc) | 현재 노드, 받아쓰기 접미사 노드 |
| (c) | AB | c:4 | (bc) ~ 접미사 (c) ~ 접미사 () ~ 하위 (c) | 현재 노드 |
| (ca) | b | a:5 | (c) ~ (ca) | 받아쓰기 접미사 노드 |
| (a,b) | ab:6 | (ca) ~ 접미사(a) ~ 하위(ab) | 현재 노드 |
동적 검색 목록
원래의 아호-코라식 알고리즘은 검색 문자열 세트가 고정된 것으로 가정한다.알고리즘 적용 중 새로운 검색 문자열이 추가되는 애플리케이션에는 직접 적용하지 않는다.사용자가 본문을 통해 새로운 단어나 구문을 강조하여 보는 대로 색인화하는 대화형 색인 프로그램이 그 예다.베르트랑 마이어는 검색 도중 검색 문자열 세트를 점진적으로 확장할 수 있는 알고리즘의 증분 버전을 도입해 원본의 알고리즘 복잡성을 유지했다.[2]
참고 항목
참조
- ^ Aho, Alfred V.; Corasick, Margaret J. (June 1975). "Efficient string matching: An aid to bibliographic search". Communications of the ACM. 18 (6): 333–340. doi:10.1145/360825.360855. MR 0371172. S2CID 207735784.
- ^ Meyer, Bertrand (1985). "Incremental string matching" (PDF). Information Processing Letters. 21 (5): 219–227. doi:10.1016/0020-0190(85)90088-2.
외부 링크
 | 위키미디어 커먼즈에는 아호-코라식 알고리즘과 관련된 미디어가 있다. |
- NIST 알고리즘 및 데이터 구조 사전의 Aho-Corasick (2019-07-15)
- 아호-코라식 시각화
- GitHub에 대한 Aho-Corasick 구현(C++)
- GitHub에서 Aho-Corasick 문자열 매칭 알고리즘의 골랑 구현
- GitHub에서 Rust in Aho-Corasick의 신속한 구현
