반응형
Aho–Corasick string matching algorithm
패턴 집합에 대한 매칭 알고리즘
타 알고리즘 시간 복잡도 :
- (
: 모든 패턴들의 길이 합,
: 패턴 수,
: text 크기)
![O(m + zn)](https://upload.wikimedia.org/math/3/6/d/36d7b46833abfb2140d067f123eb3632.png)
![m](https://upload.wikimedia.org/math/6/f/8/6f8f57715090da2632453988d9a1501b.png)
![z](https://upload.wikimedia.org/math/f/b/a/fbade9e36a3f36d3d676c1b808451dd7.png)
![n](https://upload.wikimedia.org/math/7/b/8/7b8b965ad4bca0e41ab51de7b31363a1.png)
Aho–Corasick 알고리즘 시간 복잡도 : (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') |
- 끝 -
반응형
'역량 UP! > Algorithm' 카테고리의 다른 글
모나드?? (어렵네-_-;;) - 작성 중 (0) | 2022.01.13 |
---|---|
Aho corasick 알고리즘 (0) | 2018.01.05 |