[ 대규모 서비스] [책] 7 장: 20강 하테나 다이어리의 키워드 링크

* 대규모 데이터를 대상으로 한 알고리즘 실용화에 관련된 예

- 키워드 링크

최초 구현 방식

1. 정규표현을 컴파일하는 처리

2. 정규표현에서 패턴을 매칭하는처리

 

문제점

데이터가 늘어날 수록 키워드의 개수가 증가 -> 키워드 캐수에 비례하는 계산량이 소요

 

해결방안

Tire(트라이)를 사용한 매칭 구현으로 변경

 

Tire? 선택

트리구조의 일조인 데이터 구조

• 탐색대상 데이터의 공통 접두사를 모아서 트리구조를 이루는게 그 특징
• 문자열 집합을 트리구조로 해서 효율적으로 저장

 

AC 법 - Tire에 의한 매칭을 더욱 빠르게하는 방법

Aho-Corasick(AC 법)

• Tire 에서의 패턴매칭으로 매칭이 진행되다가 도중에 실패했을 경우, 되돌아오는 길의 엣지를 다시 Tire에 추가한 데이터 구조를 사용하는 방법
• 계산량이 사전 크기에 의존하지 않는 빠른 방법
• 사전 내에서 패턴 매칭을 수행하는 오토마톤을 구축하고 입력 텍스트에 대해 선형 계산 시간을 실현

Regexp::List  로 변경

Perl 정규표현 라이브러리로 Tire에 의해 최적화된 정규표현으로 변환시키는 라이브러리

• 계산량이 줄어든다.
• 정규표현으로 사용할 수 있다.(유연성)

키워드 링크 구현, 변이 및 고찰 요약

변이: 정규표현 → AC 법 → Refexp::List

고찰

• 심플한 구현이 주효했지만, 데이터가 커지면서 계산량 문제가 발생
• 선택한 알고리즘의 근본적인 문제점을 해결하기 위하여 한 알고리즘 평가를 통해 계산량의 관점에서 문제를 해결

처음부터 최적의 구현을 사용하는 것이 반드시 옳지는 않다.

데이터가 대규모가 될 시기를 대비해서 본질적인 문제의 해결방법을 머릿속에 넣어두어야 한다.