Aho-Corasick 알고리즘 — 접두사 트리로 여러 문자열을 동시에 찾기

AI 요약

Aho-Corasick은 입력 문자열 하나를 훑으며 여러 패턴을 동시에 찾는 알고리즘입니다. 글은 기존 Trie(접두사 트리)에 두 종류의 링크를 더한 뒤, 각 입력 문자에 대한 전이를 미리 계산해 자동자(automaton)를 완성하는 과정을 설명합니다.

Trie와 접미사 링크

Trie에서는 패턴의 공통 접두사를 노드와 간선으로 공유합니다. 예를 들어 suit, suited, suitable을 저장하면 세 문자열이 공유하는 suit 경로를 한 번만 둡니다. 패턴의 끝을 나타내는 노드에는 매칭 결과를 표시합니다.

입력이 현재 노드에서 더 진행되지 않으면 접미사 링크(suffix link)를 따라갑니다. 각 링크는 해당 노드가 나타내는 문자열에서, Trie의 다른 패턴 접두사와 일치하는 가장 긴 접미사를 가리킵니다. suit 노드에서 다음 문자 e를 읽었는데 간선이 없더라도, suit의 접미사 it가 다른 패턴의 접두사라면 그 상태로 이동해 매칭을 이어갑니다. 글의 예에서는 item을 찾을 수 있습니다.

접미사 링크는 Trie를 너비 우선 탐색(BFS)하며 계산합니다. 루트와 루트의 자식은 접미사 링크가 루트를 가리킵니다. 그보다 깊은 노드는 부모의 접미사 링크에서 시작해 현재 간선의 문자와 같은 간선을 찾습니다. 찾으면 그 간선의 도착 노드가 새 접미사 링크가 됩니다. 찾지 못하면 접미사 링크를 거슬러 올라가며 탐색하고, 루트에서도 찾지 못하면 루트를 가리킵니다. 예를 들어 facade의 faca 상태에서 ca를 보존할 수 있다면, ca가 접두사인 cadence의 Trie 상태로 이어집니다.

출력 링크

한 패턴의 끝에 도달했을 때, 그 상태에 해당하는 패턴만 출력하면 충분하지 않을 수 있습니다. 현재 문자열의 접미사도 다른 패턴과 일치할 수 있기 때문입니다. spin, pin, in을 저장한 Trie에서는 spin을 찾은 상태에서 pin과 in도 함께 출력해야 합니다.

출력 링크(output link)는 접미사 링크가 가리키는 노드에 패턴이 있으면 그 노드를 가리킵니다. 패턴이 없다면 해당 노드의 출력 링크를 이어받습니다. 접미사 링크를 먼저 계산하므로, BFS 과정에서 각 노드의 출력 링크도 이어서 정할 수 있습니다. 매칭 시에는 출력 링크를 따라가며 함께 보고해야 하는 패턴을 찾습니다.

전이를 미리 계산해 자동자 완성

접미사 링크를 그대로 사용하는 방식은 입력 문자마다 링크를 여러 번 따라갈 수 있습니다. 글은 링크 계산 뒤 Trie를 다시 BFS로 순회하며 각 상태의 문자별 전이를 미리 결정합니다. 루트에서 간선이 없는 문자는 루트에 머물게 합니다. 다른 상태에서 간선이 없으면 접미사 링크가 가리키는 상태의 해당 문자 전이를 사용합니다. 이렇게 하면 실패 후에도 가장 긴 유효 접미사 접두사를 보존하는 결정적 유한 오토마톤(DFA)이 만들어집니다. 패턴에 쓰이지 않는 문자는 루트로 향하는 경우가 많으므로, 글은 오프라인 자동자에서 희소 행렬 저장을 권합니다.

Lobsters 반응

• @novedevo — 이 알고리즘을 좋아합니다. 최적화된 Rust 구현이 있으며, 지연 DFA가 덜 빠른 일부 상황에서 사실상 표준인 regex 크레이트도 사용합니다.
  • @fazalmajid — 방화벽이나 백신 같은 보안 장비처럼 패턴이 아주 많다면, Intel의 고도로 최적화된 HyperScan 라이브러리에 기반하면서 ARM64 NEON 지원을 추가한 hyperscan-tokio-sys의 VectorScan을 쓰는 편이 낫습니다.
  • @novedevo — VectorScan을 알려주셔서 감사합니다. 다만 보안이 중요한 환경에서는 버전이 하나뿐이고, 작년에 처음 공개된 뒤 활동이 없으며, GitHub 저장소도 삭제된 크레이트라 우려됩니다. 벤치마크도 재현하지 못했습니다. 제가 얻은 결과는 regex보다 6~7배 빨랐고, 그것도 좋은 수치이긴 합니다. 대신 vectorscan-rs를 쓰는 편이 나을 수 있습니다. 제 벤치마크에서는 성능이 같거나 조금 더 좋았고, 유지 관리도 되고 있으며 작성자도 신뢰할 만해 보입니다.
• @ThomasAdam — 몇 년 전 웹 콘텐츠 필터를 개발하는 회사에서 일했습니다. 단어를 검사해 가중치를 매기는 데 이 알고리즘을 주요하게 사용했습니다.
• @thangalin — 제 Markdown 편집기 KeenWrite가 R 표현식 수백 개를 실시간으로 평가하는 이유 중 하나가 Aho-Corasick 알고리즘입니다. Robert Bor가 Java용으로 훌륭한 구현을 만들었습니다. https://github.com/robert-bor/aho-corasick https://repo.autonoma.ca/repo/keenwrite/blob/HEAD/src/main/java/com/keenwrite/processors/text/AhoCorasickReplacer.java
• @ruuda — 몇 년 전 Haskell로 이 알고리즘을 구현했습니다. 당시 UTF-16에서는 Haskell 구현이 Rust보다 빨랐습니다.

원문: compiler.club / 번역·요약: Trawling