Bluetape4k Text Part 3: Aho-Corasick 검색과 workshop 시나리오

키워드가 많아질수록 핵심은 단순합니다. 사전은 한 번 만들고, 입력은 한 번 훑습니다.

2026-06-29 · bluetape4k-text series · Part 3

Part 2에서는 tokenizer와 언어 감지로 입력을 나누는 방법을 봤습니다. 이번에는 그 다음 단계입니다. 입력을 어느 경로로 보낼지 정했다면, 이제 위험 키워드나 금칙어 사전을 빠르게 찾아야 합니다.

처음에는 keywords.any { text.contains(it) }로 충분합니다. 키워드가 열 개쯤이고 입력도 짧다면 굳이 복잡한 구조를 넣을 이유가 없습니다. 문제는 사전이 수백 개, 수천 개로 늘어날 때입니다. 금칙어, 브랜드명, 보안 이벤트, URL scheme, 코드 keyword가 섞이기 시작하면 contains() 반복은 금방 똥 치우기 후보가 됩니다.

text-search 모듈은 이 지점에 Aho-Corasick automaton을 둡니다. 키워드 사전으로 automaton을 한 번 만들고, 이후 입력은 한 번만 훑습니다. 매치가 있으면 위치와 keyword, 연결된 value를 돌려줍니다.

왜 contains() 반복을 바꾸나

가장 단순한 구현은 아래처럼 생깁니다.

fun hasRisk(text: String, keywords: List<String>): Boolean =
    keywords.any { keyword -> text.contains(keyword, ignoreCase = true) }

작은 서비스에서는 이 코드가 더 낫습니다. 읽기 쉽고, 실패할 곳도 적습니다. 하지만 사전이 커지면 비용 구조가 달라집니다. 키워드마다 입력을 다시 훑기 때문입니다.

방식	사전 처리	입력 처리	적합한 상황
contains() 반복	없음	키워드 수만큼 입력 반복 검사	키워드가 작고, 호출 빈도가 낮은 내부 도구
Aho-Corasick	keyword trie와 failure transition을 미리 구성	입력을 한 번 훑으며 match emit	사전이 크고, 요청마다 같은 사전을 반복 사용하는 서비스

contains() 반복은 매 요청마다 키워드 줄 세우기를 다시 하는 방식에 가깝습니다. Aho-Corasick은 사전을 먼저 기계처럼 조립해두고, 요청이 오면 텍스트만 통과시킵니다. 첫 방식은 편하지만 커질수록 비용이 누적됩니다. 두 번째 방식은 처음 만들 때 비용이 있지만, 서비스 코드에서는 반복 호출에 강합니다.

처리 흐름

text-search를 서비스 경계에 넣을 때는 아래처럼 흐름을 나누면 됩니다.

사전은 build 단계에서 automaton으로 만들고, 요청 처리에서는 입력을 한 번 훑어 결과만 사용합니다.

가장 흔한 실수는 automaton을 요청마다 다시 만드는 일입니다. build 단계에서는 keyword trie와 failure transition을 구성합니다. 요청마다 반복할 작업이 아닙니다. 서비스 시작 시점, 설정 reload 시점, 또는 사전 version이 바뀌는 시점에 만들고 재사용하는 편이 맞습니다.

AhoCorasickAutomaton은 build가 끝난 뒤 immutable이고 thread-safe입니다. 따라서 여러 요청이 같은 instance를 공유합니다. 이 경계를 지키면 service method 안에서는 parseText, containsMatch, replaceAll, matchesAsFlow 중 필요한 API만 고르면 됩니다.

builder와 DSL

Builder는 아래처럼 시작합니다.

val automaton = AhoCorasickAutomaton.builder<String>()
    .add("password reset", "ACCOUNT_TAKEOVER")
    .add("card declined", "PAYMENT_RISK")
    .options(
        SearchOptions(
            ignoreCase = true,
            allowOverlaps = false,
            wordBoundary = WordBoundary.WHITESPACE_SEPARATED,
        )
    )
    .build()

