아호코라식(Aho-Corasick) 알고리즘

아호코라식(Aho-Corasick)은 일대다 패턴매칭 알고리즘으로 문자열에 문자가 존재하는지 판별하는데 탁월한 성능을 제공합니다. 

 

많지 않은 데이터를 처리할때는 일반적인 방법으로도 쉽게 처리 가능하지만 100,000건 이상의 데이터에서 특정 단어를 빠르게 찾는건 쉽지 않습니다. 

검색에서 사용자사전, 동의어사전 등의 데이터를 아호코라식을 이용해 키워드를 추출하는데 매우 유용합니다. 

빠른 성능과 쉬운 사용법을 제공합니다. 

단순히 dependency를 추가하고 간단하고 짧은 코딩만으로 큰 효과를 얻을 수 있습니다. 

 

참고 : https://m.blog.naver.com/kks227/220992598966

아호코라식(Aho-Corasick)

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

GitHub - robert-bor/aho-corasick: Java implementation of the Aho-Corasick algorithm for efficient string matching

1. Dependency 추가 

<!-- https://mvnrepository.com/artifact/org.ahocorasick/ahocorasick -->
<dependency>
    <groupId>org.ahocorasick</groupId>
    <artifactId>ahocorasick</artifactId>
    <version>0.6.3</version>
</dependency>

2. 사용법 

// 생성 및 데이터 추가 
Trie trie = Trie.builder()
    .addKeyword("hers")
    .addKeyword("his")
    .addKeyword("she")
    .addKeyword("he")
    .build();

// 키워드 찾기     
Collection<Emit> emits = trie.parseText("ushers");

 Trie 생성 및 설정 

설정	내용
* ignoreOverlaps	* 중복무시, 가장 긴 문자열이고 가장 왼쪽에 매치 되는 문자열을 우선 반환.
ignoreCase	대소문자무시
onlyWholeWords	전체 키워드 매치
* onlyWholeWordsWhiteSpaceSeparated	* 화이트 스페이스로 분리한 키워드 매치
stopOnHit	첫번째 키워드만 반환

생성 및 이용 예시 

// 화이트 스페이스로 분리된 단어 매치 + 대소문자무시 
Trie.TrieBuilder trieBuilder = Trie.builder().onlyWholeWordsWhiteSpaceSeparated().ignoreCase();
// 중복제거, 대상이 되는 문자열 중에 가장 긴 키워드 반환 + 대소문자무시 
Trie.TrieBuilder trieBuilder = Trie.builder().ignoreOverlaps().ignoreCase();

// 사전에서 키워드 데이터를 가져온다. 
List<String> dictionaries = getDictionaries();

// 단어를 추가한다. 
dictionaries.stream().forEach(i->trieBuilder.addKeyword(i));

// build()
Trie ahoDictionaries = trieBuilder.build();

// 사용 
String text = "각시방편백나무침대";
for (Emit aEmit : this.ahoDictionaries.parseText(text)) {
    System.out.println("keyword : "+aEmit.getKeyword());
}

public void test() {
    PayloadTrie<String> trie = PayloadTrie.<String>builder().ignoreOverlaps().ignoreCase()
            .addKeyword("nike", "나이키")
            .addKeyword("나잌", "나이키")
            .addKeyword("나이키", "나이키")
            .addKeyword("신발", "운동화")
            .addKeyword("shoes", "운동화")
            .build();
        Collection<PayloadEmit<String>> emits = trie.parseText("nike shoes");
        for (PayloadEmit<String> aEmit : emits) {
            System.out.println("keyword : "+aEmit.getKeyword());
            System.out.println("payload : "+aEmit.getPayload());
        }
}

output

keyword : nike
payload : 나이키
keyword : shoes
payload : 운동화