문자열 매칭1 Python에서 AhoCorasick(아호코라식) 알고리즘 구현하기 지금 캐글에 논문을 입력으로 받아 논문에서 사용된 데이터셋 이름을 찾는 대회가 진행 중이다. 만약 알고 있는 데이터셋 이름이 있다면, 논문 속에서 그 이름을 단순 문자열 매칭을 이용해서 찾아내어서 출력에 반영할 수 있을 것이다. 처음에는 Test 셋이 몇 개 없는 줄 착각하고 단순 2중 for문으로 이를 구현했었다. 그러나 숨겨진 test 셋에 문서가 8000개가 넘어서 문자열 매칭만 하였음에도 50분이 넘게 걸렸었다. 그래서 이 부분을 다중 패턴 매칭 알고리즘인 아호코라식을 사용하여서 구현하였다. 아호코라식 알고리즘은 찾아야 하는 패턴이 많을 때 단순 2중 for문에 비해 큰 시간 차이를 보인다. 또, 검색해야 하는 범위가 방대할 때, 아호코라식으로는 커피 두 잔 정도 타는 시간에 끝낼 수 있을 것들이.. 2021. 4. 17. 이전 1 다음