val matches = automaton.parseText(
    "user requested password reset before card declined"
)

matches.map { it.value }
// ["ACCOUNT_TAKEOVER", "PAYMENT_RISK"]

DSL을 쓰면 같은 설정을 조금 더 짧게 표현합니다.

val automaton = ahoCorasick<String> {
    ignoreCase = true
    allowOverlaps = false
    wordBoundary = WordBoundary.WHITESPACE_SEPARATED
    keyword("password reset", "ACCOUNT_TAKEOVER")
    keyword("card declined", "PAYMENT_RISK")
}

여기서 value를 문자열로만 둘 필요는 없습니다. 운영 코드에서는 enum이나 data class를 연결하는 편이 낫습니다.

enum class RiskType {
    ACCOUNT_TAKEOVER,
    PAYMENT_RISK,
}

val automaton = ahoCorasick<RiskType> {
    ignoreCase = true
    wordBoundary = WordBoundary.WHITESPACE_SEPARATED
    keyword("password reset", RiskType.ACCOUNT_TAKEOVER)
    keyword("card declined", RiskType.PAYMENT_RISK)
}

이렇게 하면 뒤쪽 코드가 문자열 비교 대신 type-safe한 분기를 사용합니다. 문자열 상수는 편하지만, 나중에 한 글자 틀리면 꽤 허무한 디버깅이 기다립니다.

금칙어 필터: workshop 예제

bluetape4k-workshop의 kotlin/text-processing 모듈에는 AbuseWordFilter가 있습니다. 이 예제는 text-search를 서비스 helper로 감쌀 때의 기본 모양을 보여줍니다.

class AbuseWordFilter(abuseWords: Collection<String>) {
    private val automaton: AhoCorasickAutomaton<String> = ahoCorasick {
        ignoreCase = true
        allowOverlaps = true
        normalization = NormalizationForm.NFC
        abuseWords.filter { it.isNotBlank() }
            .forEach { word -> keyword(word, word) }
    }

    fun containsAbuse(text: String): Boolean =
        automaton.containsMatch(text)

    fun filterText(text: String): String =
        automaton.replaceAll(text) { match ->
            "*".repeat(match.length)
        }

    fun findMatches(text: String): List<AhoCorasickMatch<String>> =
        automaton.parseText(text)
}

이 예제에서 확인할 항목은 세 가지입니다.

메서드	내부 API	서비스 의미
containsAbuse	containsMatch	존재 여부만 필요하면 첫 match에서 끝낸다
filterText	replaceAll	match span을 같은 길이의 *로 바꾼다
findMatches	parseText	위치, keyword, value까지 모두 확인한다

테스트도 이 계약을 바로 검증합니다.

val filter = AbuseWordFilter(listOf("badword", "spam", "abuse", "hate"))

filter.containsAbuse("This message contains badword!")
// true

filter.filterText("badword and spam together")
// "******* and **** together"

filter.findMatches("spam and abuse are badword").size
// 3

금칙어 필터는 “찾았다/못 찾았다”에서 끝나지 않습니다. 화면에 보여줄 텍스트를 masking할지, 신고 점수를 올릴지, moderator queue에 넣을지 정책이 뒤따릅니다. 그래서 automaton value에 category나 severity를 넣어두면 service policy와 연결하기 쉽습니다.

경계 옵션을 먼저 고른다

SearchOptions는 작지만 실수하기 쉬운 선택을 모아둡니다.

옵션	쓸 때	주의할 점
ignoreCase	대소문자 차이를 무시해야 하는 영어 keyword	keyword도 같은 pipeline으로 정규화된다
allowOverlaps	겹치는 match를 모두 볼지, 긴 keyword를 우선할지 선택	masking/치환은 겹치지 않는 결과로 처리된다
wordBoundary	부분 문자열 match를 막아야 할 때	한글/CJK에는 LATIN_ALPHA보다 WHITESPACE_SEPARATED가 낫다
normalization	자모 분리, fullwidth 문자, 호환 문자 처리	NFKC는 비용이 크므로 필요한 경로에만 쓴다
stopOnFirstMatch	blocking API에서 존재 여부가 핵심일 때	Flow에서는 take(1)로 끊는다

