Plaything에서는 채팅이 핵심 기능 중 하나다.
그런데, 19금 서비스 특성상 문제가 될 법한 메시지가 전송되지 못하도록 막아야 한다는 문제가 있다.
성적인 제안을 하거나 금전적인 거래가 오가는 걸 막아야 한다.
굉장히 복잡하고 어려운 기능이지만..
우선 만들어야 하기에 지금 할 수 있는 선에서 최선을 다해 만들어보자.
알고리즘을 공부를 해보자!
참고: 고르곤졸라는 되지만 고르곤 졸라는 안 돼! 배달의민족에서 금칙어를 관리하는 방법
이걸 보면 생각할 부분들이 많이 보인다.
'졸라'라는 단어가 있다고 무조건 금지하면 안 된다.
'고르곤졸라'라는 단어에 '졸라'라는 단어가 있고 '리조또'에 '조또'라는 단어가 있다고 해서 무작정 금지하면 안 된다.
다만, 이건 지금 단계에서 고려하기엔 너무 많은 변칙 사례들이 있다. 우선, 확실하게 사용해선 안되는 단어를 금지하고서 그 이후로 개선해나갈 필요가 있다.
조회 패턴을 고려해라
금칙어를 DB에서 매번 조회하는 것은 불필요하다. 한번 생성되면 수정이 잘 발생하지 않고, 생성 빈도는 조회보다 훨씬 적기 때문이다. 조회할 때마다 매번 동일한 데이터를 받으니 조회 행위가 리소스 낭비가 될 수 있는 것이다.
그래서 배민에서는 10초, 1분 등 주기적으로 폴링한다고 한다.
조회 속도가 빠른 레디스를 활용하자
금칙어를 빠르게 찾아야 한다.
배민에서는 여러 도메인에서 금칙어 라이브러리를 쓰기 때문에 '범용적'일 필요가 있었다.
우리는 '자기 소개 문구', '닉네임', '채팅 메시지' 여기서 범용적으로 쓸 수 있어야 한다.
또, 길이가 긴 문장도 금칙어 검사 속도가 빨라야 한다(그렇기에 채팅 메시지도 글자수 제한을 두는 게 좋을 것 같다)
이에 배민은 아호코라식 알고리즘을 사용했다고 한다.
이 세가지 선택지가 있었다고 한다.
1) 형태소 분석기
주로 쓰는 nori 형태소 분석기는 Elastic에서 개발한 한국어에 특화된 분석기다. 문장을 입력하면 문장 속 단어들의 형태소를 분석해, 조사 어미 등 부가적인 부분은 제외하고서 명사 등 순수 단어로 탐색하는 기능을 제공한다.
다만, 단점들로는
- '맛있게 만들고자' 라는 단어에 금칙어가 있다고 판단한다. 그래서, 검사 결과를 자신있게 예측하기 어렵다.
- 형태소 분석기에는 자체 구추고딘 단어 사전이 존재하는데, 이 사전에 어떤 단어가 존재하는지 개발자가 열어보기 어렵다고 한다. 확장도 어렵다.
그래서, 형태소 분석기를 사용하지 않고 문장에 금칙어가 '포함'되는지를 직접 확인하는 방식으로 변경했다고 한다.
2) String.contains() 메서드
List에 단어들을 넣어두고, for문으로 금칙어가 있는지 확인하는 방식이다. 다만, 성능적으로 너무 안 좋았다. 어쩔 수 없다. List의 경우 문장 길이(n), 금칙어 개수(m) 때문에 o(nm) 시간 복잡도가 되기 때문이다.
3) 아호코라식 알고리즘
이 알고리즘은 문자열 탐색 알고리즘 중 하나로, 하나의 문장에서 여러개의 문자열을 찾고자 할 때 적합하다.
이 알고리즘은 내부적으로 Trie 자료구조를 사용한다. 찾고자 하는 단어 목록을 트리 형태로 만들어두고, 트리를 따라가면서 일치/불일치 여부를 판단한다.
문장 길이(n), 트라이를 구성하는 노드 개수(m), 매칭딘 금칙어의 총 개수(z)
로 해서 시간 복잡도가 O(n+m+z)다.
아호코라식 알고리즘이 뭐야?
사실 이 글만 보고서는 무슨 알고리즘이라는 건지 감이 잘 안 잡혔다.
참고: [알고리즘] 아호 코라식(Aho-Corasick) 알고리즘
S = "abababdddd"
W = {"bab", "bd", "ab"}
이렇게 단어가 있고, S문장에 W단어가 포함되는지 확인한다고 해보자.
이렇게 c->a->b->a 이런식으로 문자열을 하나씩 탐색한다.
위에 사진을 보면 'bab' 부분이 일치한다.
하지만, bab다음에 다시 'b'가 와야 하는데 'bab' 노드 다음에는 'b'가 없다.
이때 포인터를 롤백시킨다.
어디로?
이곳으로 간다.
이때는 bab에서 ba까지는 성공했으니, 이 ba로 시작하는 지점에서 시작하는 것으로 보인다.
