Ace-T's Blog 내 검색 [네이버 커넥트 이웃 합니다~^-^/ 요청 大 환영~~]

Aho–Corasick string matching algorithm란?

Architecture/algorithm 2016.03.30 17:34
[Good Comment!!, Good Discussion!!, Good Contens!!]
[ If you think that is useful, please click the finger on the bottom~^-^good~ ]
by ace-T



Aho–Corasick string matching algorithm

패턴 집합에 대한 매칭 알고리즘
타 알고리즘 시간 복잡도 : O(m + zn)  - (m : 모든 패턴들의 길이 합, z : 패턴 수, n : text 크기) 

Aho–Corasick 알고리즘 시간 복잡도 : O(m + n + k)  (k : 텍스트 내에 패턴의 발생 수) 

Aho-Corasick 알고리즘을 구현하기 위하여 Keyword Tree, Failure link, Output link 자료구조를 사용하여야 한다.


음..대충 이런 알고리즘이라는 것을 알게 되었다.

좋은 오픈 되어진 소스를 발견!

https://github.com/robert-bor/aho-corasick


디펜던시를 넣고 개발을 하면 되겠다!


메이븐

    <dependency>

        <groupId>org.ahocorasick</groupId>

        <artifactId>ahocorasick</artifactId>

        <version>0.3.0</version>

    </dependency>


그래들

compile('org.ahocorasick:ahocorasick:0.3.0')                            



참고 : https://ko.wikipedia.org/wiki/%EC%95%84%ED%98%B8_%EC%BD%94%EB%9D%BC%EC%8B%9D_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98



  - 끝 -



저작자 표시 비영리 변경 금지
신고

'Architecture > algorithm' 카테고리의 다른 글

Aho–Corasick string matching algorithm란?  (0) 2016.03.30

acet 박태하가 추천하는 readtrend 추천글!

설정

트랙백

댓글

:::: facebook을 이용하시는 분들은 로그인 후 아래에 코멘트를 남겨주세요 ::::

티스토리 툴바