한글에서는 특히 word boundary를 조심해야 합니다. LATIN_ALPHA는 Character.isAlphabetic을 기준으로 보는데, 한글과 CJK도 alphabetic으로 분류됩니다. 따라서 한글 단어 경계에는 보통 WHITESPACE_SEPARATED가 더 안전합니다.

val automaton = ahoCorasick<String> {
    normalization = NormalizationForm.NFC
    wordBoundary = WordBoundary.WHITESPACE_SEPARATED
    keyword("사과", "APPLE")
    keyword("바나나", "BANANA")
}

automaton.parseText("오늘 사과 와 바나나 를 먹었다").map { it.value }
// ["APPLE", "BANANA"]

정규화도 마찬가지입니다. 입력이 자모 분리 형태로 들어오거나, ㈜ 같은 호환 문자가 섞이면 normalization이 필요한 경우가 있습니다. 하지만 정규화는 공짜가 아닙니다. 모든 경로에 NFKC를 켜기보다, 실제 입력에서 필요한지 확인한 뒤 적용하는 편이 낫습니다.

val automaton = ahoCorasick<String> {
    normalization = NormalizationForm.NFKC
    keyword("(주)", "CORP")
}

automaton.parseText("회사명: ㈜블루테이프").first().value
// "CORP"

Flow는 streaming 경계에서 쓴다

matchesAsFlow는 match를 Flow로 emit합니다. 예제에서는 로그성 입력에서 첫 번째 alert만 가져오는 모양으로 씁니다.

val automaton = ahoCorasick {
    ignoreCase = true
    keyword("critical login", "ACCOUNT_TAKEOVER")
    keyword("card declined", "PAYMENT_RISK")
}

val firstAlert = automaton.matchesAsFlow(
    "critical login failed before card declined"
).take(1).toList().firstOrNull()

firstAlert?.value
// "ACCOUNT_TAKEOVER"

여기서 stopOnFirstMatch 옵션을 기대하면 안 됩니다. Flow에서는 take(1)로 collector 쪽에서 끊는 방식이 더 명확합니다. 기본 옵션에서는 trie traversal 중 match가 나오는 대로 emit하고, take(N)이 producer를 협력 취소합니다.

다만 allowOverlaps = false이거나 wordBoundary가 들어가면 전체 결과를 한 번 post-processing해야 합니다. 이때는 Flow라도 완전히 streaming처럼 동작하지 않습니다. 이 차이를 모르면 “Flow니까 항상 한 건만 보고 바로 끝나겠지”라고 착각하기 쉽습니다. 그런 착각은 운영에서 나중에 비용으로 돌아옵니다.

benchmark는 방향만 보자

저장소에는 JMH benchmark가 있습니다. 숫자는 production 순위표가 아니라, 같은 환경에서 같은 명령으로 비교하기 위한 snapshot입니다.

실행은 아래 조건에서 수행했습니다.

./gradlew :text-search:benchmark

기준 파일은 docs/benchmark/2026-06-04-issue-97-ahocorasick-baselines.json이고, ops/s는 높을수록 빠릅니다.

항목	Ops/s	해석
parseTextNoMatch	12,209.23	5,000-keyword automaton에서 match가 없을 때
parseTextDenseMatches	3,566.90	겹치는 match가 많은 입력
parseTextLargeDictionary	3,116.99	5,000 keyword, 2,000 match token
matchesAsFlowLargeDictionaryCollect	712.62	큰 사전 결과를 Flow로 모두 수집
naiveContainsSmallDictionary	248.39	1,000 keyword를 순차 String.contains로 검사
parseTextNfkcNormalization	3.68	NFKC + ignore-case 정규화 경로

여기서 확인할 내용은 “항상 Aho-Corasick이 몇 배 빠르다”가 아닙니다. benchmark setup이 다르고, 정규화처럼 비용이 큰 경로도 섞여 있습니다. 대신 방향은 분명합니다. 키워드 사전이 커지고 같은 사전을 반복 사용한다면, 매번 contains()를 돌리는 방식보다 automaton을 재사용하는 구조가 맞습니다.

