우선
implementation 'org.ahocorasick:ahocorasick:0.6.3'아호코라식 알고리즘으로 문장 속 단어를 찾아주는 라이브러리를 추가해준다.
관련내용은 여기서 볼 수 있다.
이렇게 금칙어가 어디서부터 어디서까지 시작되는지를 확인할 수 있다.
'돈까스'에 돈과 돈까스가 겹치는데, 이렇게 중복되는 걸 찾지 않으려면 ignoreOverlaps()를 붙이면 된다.
이 경우는 더 긴 단어가 나온다고 한다.
이 경우는 완전한 일치만 찾는 api다.
ignoreCase()를 붙이면 대/소문자 구분이 없어진다.
firstMatch()를 사용하면, 처음 매치를 찾을 때 검색을 종료한다. 우리 상황에 잘 쓸 수 있을 것이다.
매칭에 걸리는 게 없으면 null을 반환한다.
Trie를 캐시해야할까?
레디스에 금칙어 목록을 저장하고, 이걸 조회해서 Trie를 빌드하는 걸 생각했는데
매번 Trie를 빌드하는 것도 비용이 들지 않을까 싶다.
그렇다면, Trie를 캐시해두는 건 어떨까?
public static void main(String[] args) throws InterruptedException {
List<String> list = new ArrayList<>();
for(int i =0; i<3000; i++){
list.add("aabc"+i);
}
System.gc();
Thread.sleep(100);
System.gc(); // 한번 더 GC
Thread.sleep(100);
long before = getUsedMemory();
Trie trie = Trie.builder()
.addKeywords(list)
.build();
// 워밍업은 여러번
for(int i = 0; i < 10; i++) {
trie.parseText("test" + i);
}
System.gc();
Thread.sleep(100);
System.gc();
Thread.sleep(100);
long after = getUsedMemory();
System.out.println("Memory used: " + (after - before) + " bytes");
}
private static long getUsedMemory() {
return ManagementFactory.getMemoryMXBean().getHeapMemoryUsage().getUsed();
}
사용하는 메모리 양이 1.5MB라서 캐싱해두는 것도 나쁘지 않을 듯하다.
매번 빌드하는 것이 더 많은 메모리를 쓸 수 있기 때문...
List<String> list = new ArrayList<>();
for(int i = 0; i < 3000; i++){
list.add("aabc"+i);
}
long totalBuildMemory = 0;
int iterations = 10;
for(int i = 0; i < iterations; i++) {
System.gc();
Thread.sleep(100);
long buildStart = getUsedMemory();
Trie trie = Trie.builder()
.addKeywords(list)
.build();
long buildEnd = getUsedMemory();
totalBuildMemory += (buildEnd - buildStart);
}
System.out.println("Average build memory: " + (totalBuildMemory / iterations) + " bytes");
빌드 시엔 1.1mb정도를 사용한다.
List<String> list = new ArrayList<>();
for(int i = 0; i < 3000; i++){
list.add("aabc"+i);
}
long totalBuildTime = 0;
int iterations = 10;
for(int i = 0; i < iterations; i++) {
System.gc();
Thread.sleep(100);
long startTime = System.nanoTime();
Trie trie = Trie.builder()
.addKeywords(list)
.build();
long endTime = System.nanoTime();
totalBuildTime += (endTime - startTime);
}
System.out.println("Average build time: " + (totalBuildTime / iterations / 1_000_000) + " ms");
빌드에 걸리는 시간은 19ms로 매우 짧지만 채팅메시지마다 이걸 빌드하는 건 매우 비효율적이다.
채팅에 사용하는 만큼 캐시해놓고 사용하는 게 좋을듯하다.
시간은 얼마나 걸릴까?
public static void main(String[] args) throws InterruptedException {
List<String> list = new ArrayList<>();
for (int i = 0; i < 100; i++) {
list.add("abc" + i);
list.add("안녕");
list.add("abc" + i);
}
Trie trie = Trie.builder()
.addKeywords(list)
.build();
String[] testTexts = {
"hello world abc123",
"안녕하세요 반갑습니다",
"this is test message hello55",
"no matching words here",
"abc99 appears at start",
"multiple matches hello1 abc2 안녕",
"잘 있어요 안녕",
"안녕! 반가워!",
"안녕 행복하니?",
"잘 지내길!",
"뭐해?",
"abc",
"abcd",
"abc abc",
"안녕하십니까?",
"잘있어요!",
// 일반적인 대화
"hello world abc123",
"안녕하세요 반갑습니다",
"오늘 날씨가 참 좋네요",
"저녁 먹고 영화 볼까?",
"주말에 뭐하세요?",
// 금칙어 포함
"abc99 appears here",
"multiple matches abc2 안녕",
"안녕! 잘 지내?",
"abc abc abc",
// 긴 문장
"오늘 날씨가 참 좋아서 공원에 산책을 갔다왔어요. 안녕하세요!",
"This is a long sentence with multiple words and possible matches like abc123",
// 특수문자/이모지 포함
"안녕~!! 😊 반가워요!",
"abc...123...안녕!!",
// 실제 채팅 스타일
"ㅋㅋㅋ 안녕 뭐해?",
"오늘 저녁에 abc 카페에서 만나자",
"헐 대박!! abc99 진짜??",
// 띄어쓰기 변형
"a b c 9 9",
"안 녕 하 세 요",
// 반복
"안녕안녕안녕",
"abcabcabc",
// 랜덤 텍스트
"qwerty keyboard",
"12345 67890",
"!@#$% ^&*()",
// 혼합
"abc55 hello 안녕 testing",
"한글과 abc123이 섞여있는 문장"
};
for (int i = 0; i < 10; i++) {
long startTime = System.nanoTime();
for (String text : testTexts) {
trie.firstMatch(text);
}
long endTime = System.nanoTime();
System.out.println((endTime - startTime) / 1_000_000 + "ms");
}
}
}대략 50개의 문장이다.
이정도면 속도가 굉장히 빠르다
답을 찾기 위해서 노력하는 사람