👨🏻‍💻 금칙어 필터링 기능을 분석하고 리팩토링 해보자! (1) - Trie 자료구조 및 라이브러리들 분석

👀 Overview

Space club 프로젝트를 진행할 당시, 각 클럽 별 게시글을 작성하거나 공지, 댓글등을 작성할 때 금칙어가 포함되어 있을 경우 아래 그림과 같이 작성에 실패했다는 모달을 보여주며 작성에 실패하게 처리를 했었다.

이때, 입력받는 값에 금칙어를 찾는 과정에 있어서 Trie 자료구조를 사용했는데, 그때의 생각프로세스를 정리해 보고자 한다.

또한, 현재 프로젝트 코드레벨에서의 문제점은 없는지 고쳐 보려 한다.

글 입력시 금칙어가 포함되어 있을 경우 작성 불가

🔭 자료구조 / 알고리즘 선택하기!

먼저 우리는 지금 구현해야하는것이 특정 문자열이 주어졌을 때, 해당 문자열에 금칙어가 포함되어 있는지 여부를 확인하고 싶다.

먼저, 금칙어를 List 자료구조로 저장해 놓고 비교를 한다면, 금칙어 List 크기가 N이고, 입력받는 문자열의 길이가 M일때, 

시간복잡도는 O(MN)이 된다.

 

이때, 시간복잡도를 줄일 수 있는 방법은 없을지 고민했다.

문자열 관련 시간복잡도..? 알고리즘?

 

먼저 머리속에 떠오른건 알고리즘 학습 시 학습했던 KMP 알고리즘이였다.

다행히 KMP 알고리즘은 예전에 알고리즘을 학습하며 정리해 놓은 글이 있어 [여기]를 참고하면 된다!

 

[KMP 알고리즘의 한계]

하지만 이 KMP 알고리즘은 하나의 긴 패턴을 대량의 텍스트에서 검색할 경우에 효과적이다.

문자열 알고리즘이라고 해서 떠올려봤지만, KMP 알고리즘은 

우리가 금칙어 개수가 N일경우, N마다 O(M+ P)의 시간복잡도가 걸리기에 (P는 금칙어의 길이) 전체 시간복잡도는 대략적으로 O(MN)이 된다. ➡ 효과 없음

 

[해결책 : 검색하자!]

그래서 나는 어떤 것을 사용하는지 찾아보았고, Trie 자료구조를 사용한다면 문자열 검색에 효율적인 것을 알 수 있었다.

추가로, 아호코라식(Aho-Corasick) 알고리즘이라는 것을 알게되었고, 이번에 공유해 보고자 한다.

🌳 Trie 자료 구조란

트라이는 트리의 일종으로 문자열을 다루는 자료구조이다. 

각 노드는 문자 하나와 문자열 완성 여부를 나타내며, 트라이를 어떤 경로로 타고 내려가는지에 따라 문자열이 조합된다.

 

Tree 자료구조 / 출처 : https://www.javatpoint.com/tree

위 Tree자료구조에서 이진 검색으로 특정 노드를 검색하는 것은 O(logN)의 시간복잡도가 걸린다.

하지만 정수가 아닌 문자열을 검색하면 어떻게 될까?

노드에 있는 문자열의 길이가 M일때, 시간복잡도는 O(MlogN)이 된다. (정렬된 문자를 찾고, 문자열을 순회해야 하기 때문에)

이 문제를 해결하기 위해서 Trie라는 자료구조를 이용할 수 있는데,

Trie 자료구조 / 출처 : https://en.wikipedia.org/wiki/Trie

Trie 자료구조는 하나의 노드가 26개(알파벳)*2(대소문자) + 숫자 (0~9) 총 62개 노드를 가질 수 있을 것이다.

이렇게 저장해놓는다면, 문자열의 길이가 M일때, 검색을 O(M + K)의 시간으로 찾을 수 있다. (K는 입력 문자열에 포함된 금칙어 총 길이)

 