특히 parseTextNfkcNormalization 수치를 보면 정규화 비용이 큽니다. 이 결과를 보고 모든 입력에 무조건 NFKC를 켜면 안 됩니다. 필요한 입력 경로에만 적용해야 합니다. 성능 문제는 대개 이런 “편한 옵션을 전부 켠” 지점에서 시작합니다.

서비스에 넣을 때의 모양

실제 서비스에서는 아래 정도의 구조가 다루기 쉽습니다.

class RiskKeywordService(
    keywords: Collection<RiskKeyword>,
) {
    private val automaton = ahoCorasick<RiskKeyword> {
        ignoreCase = true
        allowOverlaps = true
        normalization = NormalizationForm.NFC
        keywords.forEach { keyword(it.phrase, it) }
    }

    fun inspect(text: String): RiskInspection {
        if (text.isBlank()) return RiskInspection.clean()
        if (text.length > MAX_TEXT_LENGTH) return RiskInspection.rejected()

        val matches = automaton.parseText(text)
        if (matches.isEmpty()) return RiskInspection.clean()

        return RiskInspection.flagged(
            categories = matches.mapTo(linkedSetOf()) { it.value.category },
            masked = automaton.replaceAll(text) { "*".repeat(it.length) },
        )
    }
}

사전 reload가 필요하면 새 automaton을 만든 뒤 reference를 교체하는 식으로 처리하는 편이 낫습니다. 기존 automaton을 mutable하게 고치려고 하면 요청 중간에 사전 상태가 바뀌는 문제가 생깁니다. 그런 코드는 테스트에서도 설명하기 어렵고, 운영에서는 더 어렵습니다.

입력 경계도 여기서 같이 봐야 합니다. 너무 긴 입력은 automaton에 넣기 전에 거부합니다. 원문을 에러 메시지나 로그에 그대로 남기지 않는 것도 Part 1에서 본 것과 같은 안전 경계입니다.

언제 쓰지 말까

Aho-Corasick이 항상 정답은 아닙니다.

상황	더 단순한 선택
keyword가 3~5개이고 호출 빈도가 낮다	contains() 반복
regex 문법 자체가 필요하다	정규식 또는 parser
문맥/의미 기반 분류가 필요하다	tokenizer, rule engine, ML classifier
사전이 요청마다 완전히 달라진다	automaton build 비용까지 포함해 다시 측정
입력이 너무 짧고 사전도 작다	단순 코드가 유지보수에 낫다

반대로 금칙어, 보안 이벤트, 브랜드/상품명, URL scheme, 코드 keyword처럼 사전이 반복 사용되고 match 위치가 필요한 작업이라면 text-search가 잘 맞습니다. 특히 replaceAll과 tokenize가 있으면 masking과 highlighting까지 같은 match 결과로 이어갈 수 있습니다.

Part 3의 결론은 간단합니다. 키워드가 적으면 단순한 코드가 이깁니다. 키워드가 많아지고 같은 사전을 계속 쓴다면 automaton을 만들어 재사용하세요. 그리고 옵션은 “편해 보이는 것”을 전부 켜지 말고, 입력 특성과 테스트 fixture로 고르세요.

참고한 소스

• text-search README
• AhoCorasickAutomaton
• SearchOptions
• matchesAsFlow
• AhoCorasickScenarioTest
• AhoCorasickKoreanTest
• AhoCorasickFlowTest
• AhoCorasickBenchmark
• Aho-Corasick benchmark baseline
• TextSearchExamples
• AbuseWordFilter
• AbuseWordFilterTest

시리즈

• Part 1: 텍스트 처리의 시작점과 품질 기준
• Part 2: tokenizer와 언어 감지로 입력을 라우팅하기
• Part 3: Aho-Corasick 검색과 workshop 시나리오
• Part 4: 사전과 금칙어 변경을 테스트로 다루기