[아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (3) - 성능 측정

이전 글에서는 아호코라식 알고리즘의 구조에 대해서 알아보았다.

이번 글에서는 아호코라식과 엘라스틱서치(ES) 로 검색을 했을 때 성능 측정을 간단하게 해볼 것이다.

결론

색인 키워드: 5543 개

검색 요청: 1000 개

	아호코라식	ES
메모리 사용량	5 mb	2 mb
색인 시간	42 ms	286 ms
검색 시간	7 ms	2051 ms

• 아호코라식이 압도적으로 빠르다. (색인시간은 약 6.8배, 검색시간은 약 293배 빠름)
• 메모리 사용량은 아호코라식이 더 잡아먹는다. (ES 보다 2.5배)
• 아호코라식은 색인시간이 검색시간보다 더 오래걸린다. (42 ms > 7 ms)
• ES는 검색시간이 색인시간보다 더 오래걸린다. (2051 ms > 286 ms)

※ 검색 결과는 고려하지 않았다.

자세한 이야기

[색인 키워드] 한글로 이루어진 단어 5543 개이다.

[검색 키워드] 아무 키워드로 검색하면 결과 없음이 다수 출현할 수 있으므로 색인 키워드를 edge_ngram 한 리스트 중에 랜덤으로 1000 개를 뽑았다.

아호코라식 구현하기

디펜던시

implementation 'org.ahocorasick:ahocorasick:0.6.3'

자바는 아호코라식 라이브러리가 있어 직접 구현하지 않아도 된다. 자세한 내용은 깃 을 참고한다.

색인

색인할 때도 검색 키워드와 동일하게 edge_ngram 으로 토크나이징힌다.

PayloadTrie 를 사용하면 토큰이 매칭됐을 때 반환할 payload 도 같이 저장할 수 있다.

예시) 색인어가 ”철학자”라면, 철 혹은 철학 혹은 철학자 로 검색했을 때 철학자 가 반환되게 하는 것이다.

val trieBuilder = PayloadTrie.builder<String>()
keywords.forEach { keyword ->
    log.debug("색인할 단어: $keyword")
      trieBuilder.addKeyword(keyword)
    edgeNgramTokenizing(keyword).forEach { token ->
        log.debug("-- 토큰: $token")
      trieBuilder.addKeyword(token, keyword)
    }
}
trie = trieBuilder.build()

검색

val emits = trie.parseText(searchKeyword)

PayloadTrie.parseText() 를 호출하면 검색 결과가 반환된다. start, end position 같은 추가 정보도 제공한다.

엘라스틱서치 구현하기

색인

엘라스틱서치에서 제공하는 edge_ngram 토크나이저로 색인한다.

PUT autocomplete_elsboo
{
  "settings": {
    "analysis": {
      "analyzer": { "autocomplete": { "tokenizer": "edge_ngram" } },
      "tokenizer": { "edge_ngram": { "type": "edge_ngram", "max_gram": 10 } }
    }
  },
  "mappings": {
    "properties": { "keyword": { "type": "text", "analyzer": "autocomplete" }}
  }
}

검색

검색어는 이미 edge_ngram 으로 토크나이징 되어있으니 검색어 분석을 하지 않는 term query 를 사용하였다.

{
  "query": {
    "term": {
      "keyword": "%s"
    }
  }
}

결과

색인 키워드: 5543 개
Used Memory: 10 mb
[아호코라식] Indexing started...
[아호코라식] Index finished. Duration: 42 ms
[아호코라식] Perform started...
[아호코라식] Perform finished. Duration: 7 ms
Used Memory: 15 mb

Used Memory: 15 mb
[엘라스틱서치] Indexing started...
[엘라스틱서치] Index finished. Duration: 286 ms
[엘라스틱서치] Perform started...
[엘라스틱서치] Perform finished. Duration: 2051 ms
Used Memory: 17 mb

성능 측정에 관련된 코드는 여기에서 확인할 수 있다.

 

글 읽어주셔서 언제나 감사합니다. 좋은 피드백, 개선 피드백 너무나도 환영합니다.