Porter Stemmer(포터 스테머)를 만들어보자!

 

영어 자연어처리를 위한 전처리 과정에서는 동사의 어간을 추출하기 위한 'stemming' 과정이 포함되기도 합니다. 

영어는 굴절어로 분류되며, 그 특징을 동사에서 발견할 수 있습니다. 물론 명사나 형용사에서 나타나는 접사들의 결합 여기에 포함될 수 있습니다.

 

동사의 경우만 살펴보자면, 예를 들어, say, says, saying, said는 say가 문장의 시제나 상(aspect), 태(voice)를 나타내기 위해 굴절이 일어난 형태입니다. 말뭉치(corpus) 내에서 통계를 분석할 때, 필요에 따라 이들은 모두 같은 단어인 'say'가 굴절한 형태로 보고 통계 수치가 측정되어야 할 것입니다. 이를 위해서 굴절 어미인, -s, -ing, -(e)d 등을 제거하여 say(sai)와 같은 어간(stem)만을 추출해내기 위한 도구가 바로 Stemmer입니다. 통계 분석 뿐만 아니라, 분리된 어간에 다른 형태의 어미를 결합하여 단어를 생성해낼 수도 있습니다. 

 

그러나 어간으로도 원래 굴절 이전의 단어를 추출하는 데 어려움이 있을 수 있습니다. 어간이 변형되기도 하기 때문입니다. 앞서 언급한 'said' 같은 경우가 이에 해당합니다. 굴절이 일어나기 이전의 어휘를 'lemma'라고 하며 lemma로 복원하는 작업을 lemmatization이라 합니다. 이에 관해선 이후에 기회가 된다면 다루도록 하겠습니다.

 

그 중 가장 유명한 Stemmer가 바로 1980년도에 Porter 씨가 제안한 Porter Stemmer라 합니다.

다양한 프로그래밍 언어의 여러 버전으로 무료 배포되고 있으며, 아래 사이트에서 그 정보를 확인하고자 합니다.

 

tartarus.org/martin/PorterStemmer/

Porter Stemming Algorithm

NLTK의 Porter Stemmer

Porter stemmer는 자연어 처리 라이브러리인 NLTK에서 제공됩니다. 이 외에 다른 stemmer도 제공됩니다.

import nltk
nltk.download()

from nltk.stem import LancasterStemmer, PorterStemmer, RegexpStemmer, RSLPStemmer 
stemmer = PorterStemmer()
stemmer.stem('saying')

## output: say ##

 

 

본문에서는 Python의 정규표현식을 이용해 Porter Stemmer의 일부를 만들어보고 적용해보고자 합니다.

Porter Stemmer의 원리는 아래 글에서 확인할 수 있습니다. 본문도 이 글을 참조했습니다.

 

M.F.Porter, (1980). "An algorithm for suffix stripping" 

 

본문에서는 굴절 어미 즉, 앞서 설명한 영어에서 동사의 시제, 태, 상을 표현하는 어미들에 대한 stemming에 대해서 다루고자 합니다. 

 

이외에 파생 어미에 대한 Stemming도 제공하지만, 애초에 파생 어미는 품사가 바뀌기에 다른 단어라 생각하여 제외하였습니다. 그러나 이 역시 같은 원리로 코드를 작성할 수 있을 것이라 생각합니다.

 

Porter Stemmer는 총 5단계로 구성되어 있는데, 이 중 1단계가 복수형 접사와 굴절 어미 분리에 관한 내용입니다. 이를 구현해보도록 하겠습니다. 

 

1단계는 다시 1a, 1b, 1c로 세분화되어 있습니다. 각 세부 단계 내에서도 여러 규칙들이 있고 그 순서가 정해져있습니다. 

순서에 맞게 규칙을 적용해야 원하는 결과를 얻을 수 있습니다. 

 

Porter Stemmer의 python 버전에서 사용된 방식과 다르게 정규표현식을 이용하였습니다. 따라서 적용 과정에서 변형이 있을 수 있습니다. 

 

사용된 개념 정리

 

알고리즘을 설명하기에 앞서, 전제된 개념들에 대해 살펴보겠습니다. 

 

영어의 알파벳을 자음(Consonants), 모음(Vowels)으로 구분하였으며, 모음을 a, e, i, o, u로, 자음을 a, e, i, o, u 외의 알파벳으로 구성하였습니다. 그리고 하나 이상의 자음 연쇄를 C, 하나 이상의 모음 연쇄를 V라 칭합니다.

 

단어에서 나타나는 영어 알파벳의 패턴을 다음과 같이 단순화 시킬 수 있다고 합니다. 

 

