Day 23 (3) : 아호코라식을 쓴 Chat Keywords 검색 알고리즘

 

아호코라식은 KMP를 트라이에서 쓰는 알고리즘이다

트라이의 각 노드는 매칭을 확인할 글자, 성공시 넘어갈 자식노드, 실패시 돌아갈 실패함수의 리턴 노드를 갖고있고,

리프노드라면 매칭 성공시 아웃풋 함수를 실행시킨다.

 

KMP가 하나의 검색어 = 1차원 스트링에서 실패함수를 만들듯이

아호코라식은 여러개의 패턴을 트라이로 묶어 거기서 실패함수를 만든다.

 

브루트포스나 KMP는 n개의 검색어를 검색하면 n배의 시간이 들지만, 아호코라식은 그렇지 않은 것이 장점

 

 

알고리즘 공부할때 구현해둔 class가 있어서 가져다가 써보니

시연에 쓸 슈카월드 영상에서 키워드를 검색하는데 0,1초만에 끝난다

 

굿

 

디스크를 읽는 작업이고, 나름 5만명이 본 4시간짜리 영상인데도 성능이 꽤 좋다

이정도면 물건너 버튜버가 등판해도 1초컷할듯

 

KMP도 만들어둔게 있어서 긁어와서 돌려보니 검색어 갯수에 따라 정비례하는 시간이 걸리는것과 차이가 있다

 

비속어필터링이든 자동완성이든 json 파싱이든 나만무때 뭘 만들더라도 문자열을 탐색할 일이 있으면 일단 쓸것같아서

다이아 찍을때 배워뒀는데 쓸모가 있어서 다행이다

 

이걸 함수의 형태로 가공해서 서버의 post에 연결하면

프론트에서 기능 구현중인 팀원이 axios를 만들어서 요청했을 때 키워드 출현 Distribution을 보내줄 수 있다.