Skip to content

[algorithm] structural pattern matching

Jump to bottom
Myungchul Shin edited this page Jun 7, 2016 · 9 revisions

Naive Approach

  • 형태소, 태그, 기타 정보를 가진 구조체의 리스트(혹은 배열)가 형태소분석결과라고 가정한다.
  • 이 데이터 위에서 특정 패턴매칭을 수행하려면 어떻게 해야할까?
    • 예를 들면, 패턴이 매칭되면 해당 구조체 영역을 하나로 병합한다던가(merge)
    • 아니면 특정 output을 출력한다던가
  • 패턴(혹은 rule)의 형태는 아래와 같다
-2  -1   0
끈   *   잇다
NNG JKO  VV

=> 현재 위치에 '잇다'가 있고 앞쪽에 '끈,을'이 있으면 매칭하겠다는 의미
   특정 action이 기술될수도 있다. '*'는 모두 가능하다는 의미
  • 현재 위치를 표시하는 '0'에 해당하는 형태소를 key라고 하고 나머지를 context라고 하자.
  • 아주 나이브한 매칭 방법은 분석결과를 스캔하면서 key가 있는지 탐색하고 있다면 해당 key를 가진 rule들을 가지고 매칭시켜보는 방법이다.
예를 들어서 분석결과가 아래와 같다고 하자. 

-2  -1   0
끈   이   잇다
NNG  JKS VV

분석결과를 스캔하다가 '잇다'를 만나면 '잇다'에 기술된 context에 맞춰서 비교 데이터를 생성한다. 
즉, '끈_NNG/*_JKS'
(context에 있는 *는 모두 가능하다는 의미이므로 비교 데이터를 생성할때도 그렇게 한다)
그리고 이 값을 패턴의 context('끈_NNG/*_JKO')와 비교한다. 
비교 결과 다르므로 매칭은 실패한다. 
만약 '잇다'에 대해서 또 다른 context가 존재한다면 그것에 맞춰서 비교 데이터를 다시 생성하고
비교를 계속해 나간다. 모든 context에 대해서 매칭이 실패하면 '실패'.
중간에 하나라도 매칭이 성공하면 '성공'으로 판단한다. 
여기서 중요한 포인트는 '잇다'의 context를 길이의 내림차순으로 정렬해서
가장 긴 것부터 비교해야한다는 것이다.(longest context matching)
그리고 같은 길이인 경우에는 태그보다는 형태소 매칭을 우선한다던가 하는 
우선순위를 두고 정렬해둬야 한다는 점도 주의하자. 

비교 데이터를 생성할때는 버퍼에 strcat()으로 복사하면서 생성하는 방법도 있고
분석결과 구조체와 동일한 비교 구조체를 하나 두고 pointer만 할당한 다음
비교하는 방법이 있을 수 있다. 

또한 비교 구조체를 사용하는 경우에는 현재 '0'의 위치에서 가까운 순으로 비교해가는 방법이 효율적이므로
비교 순번을 정해서 비교해 가는 것이 좋다. 

0   1   2   3 ....
-1  1   -2  2 ....

물론, context가 앞쪽(-)에만 존재하거나 뒤쪽(+)에만 존재할 수도 있는데, 특정 순번에 비교할 context가 
없는 경우는 그냥 skip하도록 flag를 두면 될 것이다. 
context는 사실 그렇기 길지 않으므로 비교 구조체는 적정한 사이즈(예를 들면, 16)로 할당해서 사용한다.
  • 위와 같은 방법은 rule의 수가 적당한 경우에는 제법 효율적으로 동작한다.
  • 하지만, 같은 key를 갖는 context는 매우 많을 수도 있다.
  • 이런 상황에서 효율적인 매칭을 하려면 어떻게 해야할까?
    • 예를 들면, '잇다'의 context는 10000건이 넘는다.
    • 최악의 경우는 비교 구조체를 10000건 이상 만들고 비교할수도 있다.
  • 간단한 방법은 '잇다'를 key로 사용하는 것이 아니라 '잇다'와 -1 위치의 태그 혹은 +1 위치의 태그를 함께 key로 사용하는 것이다.
    • 이런 방법은 그렇게 아름답지는 않으니 key에 해당하는 context를 가져올 때 context들을 -1/+1의 태그를 가지고 분기시키는 방법을 사용하자.
    • 이렇게 분기하는 방법을 사용해서 비교 대상을 절반이상으로 줄일 수도 있다.
    • 물론 최악의 경우는 -1/+1 태그까지 전부 똑같아서 분기가 안되는 경우도 있을 수 있다.
    • 좀더 일반화 시킨다면 현재 분석결과 구조체에 대해서 아래와 같이 탐색 공간을 줄일 수 있는 방법이 있다면 더 좋을 것이다.
    (-) 방향으로 가면서 context 중 비교대상을 좁힌다.
(+) 방향으로 가면서 context 중 비교대상을 좁힌다.

Advanced Approach

- rule
-2  -1   0
끈   *   잇다
*   JKO  VV

- 위와 같은 rule이 있을 때, 이것을 fst로 표현한다. 

0 -> 현재/형태소/잇다 -> 1 -> 왼쪽/태그/JKO -> 2
  -> 왼쪽/형태소/끈 -> 3
3 : final state

- 임의의 형태소 분석 결과에 대해서 fst를 이용해서 탐색한다. 
  즉, 형태소 분석이 '끈/NNG 을/JKO 잇다/VV'인 경우
  현재 위치에서 만들 수 있는 가능한 조합을
  '현재/형태소/끝', '현재/태그/NNG', '현재/어절/끝을'
  fst에 입력해서 상태전이를 따라간다. 없으면 다음 형태소에 대해서 진행하다가
  '현재/형태소/잇다'에 대해서 적용해보면 final state로 가게 되는데, 
  이때 어떤 action을 취하게 하면 된다.
Clone this wiki locally