←BACK TO RESUME

Profanity Filter Library

Aho-Corasick 알고리즘 기반의 O(N) 고성능 비속어 탐색 엔진 및 라이브러리

KotlinAho-CorasickTrieJitpackGradleJUnit5

1. Why this project? (Motivation)

대규모 트래픽이 발생하는 실시간 서비스에서 비속어 필터링은 단순한 기능 그 이상의 의미를 가집니다. 기존의 `String.contains` 반복 루프나 복합 정규식(`Regex`) 기반 탐지 방식은 두 가지 치명적인 한계를 가지고 있었습니다.

  • 성능의 선형 저하: 금칙어 사전의 크기가 커질수록 모든 패턴을 개별적으로 검사해야 하므로 시간 복잡도가 O(N*K)로 증가합니다.
  • 변칙 우회의 취약성: 숫자나 공백을 섞은 변칙 표현(예: "시1발")을 정규식으로 처리하려면 패턴이 기하급수적으로 복잡해져 성능이 더욱 악화됩니다.

이러한 성능 병목을 근본적으로 해결하고, 알고리즘 이론인 아호코라식(Aho-Corasick)을 실제 비즈니스 문제에 적용하여 고성능 필터링 엔진을 직접 구축하고자 본 라이브러리를 기획하게 되었습니다.

2. Architecture & Deployment

Core Architecture

Trie 자료구조를 기반으로 Failure Function을 결합한 아호코라식 알고리즘을 핵심 엔진으로 채택했습니다. 매칭 실패 시 루트로 돌아가지 않고 최장 공통 접미사 노드로 즉시 이동하여 입력 문자열을 단 한 번만 순회(O(N))하도록 설계했습니다.

Deployment Process

오픈소스 라이브러리로서의 범용성을 위해 Jitpack을 배포 저장소로 선택했습니다. GitHub 리포지토리의 태그 릴리즈를 통해 버전 관리를 수행하며, Gradle 및 Maven 환경에서 별도의 복잡한 설정 없이 의존성을 추가하여 즉시 사용 가능하도록 배포 체계를 구축했습니다.

Aho-Corasick Algorithm & Trie DiagramClick to Enlarge
Aho-Corasick Algorithm Structure

3. Problems & Technical Solutions

Problem 01: Performance Bottleneck

정규식 기반 탐지의 극심한 지연

10만 자 이상의 텍스트에서 수천 개의 금칙어를 탐지할 때, 정규식 엔진은 역추적(Backtracking)과 패턴 수만큼의 반복 검사로 인해 심각한 CPU 점유와 응답 지연을 초래했습니다.

Solution Implementation:

모든 금칙어를 Trie 자료구조로 구축하고, 매칭 실패 시 이동할 지점을 미리 계산하는 Failure Function을 연결했습니다. 이를 통해 텍스트를 단 한 번만 순회하며 수천 개의 패턴을 동시에 찾아내는 O(N) 복합 탐색을 구현하여, 기존 정규식 대비 약 27배의 성능 향상을 달성했습니다.
kotlin
// Aho-Corasick PayloadTrie를 활용한 O(N) 고속 탐색
// 금칙어 개수가 늘어나도 입력 문자열 순회 횟수는 단 1회로 고정
val detectedBans = trie.parseText(normalizedSentence)
  .map { it.payload.word }
  .distinct()
Problem 02: Obfuscation Evasion

숫자와 공백을 혼용한 우회 패턴

사용자들은 금칙어 사이에 숫자나 특수문자를 삽입하여 필터링을 교묘하게 회피합니다. 이를 패턴으로 모두 정의하는 것은 비효율적이었습니다.

Solution Implementation:

탐색 수행 전, 설정된 정책(NUMBERS, WHITESPACES)에 따라 입력 텍스트에서 숫자와 공백을 제거하는 전처리 정규화(Normalization) 파이프라인을 도입했습니다. 원본을 훼손하지 않고 내부적으로 정제된 텍스트 스트림에 대해 탐색을 수행함으로써, 변칙적으로 삽입된 방해 요소를 무력화합니다.
kotlin
// 정책 기반 정규화(Normalization) 전처리
// NUMBERS, WHITESPACES 정책에 따라 탐색 전 텍스트 정제
private fun applyPolicies(text: String, policies: Set<ProfanityFilterRegex>): String {
    val combinedRegex = policies.joinToString("|") { "(${it.regex})" }.toRegex()
    return text.replace(combinedRegex, "")
}
Problem 03: False Positives

정상 단어 내 금칙어 포함 이슈 ("시발점")

단순 문자열 제거 방식을 사용하면 의미 있는 정상 단어까지 훼손되는 문제가 발생했습니다. 비속어와 화이트리스트 간의 정교한 구분법이 필요했습니다.

Solution Implementation:

탐지된 금칙어의 인덱스 구간과 미리 정의된 허용 단어(White-list)의 구간을 비교하는 Interval Overlap 로직을 구현했습니다. 금칙어 구간이 허용 단어 구간에 완전히 포함될 경우(예: '시발' ⊂ '시발점') 이를 정상어로 판단하여 제외함으로써 필터링의 정확도를 극대화했습니다.
kotlin
// Interval Overlap 검증 로직
// 탐지된 비속어 구간이 허용 단어(WhiteList) 구간 내에 포함되면 무시
val remains = detectedBans.filterNot { ban ->
    detectedAllows.any { allow -> 
        overlaps(ban.start, ban.end, allow.start, allow.end)
    }
}

private fun overlaps(s1: Int, e1: Int, s2: Int, e2: Int) = s1 <= e2 && s2 <= e1

Performance Benchmark Results

Click to Enlarge
Regex vs Aho-Corasick Performance Comparison

Library (O(N))

3.15 ms

Complex Regex

85.89 ms

Performance Gain

27x

Time Complexity

O(N)

4. Lessons Learned

● 이론의 실제적 가치 실증

교과서적인 알고리즘(Aho-Corasick, Trie)이 실제 비즈니스 환경에서 발생하는 극심한 성능 병목을 어떻게 효율적으로 해결할 수 있는지 체득했습니다. 기술적 선택이 단순한 취향의 문제를 넘어 서비스의 품질(응답 속도, 리소스 절감)과 직결됨을 깊이 이해했습니다.

● 라이브러리 설계의 범용성 고려

단순히 기능을 구현하는 것을 넘어, 다른 개발자가 내 코드를 어떻게 사용할지 고민하며 의존성 주입(DI)과 설정 커스텀(Policy)이 용이한 API 구조를 설계하는 법을 배웠습니다. Jitpack 배포 과정을 통해 안정적인 버전 관리와 배포 파이프라인의 중요성을 경험했습니다.