이 Trie 자료구조를 사용한다면, 다수의 금칙어를 한번의 입력 문자열 스캔만으로 검사을 할 수 있다!

따라서 이러한 정보를 바탕으로 우리 서비스의 금칙어 처리 기능에 Trie 자료구조를 도입했다.

 

🤔 아호 코라식 알고리즘이란? (Aho-Corasick Algorithm)  

아호 코라식 알고리즘이 뭔지 찾아보니, KMP 알고리즘이 일대일 문자열 패턴 매칭 알고리즘이였다면, 아호 코라식 알고리즘이란 일대다 문자열 패턴매칭에 사용되는 알고리즘이다.

아호 코라식 알고리즘은 KMP 알고리즘의 확장이며, 메커니즘은 비슷하다고 한다.

 

KMP 알고리즘이 문자열과 문자열간의 매칭이라면, 아호 코라식은 문자열과 트라이 간의 매칭이다.

 

원리는, 다음과 같은 트라이가 있을 때, (S는 입력받는 문자열, W가 금칙어 목록들이라 생각하면 된다)

아래와 같이 문자열 S를 돌면서 금칙어 여부를 판별하는데, 매칭에 실패 했을 경우 포인터를 실패한 문자 전 까지의 일치한 문자열에 대해 접두사와 접미사가 같은 지점으로 이동시킨다.

출처: https://pangtrue.tistory.com/305

트라이에서 매칭 과정 ❘ 출처: https://pangtrue.tistory.com/305

트라이에서 매칭 중 실패한 상황 ❘ 출처: https://pangtrue.tistory.com/305

위 경우 매칭이 실패 했을 경우 가리키는 지점을 이동시키는 fail 함수를 통해 포인터를 접두사와 접미사가 같은 지점인 a (5번 인덱스)로 이동시킨다.

 

시간복잡도를 따져보자면, Trie가 만들어져 있는 상황에서, 입력 문자열의 길이가 M이고, 문자열에서 발견된 패턴(금칙어) 발생 횟수가 Z일때, 시간복잡도는 O(M+Z)가 된다. 

 

🥸 Trie 라이브러리 선택하기

자 그럼 이걸 프로젝트에 적용해보자.

찾아보니, 자바에서는 Trie에 대한 자료구조를 기본적으로 제공하지 않는다. (Python 경우 제공한다고 한다)

이걸 구현할 수도 있겠으나 매우 효율이 낮을 것이다. 그래서 다른 사람들이 잘 만들어 놓은 라이브러리를 가져다 쓰면 된다고 판단했다.

 

먼저 팀원이 프로젝트 진행 당시 사용한 라이브러리는 다음과 같다.

https://github.com/npgall/concurrent-trees

GitHub - npgall/concurrent-trees: Concurrent Radix and Suffix Trees for Java

위 라이브러리는 Concurrent Radix Tree와 Concurrent Suffix Tree를 제공한다.

README와 document를 보니 쓰기작업에 대해서는 lock 걸기에 thread의 blocking이 일어나지만, 읽기작업에 대해서는 lock을 걸지않는다고 한다.

쓰기 작업 발생 시 일어나는 일 / 출처 : https://github.com/npgall/concurrent-trees?

이렇게 Trie 구조에 대해서 추가할때 구조를 알아서 바꿔주고, 동시성까지 보장해준다니 동적으로 운영중인 트라이에 금칙어를 추가 할 수도 있겠다는 생각이 든다.

그럼 Radix Tree와 Suffix Tree는 대체 뭘까?🧐

 🌲 Radix Tree에 대해서

