[나만무] 채팅 금칙어 필터링 속도개선

intro..

게임 채팅 시스템을 만들었는데 뭔가 허전하다 뭔가 있어야 할 것 같은 느낌이였다.

 

흠.. 뭐지..뭔가 허전한데 하다 문득 생각난 금칙어(욕설) 필터링 기능..!

그래.. 필터링 없는 게임은 없었어..! 우리도 있어야해 

 

금칙어 db

금칙어 필터링 api가 있긴했는데.. 유료였다 돈내고 이용하는 것도 합당한 방식이지만 취업을 위한 포트폴리오라면 우리가 한번 구현해보는것도 멋진일 일 것이라고 생각이 들어서 직접 금칙어 필터링을 구현해보자고 했고.. 그래서 그럼 첫번째 단계로 금치어 db가 필요했다

금칙어 db에 존재하는 데이터들이 채팅에 포함되어있다면 이걸  "***" 이렇게 변환해서 보내보자란 생각이였다

 

그렇게 정처없이 검색을 하고 차라리 내가 직접 금칙어 db를 만들어볼까하다가 그래... 깃허브에 나와 같은 생각으로 금칙어 필터링을 만든 사람들이 있었고 다양한 레포리토리를 참고하면서  금칙어들 추가해가며 금칙어 db를 만들 수 있었다 ..

대략 천여개의 수많은 욕설들을 ... 추가 해줬다

 

필터링속도 개선

이제 금칙어 db에서 금칙어를 불러들어오고 채팅이 들어오면 채팅내에 금칙어가 들어있는 부분을 찾아서 *** 치환해 주면 되는데

처음에는 단순하게 금칙어 list를 for문으로 순회하면서 해당 문자열에 금칙어가 포함되어있다면 ***이렇게 변환 시켜줄려고 했는데 암만 생각해도 비효율 적이라고 생각햇다, 금칙어가 지금은 상대적으로 적어서 1000여개지만 금칙어 db를 잘 구현했다는곳을 보면 (유료 api 서비스 같은경우 60만개정도라고하니..) for로 순회해서 찾는건 상당히 비효율적이라는 결론이고 이와 관련해서 다양한 자료들을 찾아보다가

매우 적합한 알고리즘을 발견했다. 

 

 

아호 코라식-알고리즘

문자열 패턴 매칭 알고리즘 중 하나로 트라이(Trie) 자료구조를 바탕으로한 KMP 알고리즘을 구현한 느낌이다.

KMP가 문자열에서 패턴 하나를 찾아내는 1:1 패턴매칭 알고리즘 이라면 아호 코라식 알고리즘은 문자열에서 다수의 패턴을 찾아내는 1:다 패턴 매칭알고리즘이다.

 

아호 코라식 알고리즘의 시간 복잡도는 다음과 같은데

O(n+m+z)  ,  n: 문장길이 , m: 트라이를 구성하는 노드 개수, z: 매칭된 금칙어의 총 개수

 

즉 금칙어가 100개이든 1000000개이든, 문장을 한 번만 스캔하면 원하는 패턴을 모두 매칭 시킬 수 있는 알고리즘이다 ..!

 

이번에 우리 프로젝트에 적용한 아호 코라식 알고리즘이다.

export class AhoCorasick {
  private goto: { [key: number]: { [key: string]: number } } = {};
  private output: { [key: number]: string[] } = {};
  private fail: { [key: number]: number } = {};

  build(patterns: string[]): void {
    let newState = 0;
    for (const pattern of patterns) {
      let currentState = 0;

      for (const symbol of pattern) {
        if (!this.goto[currentState]) this.goto[currentState] = {};
        if (!this.goto[currentState][symbol]) {
          newState++;
          this.goto[currentState][symbol] = newState;
        }
        currentState = this.goto[currentState][symbol];
      }

      if (!this.output[currentState]) this.output[currentState] = [];
      this.output[currentState].push(pattern);
    }

    const queue: number[] = [];
    for (const symbol in this.goto[0]) {
      const state = this.goto[0][symbol];
      this.fail[state] = 0;
      queue.push(state);
    }

    while (queue.length > 0) {
      const currentState = queue.shift()!;
      for (const symbol in this.goto[currentState]) {
        const nextState = this.goto[currentState][symbol];
        let failure = this.fail[currentState];

        while (
          failure !== undefined &&
          (!this.goto[failure] || !this.goto[failure][symbol])
        ) {
          failure = this.fail[failure];
        }

        if (failure === undefined) {
          this.fail[nextState] = 0;
        } else {
          this.fail[nextState] = this.goto[failure][symbol];
          if (!this.output[nextState]) this.output[nextState] = [];
          this.output[nextState] = this.output[nextState].concat(
            this.output[this.fail[nextState]] || [],
          );
        }

        queue.push(nextState);
      }
    }
  }

  search(text: string): { pattern: string; index: number }[] {
    let currentState = 0;
    const results: { pattern: string; index: number }[] = [];

    for (let i = 0; i < text.length; i++) {
      const symbol = text[i];

      while (
        currentState !== undefined &&
        (!this.goto[currentState] || !this.goto[currentState][symbol])
      ) {
        currentState = this.fail[currentState];
      }

      if (currentState === undefined) {
        currentState = 0;
        continue;
      }

      currentState = this.goto[currentState][symbol];
      if (this.output[currentState]) {
        for (const pattern of this.output[currentState]) {
          results.push({
            pattern: pattern,
            index: i - pattern.length + 1,
          });
        }
      }
    }

    return results;
  }
}

 

 

아호 코라식 알고리즘의 핵심은 바로 실패함수라고 생각하는데, 패턴 매칭에 실패했다면 내가 다시 검색을 재시작 해야할 곳을 기억해서 패턴 매칭에 실패했다면 실패지점으로 기록한 곳으로가서 다시 검색을 시도하는것이다

 

자세한 정보는.. 해당 블로그글을 보면서 공부했다

 

https://m.blog.naver.com/kks227/220992598966

아호코라식(Aho-Corasick)

 

 

 

결론..

 

알고리즘을 다양하게 알아야할 필요성을 많이 느꼈다.

추가로 여기에 적은거 외에도 고려한 사항들이 좀 더 있는데..

• 아호코라식은 처음 트라이를 구성할때 시간이 상대적으로 많이 소모되기 때문에 이와 관련해서 언제 금칙어를 업데이트 시켜줘야 할까도 생각해보았는데..
  그래서  금칙어 db가 업데이트가 되었다면 웹훅과 같이 금칙어 db업데이트를 서버가 수신하고있다가 업데이트 신호를 받고 스케쥴러를 작동시킨다, 하지만 바로 작동하면 실사용 자가 많을때 트라이구조를 변경도 같이 수행 될 우려가 있기때문에, 이용자가 가장 없을 것이라고 예측한 새벽 3시에 업데이트를 해주도록 설정했다
• 이건 적용 못 한건데, 공백이나 숫자를 이용한 금칙어 회피를 정규식을 통해 막아보자는 생각도 있었지만 이건 적용을 하지 못했다. 
• 마지막으로 허용어 db(단어의 일부에 금지어가 포함되었지만 전체적인 단어가 금지어가 아닌것들,..) 까지 있었다면 좀더 탄탄한 필터링이 되었을 것이라고 생각...!