Aho-Corasick에서 작은 고정 알파벳과 큰 희소 알파벳의 전이 저장 방식을 어떻게 선택하나요?

작고 고정된 알파벳이면 노드마다 배열 전이를 두는 편이 보통 단순하고 빠릅니다. 문자에서 정수 인덱스로 바로 접근할 수 있어 검색 전이가 일정한 비용을 갖지만, 노드 수를 N, 알파벳 크기를 K라 하면 전이 슬롯 메모리가 O(NK)입니다. 예를 들어 노드 10,000개와 26자 알파벳이면 슬롯만 260,000개이고, 실제 간선이 적어도 빈 칸 비용은 남습니다.

알파벳이 크고 실제 간선이 희소하면 map이나 정렬된 간선 목록이 실제 간선 수에 가까운 공간을 사용할 수 있습니다. 대신 해시 계산·포인터·할당·비교 또는 삽입 이동 비용이 들어가고 cache locality가 떨어질 수 있습니다. 따라서 노드 수만으로 선택하지 말고 실제 간선 수, 문자 분포, 구축률, 텍스트 처리 p99, 메모리 상한을 함께 측정합니다. 참조 구현은 배열의 메모리 이점이 아니라 빠른 접근과 O(mk) 계열 구축이라는 표현 전제를 제시합니다.

Unicode를 26칸 배열에 강제로 넣으면 문자가 손실되거나 잘못된 인덱스가 됩니다. UTF-8 바이트, code point, 정규화된 토큰 중 무엇을 alphabet 원소로 볼지 먼저 정하고, 사전 삽입과 텍스트 검색에서 같은 변환을 적용해야 합니다. 상황에 따라라는 말로 끝내지 말고 관측된 N·K·희소도와 메모리 예산으로 선택을 결정합니다.

숫자로 비교하면 선택 기준이 선명해집니다. 노드 10,000개, 26자 alphabet의 배열 전이는 260,000개 슬롯을 예약합니다. 실제 trie 간선이 9,999개라면 250,001개는 비어 있어도 구조상 존재합니다. 반대로 실제 간선만 map에 넣으면 슬롯 수는 9,999개에 가까워질 수 있지만, 각 항목의 포인터·hash bucket·allocator overhead를 더해야 합니다. 따라서 O 표기만으로 실제 메모리를 결론 내리지 않고 대표 사전으로 RSS와 lookup p99를 측정해야 합니다.

Unicode에서는 먼저 입력을 UTF-8 byte로 처리할지 code point로 처리할지 결정합니다. byte 기준이면 alphabet은 256개 가능성이지만 문자 경계와 사용자 표시 위치가 다르고, code point 기준이면 map 키의 크기와 정규화 비용이 달라집니다. 배열을 쓸 수 있을 만큼 실제 alphabet을 제한할 수 없다면 희소 구조를 택하고, 자주 쓰는 문자의 작은 직접 테이블과 드문 문자의 map을 혼합하는 선택도 workload를 근거로 검증해야 합니다.