(C)(VC)^m(V)

 

즉, 선택적인 자음 연쇄 이후 VC가 m만큼 반복되고, 모음 연쇄가 선택적으로 나타날 수 있는 형태입니다. 

 

알고리즘의 수식 구조는 아래와 같습니다. 

 

(condition) S1 -> S2

 

어간에 대한 조건(condition)이 주어지고(없을 수도 있음), S1은 식이 적용되기 이전의 접미사(suffix), S2는 식이 적용된 이후의 접미사를 의미합니다.

 

조건(condition)의 종류는 다음과 같습니다. 

 

1. (m > 0): 앞서 설명한 식"(C)(VC)^m(V)"에서 m이 0보다 크다는 뜻. 즉, win은 VC(in)가 하나 들어가 있기에 이를 만족하지만, free는 VC 조합이 없기에 이 조건을 만족하지 않습니다. 

 

2. *S: S로 끝나는 어간, S 대신 다른 대문자 알파벳이 쓰일 수 있습니다. 

 

3. *v*: 모음을 포함하는 어간

 

4. *d: 이중 자음으로 끝나는 어간 (-tt-, -ss- 등)

 

5. *o: cvc로 끝나되, 두번째 나타나는 c(자음)가 W, X, Z가 아닌 형태

 

위 조건들을 바탕으로 1단계의 식들을 살펴보겠습니다. 

 

실제 코드 작성해보기

 

1a 단계

Porter의 논문에서 나타난 1a 단계에서 제안된 패턴은 아래와 같습니다. 

 

SSES -> SS
IES -> I
SS -> SS
S ->

 

1a는 조건이 따로 없으며, 위 식들이 적용됩니다. 

이 패턴을 인식하기 위해 작성된 정규 표현식은 아래와 같습니다. 

##step_1a

step_1a_before_list = [r'(?:^|\s)([A-Za-z]+?)sses(?:\s|$)', \
                        r'(?:^|\s)([A-Za-z]+?)ies', \
                        r'(?:^|\s)([A-Za-z]+?)ss(?:\s|$)', \
                        r'(?:^|\s)([A-Za-z]+?[^s])s(?:\s|$)']
step_1a_after_list = [r' /\1ss/ ', r' /\1i/ ', r' /\1ss/ ', r' /\1/ '] ## //로 두번 적용을 막음

 

step_1a_before_list는 식이 적용되기 이전의 패턴을 잡아내기 위함이고, step_1a_after_list는 step_1a_before_list에서 잡아낸 패턴을 변환하기 위한 패턴들입니다. \1을 통해 ( )안에 포함된 패턴을 재참조 하였습니다.

 

각 정규표현식에 대해 간단히 설명하자면, 우선 (?:^|\s), (?:\s|$)는 어절 단위를 제한하기 위함입니다. ([A-Za-z]+?)는 뒤의 식과 함께 어간을 잡아내기 위해 쓰인 표현입니다. 4번째 식에서는 어간 표현식 내에 [^s]가 들어갔는데, 이는 3번째 식에서 잡힌 ss 패턴 외의 대상들에 대해 적용하기 위해 넣어주었습니다.

즉, 예를 들어 confess가 3번째 식에만 적용되고, 4번째 식에는 적용되지 않도록 하기 위함입니다.

 

step_1a_after_list 에서는 '/ /' 로 앞 뒤에 달아주었는데, 여기서 적용된 단어들이 이후 식들에서 적용되지 않도록 하기 위해 표지를 추가하였습니다.

 

1b-1 단계 (적용의 구분을 위해 1b 단계를 2단계로 다시 나누었습니다.)

 

(m>0) EED -> EE

(*v*) ED ->

(*v*) ING ->

 

1b-2 단계 (적용의 구분을 위해 1b 단계를 2단계로 다시 나누었습니다.)

 

AT -> ATE

BL -> BLE

IZ -> IZE siz(ed) -> size

(*d and not (*L or *S or *Z)) -> single letter. ex: ff -> f

(m=1 and *o) -> E

 

이를 반영한 코드는 아래와 같습니다. 

##step_1b

step_1b_before_list = [r'(?:^|\s)([A-Za-z]*?[aeiou][b-df-hj-np-tv-z][A-Za-z]*?)eed(?:\s|$)', \
                        r'(?:^|\s)([A-Za-z]*?[aeiou][A-Za-z]*?[^e])ed(?:\s|$)', \
                        r'(?:^|\s)([A-Za-z]*?[aeiou][A-Za-z]*?)ing(?:\s|$)']
step_1b_after_list = [r' /\1ee/ ', r' \1 ', r' \1 ']


