Sliding Window에서 Trie로: 금칙어 필터링 성능 개선기
들어가며
금칙어 필터링 시스템을 개발하면서 성능 문제에 직면했습니다. 초기에는 Sliding Window 방식으로 후보 단어를 추출하고 Redis에서 매칭을 확인했는데, 네트워크 I/O가 많아 응답 시간이 느려졌습니다. 이를 해결하기 위해 Trie 데이터 구조를 도입하여 성능을 크게 개선했습니다.
기존 방식: Sliding Window + Redis 조회
구현 방식
기존에는 다음과 같은 방식으로 금칙어를 감지했습니다:
- 후보 단어 추출: 텍스트를 토큰화한 후, 각 토큰에 대해 Sliding Window를 적용하여 모든 가능한 부분 문자열을 추출
- Redis 조회: 추출된 각 후보 단어를 Redis에서 조회하여 금칙어인지 확인
// TokenizationService.extractCandidates()
extractCandidates(text: string): string[] {
const candidates = new Set<string>();
const tokens = this.tokenize(text); // 공백 기준 토큰화
// 각 토큰에 대해 Sliding Window 적용
const extractSlidingWindow = (token: string): void => {
for (let start = 0; start < token.length; start++) {
for (let end = start + 1; end <= token.length; end++) {
const candidate = token.substring(start, end);
candidates.add(candidate);
}
}
};
for (const token of tokens) {
extractSlidingWindow(token);
}
return Array.from(candidates);
}문제점
- 네트워크 I/O 과다: 후보 단어가 많을수록 Redis 조회 횟수가 증가
- 예: "안녕하세요" → 15개의 후보 단어 생성 → 15번의 Redis 조회
- 시간 복잡도: O(n²) 후보 생성 + O(m) Redis 조회 (n: 텍스트 길이, m: 후보 개수)
- 응답 시간: 평균 50-100ms (네트워크 지연 포함)
새로운 방식: Trie 기반 매칭
Trie란?
Trie는 문자열 검색에 최적화된 트리 자료구조입니다. 각 노드는 문자를 나타내고, 루트부터 리프까지의 경로가 하나의 단어를 나타냅니다.
(root)
/ | \
시 개 안
/ \ \
발 새 녕
\
끼구현 방식
1. Trie 구조 정의
interface TrieNode {
children: Map<string, TrieNode>;
isEndOfWord: boolean;
wordInfo?: {
word: string;
normalizedWord: string;
id: string;
severity: string;
};
}2. 금칙어 추가
addWord(normalizedWord: string, wordInfo: WordInfo): void {
let node = this.globalTrie;
for (const char of normalizedWord) {
if (!node.children.has(char)) {
node.children.set(char, this.createNode());
}
node = node.children.get(char)!;
}
node.isEndOfWord = true;
node.wordInfo = wordInfo;
}3. 텍스트에서 모든 매칭 찾기
핵심은 텍스트를 한 번만 순회하여 모든 매칭을 찾는 것입니다:
findAllMatches(text: string): Match[] {
const matches: Match[] = [];
// 텍스트의 각 위치에서 시작
for (let i = 0; i < text.length; i++) {
let node = this.globalTrie;
// 현재 위치부터 Trie 탐색
for (let j = i; j < text.length; j++) {
const char = text[j];
const child = node.children.get(char);
if (!child) {
break; // 더 이상 매칭 불가
}
node = child;
// 단어 끝에 도달하면 매칭 추가
if (node.isEndOfWord && node.wordInfo) {
matches.push({
word: node.wordInfo.word,
normalizedWord: node.wordInfo.normalizedWord,
severity: node.wordInfo.severity,
startIndex: i,
endIndex: j + 1,
});
}
}
}
return this.deduplicateMatches(matches);
}개선 효과
- 네트워크 I/O 제로: 메모리 기반 Trie로 직접 접근
- 시간 복잡도: O(n) (n: 텍스트 길이)
- 응답 시간: 평균 < 10ms (Fast Path)
- 위치 정보 포함: 전체/부분 매칭 구분 가능
성능 비교
| 방식 | 시간 복잡도 | 네트워크 I/O | 평균 응답 시간 |
|---|---|---|---|
| Sliding Window + Redis | O(n²) + O(m) | m회 (후보 개수) | 50-100ms |
| Trie | O(n) | 0회 | < 10ms |
전체/부분 매칭 구분
Trie는 매칭된 단어의 위치 정보(startIndex, endIndex)를 제공하므로, 전체 단어 매칭과 부분 매칭을 구분할 수 있습니다:
// "시발점"에서 "시발"이 부분 매칭으로 감지됨
// 하지만 토큰 경계와 일치하지 않으므로 부분 매칭으로 분류
private isFullWordMatch(
startIndex: number,
endIndex: number,
tokenPositions: TokenPosition[]
): boolean {
for (const tokenPos of tokenPositions) {
if (
startIndex === tokenPos.startIndex &&
endIndex === tokenPos.endIndex
) {
return true; // 전체 단어 매칭
}
}
return false; // 부분 매칭
}이를 통해 "시발점" 같은 정상 단어에서 False Positive를 줄일 수 있습니다.
실제 적용 예시
기존 방식 (Sliding Window)
// 1. 후보 추출
const candidates = extractCandidates("안녕하세요 시발");
// → ["안", "안녕", "안녕하", ..., "시", "시발", ...] (15+ 개)
// 2. 각 후보를 Redis에서 조회
for (const candidate of candidates) {
const exists = await redis.sismember("badWords", candidate);
if (exists) {
matches.push(candidate);
}
}
// → 15+ 번의 네트워크 I/O새로운 방식 (Trie)
// 1. 한 번의 순회로 모든 매칭 발견
const matches = trieService.findAllMatches("안녕하세요 시발");
// → [{ word: "시발", startIndex: 6, endIndex: 8, ... }]
// → 네트워크 I/O 0회, 메모리 직접 접근마무리
Sliding Window 방식에서 Trie 방식으로 전환하면서:
- 성능: 50-100ms → < 10ms (5-10배 개선)
- 네트워크 I/O: m회 → 0회
- 위치 정보: 전체/부분 매칭 구분 가능
- 확장성: 금칙어가 늘어나도 성능 저하 없음
Trie는 문자열 검색에 최적화된 자료구조로, 금칙어 필터링뿐만 아니라 자동완성, 맞춤법 검사 등 다양한 문자열 검색 문제에 활용할 수 있습니다.
Backend Developer