[JavaScript] 욕설(비속어) 필터링 기능 개선 (Aho-Corasick 알고리즘)
욕설(비속어) 필터링 기능 개선 (Aho-Corasick 알고리즘)
사이드 프로젝트를 만들었는데 뭔가 허전함을 느꼈다
문득 생각난게 게임처럼 비속어 필터링 기능을 넣으면 어떨까? 라는 생각이 문득 들었다.
import { badWords } from "@/constants/badwords"; // 욕설 모음 zip...
export default function badWordsFilter(text: string) {
let filteredText = text;
badWords.forEach((badWord) => {
let index = filteredText.toLowerCase().indexOf(badWord.toLowerCase());
while (index !== -1) {
// 비속어 *** 치환
filteredText =
filteredText.substring(0, index) +
"***" +
filteredText.substring(index + badWord.length);
// 그 다음 비속어 검색
index = filteredText
.toLowerCase()
.indexOf(badWord.toLowerCase(), index + 3);
}
});
return filteredText;
}
export const containsBadWords = (value: string) => {
return badWords.some((badWord) => value.toLowerCase().includes(badWord));
};
기존코드는 비속어를 *** 로 변경하는 단순 반복 검색하는 간단한 코드인데 badWords 비속어 배열이 많아질수록, 텍스트 길이가 길어질수록 비효율적으로 보인다. (시간 복잡도도 O(k*n*m)으로 보인다. - k:금칙어 개수, n:텍스트 길이, m:각 금칙어의 출현 횟수)
요즘 코딩테스트 공부를 하면서 알고리즘에 따라 시간복잡도를 많이 개선할 수 있는것을 보고 비속어 필터링 기능을 어떻게 다른 사람들은 구현했는지 찾아봤다.
AI를 사용해도되고 비속어 필터링 라이브러리도 있지만 관심을 끌만한 내용은 Aho-Corasick 알고리즘을 사용해서 구현하는 방법이 관심을 끌었다.
이외에도 일대일 문자열 패턴 매칭 알고리즘에 KMP 알고리즘이 있는데 KMP(Knuth-Morris-Pratt) 알고리즘은 한가지의 패턴을 찾는 알고리즘이라 시간복잡도도 빠르고 좋다고 생각했지만 문자열에서 여러가지의 비속어를 필터링 하기 위해서는 Aho-Corasick 알고리즘을 채택하기로 결정했다.
Aho-Corasick(아호 코라식) 알고리즘
- 간단하게 여러개의 패턴을 동시에 찾는 알고리즘이다. (일대다 문자열 패턴 매칭 알고리즘)
- 시간 복잡도는 다음과 같다.
O(n+m+z) -> n: 문장길이 , m: 트라이를 구성하는 노드 개수, z: 매칭된 금칙어의 총 개수
더 자세한 설명은 아래 사이트가 그림으로 잘 정리되어있다.
https://www.slideshare.net/slideshow/ahocorasick-algorithm/53152784
Aho-Corasick Algorithm(아호 코라식 알고리즘)
Aho-Corasick Algorithm(아호 코라식 알고리즘) - Download as a PDF or view online for free
www.slideshare.net
어렵다면 유튜브 링크도 참고 바람 (KMP, Aho-Corasick 알고리즘)
https://www.youtube.com/watch?v=etT5jb4r2hY&list=PL9mhQYIlKEhcqOXxPOhs6pNpq681RDK4J&index=9
https://www.youtube.com/watch?v=4XI91Q5ZkRs
Aho-Corasick 알고리즘을 간단하게 설명하자면
트라이 자료구조를 통해 문자열 패턴 매칭 과정이 이루어지고 해당하는 패턴 문자가 없을때는 포인터가 롤백을 하게 되는데
트라이에서 매칭을 하다가 매칭이 실패했을 경우 다른 곳으로 이동시키는 함수를 Failure function이라고 부른다.
반복 ~~
트라이 자료구조란?
트라이는 문자열을 저장하고 빠르게 탐색하기 위한 트리 형태의 자료구조로, 자동완성 기능이나 사전 검색 등 문자열 탐색에 특화되어 있습니다.
트라이 특징
- 루트 노드는 항상 비어있습니다.
- 문자열 탐색 속도가 O(N)으로 시간 복잡도 측면에서 효율적입니다.
- 각 검색 패턴의 문자마다 메모리가 할당되므로 메모리 사용 측면에서 비효율적일 수 있습니다.
Failure function의 정의 - 이 말이 이해가 안간다면 위에 유튜브 링크를 학습하면 이해가갈거다.
매칭에 실패한 문자 전까지의 일치한 문자열에 대해 접두사와 접미사가 같은 가장 긴 부분으로 이동
or
루트가 아닌 각 노드 v에 대해서 루트 -> w로 가는 경로가 루트 -> v로 가는 경로의 접미사이며, 그러한 것들 중 가장 긴 것.
Failure function 계산 방법
- 우선 루트에서의 깊이가 1인 노드들은 failure function이 루트로 자명하다.
- 그 다음, 루트에서의 깊이가 2인 노드들, 깊이가 3인 노드들을 순서대로 탐색한다면, 해당 노드보다 깊이가 낮은 노드들은 이미 다 계산이 완료되었기 때문에 failure function을 계산할 수 있다.
- 이 과정에서 BFS를 사용하기 때문에 한 줄의 코드를 추가하는 것 만으로도 output check를 뿌려줄 수 있게 된다. 고로 위에서 output check를 따로 코딩해야 하는 번거로움이 사라진다.
결국 과정은
1. 패턴 String들에 대한 Trie(트라이) 구성
2. Failure Link 와 Success Link(Output Link) 구성
- Output Link : 패턴을 찾아보다가 패턴을 찾았을때 어디로 이동할지
- Failure Link: 패턴을 찾아보다가 패턴을 찾지 못했을때 지금 상황에서 어디로 이동하는개 가장 효율적인지
3. Matching - 탐색 진행
이제 Aho-Corasick 알고리즘을 사용해서 비속어 필터링 기능을 구현해보겠다.
비속어 필터링 구현 코드 (Aho-Corasick 알고리즘)
import { badWords } from "@/constants/badwords";
interface TrieNode {
children: Map<string, TrieNode>; // 자식 노드들을 저장하는 Map
isEnd: boolean; // 현재 노드가 단어의 끝인지 여부
output: string[]; // 현재 노드에서 매칭되는 모든 패턴들
fail: TrieNode | null; // 실패 시 이동할 노드 (실패 링크)
}
class AhoCorasick {
private root: TrieNode;
constructor() {
this.root = this.createNode();
}
private createNode(): TrieNode {
return {
children: new Map(),
isEnd: false,
output: [],
fail: null,
};
}
// 트라이 구조에 패턴 추가
addPattern(pattern: string): void {
let node = this.root;
for (const char of pattern) {
if (!node.children.has(char)) node.children.set(char, this.createNode());
node = node.children.get(char)!;
}
node.isEnd = true;
node.output.push(pattern);
}
// 실패 링크 구축
buildFailureLinks(): void {
const queue: TrieNode[] = [];
this.root.fail = this.root;
// 루트의 자식들의 실패 링크는 루트를 가리킴
for (const child of this.root.children.values()) {
child.fail = this.root;
queue.push(child);
}
while (queue.length > 0) {
const current = queue.shift()!;
for (const [char, child] of current.children) {
queue.push(child);
let failNode = current.fail!;
while (failNode !== this.root && !failNode.children.has(char))
failNode = failNode.fail!;
child.fail = failNode.children.get(char) || this.root;
child.output = child.output.concat(child.fail.output);
}
}
}
// 텍스트에서 패턴 검색 및 치환
search(text: string, replacement: string): string {
let current = this.root;
let result = text;
const matches: { pattern: string; index: number }[] = [];
for (let i = 0; i < text.length; i++) {
const char = text[i];
while (current !== this.root && !current.children.has(char))
current = current.fail!;
current = current.children.get(char) || this.root;
if (current.output.length > 0) {
for (const pattern of current.output) {
matches.push({
pattern,
index: i - pattern.length + 1,
});
}
}
}
// 매치된 패턴들을 뒤에서부터 치환 (중복 치환 방지)
matches.sort((a, b) => b.index - a.index);
for (const { pattern, index } of matches) {
result =
result.substring(0, index) +
replacement.repeat(pattern.length) +
result.substring(index + pattern.length);
}
return result;
}
}
// 금칙어 필터 초기화 및 사용을 위한 유틸리티 함수
const initBadWordsFilter = () => {
const ac = new AhoCorasick();
// 금칙어 패턴 추가
badWords.forEach((word) => ac.addPattern(word));
// 실패 링크 구축
ac.buildFailureLinks();
// 필터링 함수 반환
return {
filter: (text: string) => ac.search(text, "*"), // 금칙어 필터링
containsBadWords: (text: string) => ac.search(text, "*") !== text, // 금칙어 포함 여부 확인
};
};
export const { filter, containsBadWords } = initBadWordsFilter();
마치며...
이번 경험을 통해 알고리즘을 많이 알아야겠다는 생각이 많이 들었다.
앞으로도 새로배운 알고리즘이 있고 적용해보는 경험이 생긴다면 다시 포스팅 올릴생각이다.
이해가 안가는 부분은 댓글 남겨주시면 감사하겠습니다!