JAVA/Java 일반
금칙어 처리(with Aho corasick 알고리즘)
달사자!
2020. 11. 12. 23:43
2026-06 간단히 내용 몇 가지 업데이트
- 원래 작성했던 글은 메모 및 간단히 동료에게 공유해줄 목적이어서 실제 구현대비 누락된 내용이 많았습니다.
- 시간될때마다 내용 업데이트를 해보겠습니다.(but, 요즘에는 AI가 워낙 좋아서 요구사항을 잘 프롬프트하면 더 좋은 결과가 나와서 효용성이 없을지도..)
1. 정규표현식(Regex)의 성능 한계
정규표현식은 유연하지만 텍스트를 검사할 때 백트래킹(Backtracking) 이라는 연산 과정을 거치기 때문에 기본적으로 무거운 작업입니다.
- 검사 방식: 금칙어가 1,000개라면, 사용자가 글을 하나 쓸 때마다 1,000개의 정규식 패턴을 순회하며 매칭을 시도해야 합니다.
- 시간 복잡도: 대략 O(N * M) (N: 입력 텍스트 길이, M: 금칙어 개수)
- 문제점: 금칙어 사전(Dictionary)의 크기가 커질수록 성능이 선형적으로 하락합니다. 악의적인 사용자가 매우 긴 텍스트를 입력하면 CPU 사용량이 급증하는 병목 지점이 될 수 있습니다.
2. 텍스트 정규화 + Aho-Corasick의 압도적 성능
Aho-Corasick 알고리즘은 애초에 '다중 문자열 검색'을 위해 탄생한 알고리즘입니다.
- 검사 방식: 금칙어 1,000개를 하나의 거대한 트리(Trie) 구조와 실패 링크(Failure Link)를 가진 오토마타로 미리 만들어 둡니다. 사용자의 텍스트를 단 한 번만 쭉 읽으면서(1 Pass) 1,000개의 금칙어 포함 여부를 동시에 찾아냅니다.
- 시간 복잡도: O(N + P) (N: 텍스트 길이, P: 찾은 금칙어 개수)
- 장점: 금칙어가 10개든 10만 개든 검색 속도가 거의 똑같습니다. 정규화(특수문자 제거) 과정 역시 O(N)으로 매우 빠르기 때문에 전체적인 성능이 정규식과 비교할 수 없을 정도로 뛰어납니다.
💡 실무 적용 꿀팁: "성능도 챙기고 마스킹(***)도 하고 싶다면?"
정규화는 인덱스가 틀어져서 마스킹(*** 치환)이 까다로운데, 실무에서는 성능을 위해 Aho-Corasick을 쓰면서도, 이 문제를 '인덱스 매핑(Index Mapping)' 기법으로 해결합니다.
- 매핑 배열 생성: 원본 텍스트를 정규화하면서, 정규화된 글자가 원본 텍스트의 몇 번째 인덱스인지 기록해 둡니다.
- 원본: 욕 1설 (인덱스: 0 1 2 3)
- 정규화: 욕설
- 매핑 배열: [0, 3] ('욕'은 원본의 0번, '설'은 원본의 3번)
- Aho-Corasick 검색: 정규화된 욕설을 검사해서 금칙어를 찾습니다.
- 원본 치환: 찾아낸 금칙어의 시작/끝 글자를 매핑 배열에서 조회한 뒤, 원본 텍스트의 0번부터 3번 인덱스까지를 ***로 치환합니다.
최종 권장: 성능이 중요한 서비스(트래픽이 많거나 텍스트 길이가 긴 게시판, 실시간 채팅 등)라면 무조건 텍스트 정규화 + Aho-Corasick (필요시 인덱스 매핑 추가) 조합으로 개발하시는 것을 강력히 추천합니다!
CREATE TABLE `banned_word` (
`id` BIGINT NOT NULL AUTO_INCREMENT COMMENT '고유 식별자 (PK)',
`word` VARCHAR(100) NOT NULL COMMENT '금칙어 (다국어 및 이모지 지원)',
`category` VARCHAR(50) DEFAULT 'GENERAL' COMMENT '금칙어 유형 (예: 욕설, 도박, 혐오, 광고 등)',
`is_active` TINYINT(1) NOT NULL DEFAULT 1 COMMENT '적용 여부 (1: 활성, 0: 비활성)',
`created_by` VARCHAR(50) DEFAULT NULL COMMENT '등록자 ID 또는 이름',
`created_at` DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '등록 일시',
`updated_at` DATETIME NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '수정 일시',
PRIMARY KEY (`id`),
UNIQUE KEY `uk_banned_word_word` (`word`),
KEY `idx_banned_word_is_active` (`is_active`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci COMMENT='금칙어 관리 테이블';
테이블 설계 포인트
- CHARSET=utf8mb4 & COLLATE=utf8mb4_0900_ai_ci: 다국어와 이모지 지원을 위한 핵심 설정이야. 대소문자 구분 없이(Case-Insensitive), 악센트 구분 없이(Accent-Insensitive) 유연하게 텍스트를 처리해 줘.
- UNIQUE KEY (word): 똑같은 금칙어가 중복으로 등록되는 것을 데이터베이스 단에서 원천 차단해. Aho-Corasick 트리를 메모리에 올릴 때 중복 데이터가 있으면 낭비니까 미리 막는 게 좋아.
- is_active: 금칙어를 당장 삭제하지 않고 '잠시 사용 안 함' 처리할 때 유용해. Spring Boot 서버가 뜰 때(또는 주기적으로 캐시를 갱신할 때) SELECT word FROM banned_word WHERE is_active = 1 쿼리로 활성화된 단어만 가져와서 Aho-Corasick 오토마타를 구성하면 돼.
- idx_banned_word_is_active 인덱스: 앞서 말한 대로 서버가 구동되거나 금칙어 트리를 메모리에서 리로드할 때, 활성화된 금칙어만 빠르게 조회하기 위해 인덱스를 걸어두었어.
💻 Aho-Corasick 금칙어 필터링 구현체 (Java 21)
import java.util.*;
public class BannedWordFilter {
// 1. Trie 노드 정의 (내부 클래스)
private static class Node {
// 자식 노드들 (검색 속도를 위해 HashMap 사용)
final Map<Character, Node> children = new HashMap<>();
// 매칭 실패 시 돌아갈 링크 (성능의 핵심!)
Node fail;
// 이 노드에서 끝나는 금칙어가 있는지 여부
boolean isOutput;
}
private final Node root = new Node();
/**
* 금칙어 목록을 받아 Aho-Corasick 오토마타를 구성합니다.
* (이 작업은 무거우므로 Spring Boot 실행 시 한 번만 수행하여 캐싱하는 것을 권장)
*/
public void buildAutomaton(List<String> bannedWords) {
// [Step 1] Trie 구조 만들기
for (String word : bannedWords) {
Node current = root;
for (char c : word.toCharArray()) {
current.children.computeIfAbsent(c, k -> new Node());
}
current.isOutput = true;
}
// [Step 2] 실패 링크(Failure Link) 구성 (BFS 방식)
Queue<Node> queue = new ArrayDeque<>();
for (Node child : root.children.values()) {
child.fail = root;
queue.offer(child);
}
while (!queue.isEmpty()) {
Node current = queue.poll();
for (Map.Entry<Character, Node> entry : current.children.entrySet()) {
char c = entry.getKey();
Node child = entry.getValue();
// 실패 링크 찾기
Node failNode = current.fail;
while (failNode != null && !failNode.children.containsKey(c)) {
failNode = failNode.fail;
}
if (failNode == null) {
child.fail = root;
} else {
child.fail = failNode.children.get(c);
}
// 부모나 실패 링크에 금칙어가 포함되어 있다면, 자식 노드도 금칙어 포함으로 간주
child.isOutput |= child.fail.isOutput;
queue.offer(child);
}
}
}
/**
* 사용자가 입력한 텍스트에 금칙어가 포함되어 있는지 검사합니다.
*/
public boolean containsBannedWord(String text) {
if (text == null || text.isBlank()) {
return false;
}
// [핵심] 특수문자, 숫자, 공백 제거 (욕1설, 욕!설 -> 욕설)
String normalizedText = text.replaceAll("[^가-힣a-zA-Z]", "");
Node current = root;
for (char c : normalizedText.toCharArray()) {
// 현재 문자가 자식 노드에 없으면 실패 링크를 따라감 (백트래킹 방지)
while (current != null && !current.children.containsKey(c)) {
current = current.fail;
}
if (current == null) {
current = root; // 루트까지 와도 없으면 다시 처음부터
continue;
}
current = current.children.get(c);
// 금칙어를 발견한 경우 즉시 true 반환
if (current.isOutput) {
return true;
}
}
return false;
}
// --- 테스트용 메인 메서드 ---
public static void main(String[] args) {
BannedWordFilter filter = new BannedWordFilter();
// 1. 금칙어 트리 구성 (서버 시작 시 1회 실행)
List<String> bannedWords = List.of("욕설", "도박", "광고");
filter.buildAutomaton(bannedWords);
// 2. 텍스트 검사
String input1 = "이런 욕1설, 진짜 나쁜 놈이네";
String input2 = "도!!!박 사이트 오세요";
String input3 = "안녕하세요 반갑습니다";
System.out.println("input1 검사 결과: " + filter.containsBannedWord(input1)); // true
System.out.println("input2 검사 결과: " + filter.containsBannedWord(input2)); // true
System.out.println("input3 검사 결과: " + filter.containsBannedWord(input3)); // false
}
}
💡 핵심 자료구조 설명 및 성능 포인트
- Trie (접두사 트리):
- 여러 개의 단어를 공통된 앞글자(접두사) 기준으로 합쳐서 트리를 만들어.
- "도박", "도둑" 이라는 두 개의 금칙어가 있다면, '도'라는 하나의 노드 아래에 '박', '둑'이 갈라져 나오게 돼. 메모리도 절약되고 앞글자가 다르면 일찍 검색을 포기할 수 있어 속도가 빨라져.
- Failure Link (실패 링크):
- 검색을 하다가 중간에 매칭이 끊겼을 때, "처음부터 다시 검사하는 대신, 어디로 돌아가면 가장 효율적인가?" 를 미리 계산해 둔 포인터야.
- 이 덕분에 텍스트의 처음부터 끝까지 단 한 번만(O(N) 시간 복잡도) 훑고 지나가면 금칙어 포함 여부를 100% 잡아낼 수 있어.
- Spring Boot 연동 시 주의사항:
- buildAutomaton 메서드는 DB에 있는 모든 금칙어를 가져와서 트리를 만드는 무거운 작업이야.
- 따라서 @Service 클래스 내에서 @PostConstruct를 활용해 스프링 빈(Bean) 초기화 시점에 딱 한 번만 실행되도록 구성하고, 금칙어 추가/삭제 시에만 트리를 재구성(Re-build)하도록 캐싱 전략을 짜는 것을 권장해.
서비스를 개발하다보면 항상 금칙어처리가 필요하게 됩니다.
금칙어 갯수가 적으면 상관 없는데 갯수가 많으면(특히 중국 서비스하면..;) 성능을 잘 생각해서 처리해야 합니다.
관련해서 참고용 TC를 만들어봤습니다.
간단히 만들어서 TC종류는 많지 않고 부족한 부분이 있을 수 있습니다.
1. 금칙어 저장테이블 DDL(참고용)
-- 금칙어 테이블 DDL샘플(Mysql). 글로벌 다국어를 감안하여 금칙어 컬럼은 'utf8mb4_bin'로 정의
CREATE TABLE `bad_word` (
`pk` INT(10) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 'pk',
`use_yn` ENUM('Y','N') COLLATE utf8mb4_unicode_ci NOT NULL DEFAULT 'Y' COMMENT '사용여부',
`bad_word` VARCHAR(50) CHARACTER SET utf8mb4 COLLATE utf8mb4_bin NOT NULL COMMENT '금칙어',
PRIMARY KEY (`pk`),
UNIQUE KEY `UNQ_badWord` (`bad_word`)
) ENGINE=INNODB DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_unicode_ci COMMENT='금칙어'
2. maven dependency
<!-- https://mvnrepository.com/artifact/org.ahocorasick/ahocorasick -->
<dependency>
<groupId>org.ahocorasick</groupId>
<artifactId>ahocorasick</artifactId>
<version>0.4.0</version>
</dependency>3. test case
import org.ahocorasick.trie.Emit;
import org.ahocorasick.trie.Trie;
import org.apache.commons.lang3.RandomStringUtils;
import org.junit.Assert;
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.Timeout;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.concurrent.TimeUnit;
/**
* 금칙어 성능 테스트
* - 대량(10만개 이상)의 금칙어 키워드 존재시 금칙어 여부 판단에 성능 이슈가 없도록 처리하는 테스트(샘플) 소스
* - 아호코라식 알고리즘을 활용: https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm
*
* @author
*/
class BadWordPerformanceTest {
private static int initDummyBadwordCnt = 100_000; //더미용 금칙어 초기화 갯수
private static final String findBadword = "개새끼"; //테스트용 금칙어
private static final String findBadword2 = "소새끼"; //테스트용 금칙어2
private static LinkedHashSet<String> badwords = new LinkedHashSet<>(); //linkedhaset이 contain 성능이 가장 좋음: https://dzone.com/articles/java-collection-performance
private static Trie badwordsTrie; //아호코라식용
@BeforeAll
static void init() {
for (int i = 1; i <= initDummyBadwordCnt; i++) {
//String randomBadWord = RandomStringUtils.random(30, false, false);
String randomBadWord = RandomStringUtils.randomAlphanumeric(30);
badwords.add(randomBadWord);
}
System.out.println(String.format("init 금칙어 갯수(컬렉션용): %d", badwords.size()));
//아호코라식용 초기화
long startInitAho = System.currentTimeMillis();
badwordsTrie = Trie.builder().addKeywords(badwords).addKeyword(findBadword).addKeyword(findBadword2).build(); //시간이 많이걸리니까 가능하면 초기화 후 재 사용
//badwordsTrie = Trie.builder().addKeywords(badwords).addKeyword(findBadword).addKeyword(findBadword2).onlyWholeWords().build(); //시간이 많이걸리니까 가능하면 초기화 후 재 사용
//badwordsTrie = Trie.builder().ignoreCase().ignoreOverlaps().addKeywords(badwords).build(); //아호코라식용 초기화
long endInitAho = System.currentTimeMillis();
System.out.println("아호코라식 초기화 소요시간(ms): " + (endInitAho - startInitAho));
}
/**
* 아호코라식으로도 완전일치 테스트가 가능하지만 java컬렉션을 이용해서도 구현
*/
@Test
@Timeout(value = 20, unit = TimeUnit.MILLISECONDS)
public void 금칙어_완전일치_테스트() {
badwords.add(findBadword); //테스트용 금칙어를 금칙어 셋에 추가해둠(성능 테스트를 위해 만든 대량의 금칙어에 추가)
final String notExistBadword = findBadword + System.currentTimeMillis(); //확률적으로 존재할 수 없는 금칙어
long startExactNano = System.nanoTime();
long startExactms = System.currentTimeMillis();
Assert.assertTrue(badwords.contains(findBadword));
Assert.assertFalse(badwords.contains(notExistBadword));
long endExactNano = System.nanoTime();
long endExactMs = System.currentTimeMillis();
System.out.println("\n\n완전일치 금칙어 find 소요시간(nano): " + (endExactNano - startExactNano));
System.out.println("완전일치 금칙어 find 소요시간(ms): " + (endExactMs - startExactms));
}
/**
* 성능을 위해서 포함여부 체크는 아호코라식 알고리즘을 사용
* - 구현 java 라이브러리: https://github.com/robert-bor/aho-corasick (maven mvnrepository에는 배포를 안하니 참고해서 직접 구현하거나 소스 내려받아서 빌드 후 사용)
*/
@Test
@Timeout(value = 20, unit = TimeUnit.MILLISECONDS)
public void 금칙어_포함여부_아호코라식알고리즘기반_테스트() {
String targetText_1 = "개새끼들이 뛰어놀고 있어요. 소 는 없어요";
Collection<Emit> emits_1 = excuteAho(targetText_1);
Assert.assertTrue(emits_1.size() == 1);
String targetText_2 = "개새끼들이 뛰어놀고 있어요. 옆에는 소새끼들이 있어요";
Collection<Emit> emits_2 = excuteAho(targetText_2);
Assert.assertTrue(emits_2.size() == 2);
String targetText_3 = "개가 뛰어놀고 있어요. 옆에는 소도 있어요";
Collection<Emit> emits_3 = excuteAho(targetText_3);
System.out.println(emits_3);
Assert.assertTrue(emits_3.size() == 0);
}
private Collection<Emit> excuteAho(String targetText) {
System.out.println("\n===== excuteAho: Start ");
System.out.println("금칙어가 존재하는지 검사할 텍스트:==>" + targetText);
long startNano = System.nanoTime();
long startMs = System.currentTimeMillis();
Collection<Emit> emits = badwordsTrie.parseText(targetText);
System.out.println("검출된 금칙어 갯수: " + emits.size());
for (Emit emit : emits) {
System.out.println(String.format(" 금칙어 '%s'에 매칭됨", emit.getKeyword()));
}
long endNano = System.nanoTime();
long endMs = System.currentTimeMillis();
long duNano = endNano - startNano;
long duMs = endMs - startMs;
System.out.println(String.format("아호코라식 기반 금칙어 판별 소요시간. '%d(nano)' | '%d(ms)'", duNano, duMs));
System.out.println("===== excuteAho: End ");
return emits;
}
}