Trie vs Radix Tree (출처 : https://www.youtube.com/watch?v=E8ZGt2i3xkw)

Radix Tree는 위 그림 처럼, 공통 접두사를 사용하는 키들을 하나의 경로로 압축해 저장해 메모리 사용율을 줄인다.

Node의 깊이가 얕아지기에, 검색 경로가 짧아지고 검색 시간이 단축된다.

 

위 라이브러리에 가보면, Radix Tree도 Radix Tree, Reveresed Radix Tree, Inverted Radix Tree로 나뉘는데

사용 예시와 document를 보고 어느 경우에 어떤 자료구조를 사용하면 좋은지 알 수 있었다.

Radix Tree는 key와 정확히 일치하는지, 그리고 특정 키로 시작하는 단어를 찾을때 사용하면 된다.

Reversed Radix Tree는 반대로 어떤 키로 끝나는지 알고싶을때 사용하면 된다.

Inverted Radix Tree는 외부 문서에서 포함된 특정 키워드를 찾고 싶을 때 사용하면 된다.

따라서 내가 사용하는 입력 받은 문자열에 포함된 금칙어들을 찾으려 한다면, Inverted Radix Tree를 사용하면 된다. (docs에 잘 예시가 나와있다)

 

 🌲 Suffix Tree에 대해서

출처 : https://github.com/npgall/concurrent-trees/blob/master/documentation/ConcurrentSuffixTreeUsage.md

Suffix Tree는 위와같이 단어의 모든 접미사를 저장한다. 따라서 Radix Tree에 비해 상대적으로 많은 메모리를 사용한다. (단점)

 

그러면 왜 이렇게 모든 단어의 경우의수(접미사)를 저장할까?

이유는 문자열에 대한 검색 시 필요하기 때문인데, 기본 Radix Tree 자료구조상 위 TOAST 문자열에서 TO, TOA로를 TOAST를 찾을 수 있지만, OA, OAS 같은 문자로는 TOAST를 찾을 수 없는데, 이 문제를 Suffix Tree를 사용하면 해결할 수 있다.

 

따라서 Suffix Tree는  특정 부분 문자열이 포함된 문자들을 구하는데 사용할 수 있다. (장점)

 

 

🧐 팀원이 짜 놓은 코드를 분석하고 고쳐보자!

private final InvertedRadixTree<String> TRIE = new ConcurrentInvertedRadixTree<>(new DefaultCharSequenceNodeFactory());

위 InvertedRadixTree에 금칙어를 애플리케이션 로드시 PostConstruct를 메서드에서 메모리에 업로드 후 → 문자열 입력시 contain하는지 검증한다.

 

아래 공식문서에 따르면, DefaultCharSequenceNodeFactory는 suffix tree 사용시 메모리 효율을 높혀 줄 수 있다고 한다. 

하지만 우리는 Inverted Radix Tree를 사용하기 때문에 가장 추천되는 SmartArrayBasedNodeFactory로 바꿔주자.

 

외부 라이브러리를 사용하는 경우, 팀 내 규칙으로 학습테스트를 작성하고, 노션으로 해당 라이브러리에 대한 문서화를 진행해 팀원들에게 사용한 의도를 납득시키는 과정이 필요할 것 같다.

 

🤛🏻 이 라이브러리가 최선일까..?

지금 사용한 라이브러리는 Trie 자료구조를 만드는 데 사용한 라이브러리이다.

이는 List와 비교하면 시간복잡도를 줄일 수는 있지만, 아호 코라식 알고리즘을 사용하면 더 좋지 않을까?

 

2편에서 계속

링크 : 👨🏻‍💻금칙어 필터링 기능을 분석하고 리팩토링 해보자! - (2) 실제 성능을 측정해보자!

 

Reference

아호 코라식 알고리즘 : https://pangtrue.tistory.com/305

트라이 자료구조 : https://www.youtube.com/watch?v=TohdsR58i3Q

Suffix Tree / Radix Tree:

https://www.youtube.com/watch?v=N70NPX6xgsA

https://cd4761.blogspot.com/2017/02/suffix-tree.html

https://comdolidol-i.tistory.com/149#%EC%A0%91%EB%AF%B8%EC%82%AC%20%ED%8A%B8%EB%9D%BC%EC%9D%B4(Suffix%20trie)-1