• Aho-corasick
    • 다중패턴매칭 알고리즘이다. 
      • 예를들어 미리 구축해 놓은 사전(혹은 복수개의 검색어 리스트)에 아래의 단어가 저장되어 있다고 하자 (이하 사전단어라 칭함.)
        • no
        • now
        • here
        • where
        • nowhere
      • 사용자의 입력이 'dreamisnowhere' 가 들어왔을 때 substr 으로 발견되는 모든 사전단어를 찾아내야 하는 일을 생각해보자. 
      • 단순하게 생각하면 string class 에서 제공하는 substr을 이용하여 찾을 수도 있다. 
        • 사전단어 중에서 max 길이를 알아내고 가능한 모든 경우를 사전에 있는지 찾아보는거다
        • 물론 이렇게 하면 된다. 하지만 시간이 오래걸리고 매우 똑똑하지 못한 방법이다. 
      • 이러한 경우의 문제를 똑똑하게 풀어내기 위해 제안된 여러 다중패턴매칭 알고리즘 중 대표격인 알고리즘이다.
    • 구조
      • Trie 구조 + FailFunction Table
      • 구조는 위와 같이 단순하다.
    • 알고리즘 설명
      • 아래 블로그에 알고리즘에 대해 자세히 설명되어 있다. (다시 설명하는 번거로움 보다는 잘 설명된 곳을 알려드리는 편이 나을 듯 하여...)
    • 동작 시뮬레이션
  • Aho-Corasick 라이브러리
    • 언어 c++
    • 특징
      • 기본 Aho-Corasick 구현부는 다른 라이브러리와 동일함.
      • Dump 기능 - Aho-corasick 을 구성한 후 구성된 자료구조를 binary db 파일로 생성이 가능하다. 
      • 다중검색 기능 - 위의 시뮬레이션 사이트에서 검색을 위애 옮겨다니는 노드 포인터를 복수개로 늘린 버젼을 제공한다.
        • 이와 같은 기능은 다양한 인식 시스템에서의 후처리 업무를 하고 있는 필자의 경우 wfst로 구성된 복잡함 graph 내에서 사전단어를 검색하는 경우 유용하게 사용된다. 
    • 빌드환경
      • Windows visual studio 10.0'


+ Recent posts

티스토리툴바