step_1b_before_list2 = [r'(?:^|\s)([A-Za-z]+?)at(?:\s|$)', \
                         r'(?:^|\s)([A-Za-z]+?)bl(?:\s|$)', \
                         r'(?:^|\s)([A-Za-z]+?)iz(?:\s|$)', \
                        r'(?:^|\s)([A-Za-z]+?)([a-km-rt-y])\2(?:\s|$)', \
                        r'(?:^|\s)([b-df-hj-np-tv-z]+[aeiou][b-df-hj-np-tvz])(?:\s|$)']
step_1b_after_list2 = [r' /\1ate/ ', r' /\1ble/ ', r' /\1ize/ ', r' /\1\2/ ', r' /\1e/ ']

[aeiou]: 모음 1개

 

[b-df-hj-np-tv-z]: 자음 1개, [v-z]는 [vwxyz]와 같습니다. 알파벳 순서만 맞으면 맨 처음과 마지막 알파벳만 남기고 '-'로 연결하여 식을 쓸 수 있습니다.

 

(*v*) 조건은 ([A-Za-z]*?[aeiou][A-Za-z]*?)로 구성하였습니다. 모음이 중간에 오고 앞, 뒤로 선택적으로 어떤 알파벳이든 반복적으로 나올 수 있게하였으며, ?를 붙여 non-greedy하게 구성하였습니다.

 

(m>0) 조건은 위의 (*v*)조건에 c가 올수 있도록 하여 (*vc*)처럼 구성되도록 하였습니다. 즉, vc가 하나라도 나타나면 조건을 만족시킨다고 보았습니다. 

 

(*d and not (*L or *S or *Z)) 조건은 ([a-km-rt-y])\2 로 ([a-km-rt-y])이 반복되는 패턴(자음 중, l, s, z를 제외)으로 구성되도록 하였습니다. 

 

(m=1 and *o) 조건은 ([b-df-hj-np-tv-z]+[aeiou][b-df-hj-np-tvz])로 CVC 인데 vc가 하나만 반복되는 형태로 나타나도록 했습니다. 즉, c(1개이상)vc 조합으로 나타나는 걸 잡아내도록 하였습니다. 

 

step_1b_after_list1에서는 '/ /' 표지가 나타나지 않았는데 step_1b_after_list2에서는 나타난 건 1b-1에서 적용된 후, 1b-2에서 한번 더 적용되어 stemming이 완료되도록 만들기 위함입니다.

 

 

1c 단계

 

(*v*) Y -> I

##step_1c

step_1c_before_list = [r'(?:^|\s)([A-Za-z]*?[aeiou][A-Za-z]*?)y(?:\s|$)']
step_1c_after_list = [r' /\1i/ ']

 

전체 step pipeline

#step pipeline
test_case = 'caresses ponies ties caress cats feed agreed plastered bled motoring  sing conflated troubled sized hopping tanned falling hissing fizzed failing  filing happy sky'
test_case = '  '.join(test_case.split())

data = '  '.join(data.split())

def porter_stemmer(tokens):
    for i in range(len(step_1a_before_list)):
        tokens = re.sub(step_1a_before_list[i], step_1a_after_list[i], tokens)
        print(i, tokens)
    print()
    for i in range(len(step_1b_before_list)):
        tokens = re.sub(step_1b_before_list[i], step_1b_after_list[i], tokens)
        print(i, tokens)
    print()
    for i in range(len(step_1b_before_list2)):
        tokens = re.sub(step_1b_before_list2[i], step_1b_after_list2[i], tokens)
        print(i, tokens)
    print()

    for i in range(len(step_1c_before_list)):
        tokens = re.sub(step_1c_before_list[i], step_1c_after_list[i], tokens)
        print(i, tokens)
    print()

    tokens = re.sub('\s{2,}', ' ', tokens)
    return tokens

test_case = porter_stemmer(test_case)
print(test_case)

## output ##
## /caress/ /poni/ /ti/ /caress/ /cat/ feed /agree/ plaster /blede/ motor sing /conflate/ /trouble/ /size/ /hop/ /tan/ fall hiss fizz fail /file/ /happi/ sky

test_case는 논문에서 사용된 예시들을 사용했습니다. 정규표현식을 연습하기 좋은 예제라 생각됩니다.

 

Stemmer의 적용결과는 이후에 후처리를 통해 보완될 수 있으며, lemmatizer처럼 lemma 형태로 바꾸는 과정도 적용이 가능할 것이라 생각됩니다.

 

참고문헌

M.F.Porter, (1980). "An algorithm for suffix stripping"