Aho-Corasick 구현

invalid-file

검색에 의존적인 언어처리를 하다보니

전에는 전혀 고민의 대상이 되지 않았던 것들이 큰 부담거리로 다가온다.

대학원에서 형태소 분석기의 입력은 모두 띄어쓰기가 올바로 되어 있다고 가정하고,

띄어쓰기 오류가 틀렸다고 하더라도 그건 형태소 분석기의 몫이 아니기 때문에

처리하지 않아도 되는냥 생각했었다.

그러나 실제 서비스를 하는 필드에 와서는 앞에서 언급한 가정들이 모두 무시된다.

사용자가 잘못한것도 수정을 하여야 하고, 검색엔진의 부담을 덜어주기 위해서도 수정이 필요하다.

띄어쓰기 오류가 있는 문장은 형태소 분석기로 보내기 전에 띄어쓰기 오류를 수정하여야 하고

하나의 어절과 같이 사용되어야 하는 복합명사 형태의 단일어는 떨어져 들어오더라도 붙여서 분석을

해주어야 검색엔진의 부담을 덜어줄수 있다.(검색엔진의 부담을 덜어준다는것은 검색엔진이 위치정보를 계산한다면 두개의 어절이 입력했는지 계산하는것보다 색인시에 단일어로 만들어주는것이 검색시 시간효율이 생긴다는 의미이다. 물론 이방법을 검색에 사용할 시간을 색인시에 사용하다로 이야기할수 있다)

전자는 띄어쓰기 모듈을 개발함으로써 해결할수 있는데 후자에 언급한 떨어져 들어오는 쿼리를 하나의 어절로 만들어주는건

어떤 방법으로 구현할까..

만약 저런식으로 처리해야할 대상 어절이 많다면....그 처리 속도는...

이런 고민을 해결할수 있도록 도와준 알고리즘이 aho-corasick(이하 AC)이다.

문자열 매칭 알고리즘중 유명한것이 BM(Boyer-Moore algorithm)과 KMP(Knuth-Morris-Pratt algorithm )인데 이둘은 하나의 단어를 문장에서 찾고자 할때 효과를 볼수 있는 방법이다.

이에 반해 AC는 하나의 어절보다는 찾고자 하는 패턴이 다수일때 성능이 발휘된다.

AC를 개발하기 알아두어야 할 내용은 다음과 같다.

TRIE : 어떤 TRIE도 상관은 없다. array를 사용하는 TRIE든 Linked-list를 사용하는 TRIE든 아니면 다른 TRIE든 하나의 Node에 하나의 엔트리만 저장하는 구조라면 상관없다.

FAIL FUNCTION : KMP나 BM에서 시간을 절약하기 위해 앞에 비교한 패턴정보를 다음에 비교할 패턴에 이용한다. 흔히 FAIL FUNCTION이라고 하는데 이것에 대한 이해가 있어야 한다.

팀에 프로그램 구현능력이 좋은 분이 계셔서 테스트 버전을 7-8시간정도 걸려서 구현한것 같다.

이렇게 구현된 AC로

대상 문서 1.5G 문서

대상 패턴 : 13만개

비교시간 : 5분(딱 5분)

서버 사양은 회사기밀이라서....

여러개의 패턴을 하나의 문서에서 찾고자 한다면 AC만큼 좋은것도 찾기 어려울것 같다.

관련 자료
http://en.wikipedia.org/wiki/Aho-Corasick_algorithm

http://www-sr.informatik.uni-tuebingen.de/~buehler/AC/AC.html

http://hkn.eecs.berkeley.edu/~dyoo/python/ahocorasick/