운영 중 금지어를 추가했는데 기존 Aho-Corasick 자동자의 failure 링크를 그대로 써도 되나요?

일반적인 정적 Aho-Corasick 전제에서는 그대로 쓰면 안 됩니다. failure link는 각 trie 상태 문자열의 suffix 중 사전에 존재하는 가장 긴 상태를 가리키고, output/exit link는 terminal 상태의 연결을 나타냅니다. 새 금지어를 삽입하면 새 노드뿐 아니라 기존 여러 상태의 가장 긴 suffix 후보와 출력 chain이 바뀔 수 있습니다. 따라서 일부 링크만 국소 수정하면 어떤 상태는 새 금지어를 보고 다른 상태는 놓칠 수 있습니다.

운영 설계에서는 새 사전으로 trie와 링크를 완성한 뒤 세대(generation) 단위로 자동자를 교체하는 방식이 안전합니다. 읽는 작업은 old generation을 불변으로 사용하고, 새 구축이 끝난 시점에 포인터를 원자적으로 교체합니다. 교체 도중 링크 배열을 직접 수정하면 검색 스레드가 서로 다른 세대의 상태와 링크를 섞어 읽을 수 있습니다.

이때 요청이 시작된 세대의 규칙을 끝까지 적용할지, 처리 시점의 최신 세대를 적용할지는 별도 계약입니다. 같은 텍스트가 교체 전후에 다른 결과를 내는 것은 자연스러울 수 있지만, 한 요청 내부에서 세대가 섞이면 안 됩니다. 빈 금지어와 삭제, 구축 실패 시 old generation 유지 정책도 함께 정해야 합니다.

새 패턴이 기존 terminal의 suffix 관계를 바꾸는 구체적 이유는 링크가 “새로 추가된 노드의 부모”가 아니라 전체 사전에서 가장 긴 suffix를 찾기 때문입니다. 예를 들어 기존 사전에 he만 있고 상태 she를 새로 추가하면 she의 failure가 he를 가리켜야 하고, she 상태를 suffix로 갖는 다른 상태의 output chain도 달라질 수 있습니다. 국소 삽입 뒤 일부 링크만 고치면 영향을 받는 상태 집합을 놓치기 쉽습니다.

세대 교체에서는 새 자동자의 구축 완료와 공개를 분리합니다. 구축 중에는 요청이 old를 읽고, 모든 next·failure·output 링크와 패턴 ID가 검증된 뒤에만 새 root를 공개합니다. old를 읽던 요청이 끝난 뒤 메모리를 회수해야 하므로 참조 카운트나 epoch 기반 회수 같은 런타임 정책도 필요합니다. 이 부분은 Aho-Corasick 알고리즘 자체가 정하지 않는 운영 조건입니다.