[아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (2) - 데이터 구축

이전 글에서는 아호코라식 알고리즘의 검색 과정에 대해서 알아보았다.

[아호코라식 (Aho-corasick) 알고리즘] 논문 이해하기 (1) - 검색 과정

이번 글에서는 아호코라식이 구성하는 세 개 함수 goto(), output() , failure() 의 데이터를 구축하는 법에 대해 알아보자

함수 데이터는 어떻게 만들까?

goto()

검색 대상 단어들 [he, she, his, hers] 을 Trie 자료구조로 표현하는 게 목표이다.

문자 하나를 간선(-), 문자의 state 를 정점(○)으로 표현하면 아래와 같이 그릴 수 있다.

① he (he, she, his, hers)

state 는 0 부터 시작해서 1씩 증가한다.

② she (he, she, his, hers)

state 0 에서 시작하는 길이 h 밖에 없으므로 s 로 시작하는 라인을 추가한다.

③ his (he, she, his, hers)

state 0 에서 h 로 시작하는 간선이 이미 있다. state 1 에 이어서 다음 i, s 를 추가한다.

④ hers (he, she, his, hers)

h, e 까지 이어진 라인이 이미 있으므로 state 2 뒤에 r, s 를 추가해 마무리 해준다.

output()

output() 은 goto() 를 생성하는 시점에 생성한다. 한 검색 대상 단어 구축이 끝나는 시점에 마지막 state 값으로 매핑해준다.

논문에 나온 goto(), output() 구현 로직을 첨부한다.

Algorithm 2. Construction of the goto function.

Input. Set of keywords K = {Yl, Y2 ..... Yk}.

Output. Goto function g and a partially computed output function output.

Method. We assume output(s) is empty when state s is first
created, and g(s, a) = fail if a is undefined or if g(s, a) has
not yet been defined. The procedure enter(y) inserts into
the goto graph a path that spells out y.

begin
  newstate ← 0
  for i ← 1 until k do enter(Yi)
  for all a such that g(O, a) = fail do g(O, a) ← 0
end

procedure enter(a1 a2 • • • am):
begin
  state ← 0; j ← 1
  while g(state, aj ) ≠ fail do
    begin
      state ← g(state, aj)
      j ← j+l
    end
  for p ← j until m do
    begin
      newstate ← newstate + 1
      g(state, ap) ← newstate
      state ← newstate
    end
  output(state) ← {a1 a2 ...am}
  end

failure()

failure() 의 역할은 어떤 state 에서 검색어 문자와 다르거나 마지막 state 라 더 이상 탐색할 수 없을 때 어디 state 로 갈 수 있을지 알려준다. output을 만드는 규칙은 간단하다. 세로 라인을 같은 Depth 라고 할 때, 이전 Depth 중에서 똑같은 문자를 가진 state 값을 고르면 된다.

failure() 은 key 가 state 므로 state 기준으로 돌아보자.

① state 1, state 3

설명의 편의를 위해 state 1 의 h 를 [1]h 로 표현하겠다.

[1]h, [3]s 는 애초에 1 Depth 므로 이전 Depth 가 없다. 그래서 둘 다 output 은 0 이다.

② state 2

[2]e 의 output 을 찾기 위해 1 Depth 를 살펴보았으나 e 가 없다. 그래서 output 은 0 이다.

③ state 4

[4]h 는 2 Depth 이다. 1 Depth 중에서 h 를 찾아보니 존재한다! 그러므로 output 은 1 Depth h 의 state 값인 1 이다.

④ state 5

[5]e 는 3 Depth 이다. 2 Depth 이하 중에서 e 가 존재한다. 그러므로 output 은 2 Depth e 의 state 값인 2 다.

state 6 ~ 8 은 위의 방법들과 동일하므로 생략한다.

⑤ state 9

[9]s 의 선택지는 [3]s, [7]s 2개가 있는데, 이런 경우 가장 처음 Depth 인 값을 골라준다. 그러므로 output 은 3 이다.

논문에 나온 failure() 구현 로직을 첨부한다.

Algorithm 3. Construction of the failure function.

Input. Goto function g and output function output from Algorithm 2.

Output. Failure function fand output function output.

Method.

begin
    queue ← empty
    for each a such that g(O, a) = s ≠ 0 do
      begin
        queue ← queue U {s}
        f(s) ← 0
      end
    while queue ≠ empty do
      begin
        let r be the next state in queue
        queue ← queue - {r}
        for each a such that g(r, a) = s ≠ fail do
          begin
            queue ← queue U {s}
            state ← f(r)
            while g (state, a) = fail do state ← f(state)
            f(s) ← g(state, a)
            output(s) ← output(s) U output(f(s))
          end
      end
end

 

아호코라식 알고리즘에 대해 더 자세한 내용을 알고싶다면 아래 레퍼런스를 클릭해 논문을 읽어보는 것을 추천한다.

레퍼런스

http://cr.yp.to/bib/1975/aho.pdf

 

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