Peter Norvig’s 알고리즘 살펴보기

Peter Norvig’s은 대표적인 오타교정 알고리즘이다.

피터노빙 알고리즘을 사용하면 오탈자 키워드가 Input 값으로 주어졌을 때, 해당 오타 키워드를 교정한 단어를 Output으로 주는 함수를 만들 수 있다.

동작 원리

첫번째 단계 : 단어 사전 구축 하기 

1. 교정 사전으로 활용할 텍스트 파일을 준비한다.

2. 텍스트 파일에서 단어와 언급수를 계산해둔다.

   단어가 언급된 수는 오타 교정 후보 단어가 여러개 나온 경우, 교정 단어의 우선순위를 정할때 사용한다.

두번째 단계 : 키워드 교정하기 

1. 검색 키워드를 오타교정 함수에 전달한다.

2. 단어 사전에 있는 키워드인 경우, 그대로 키워드를 반환한다. 

   이 경우, 검색 키워드가 표준어라고 볼 수 있기 때문이다. 

3. 단어사전에서 키워드를 찾지 못한 경우, 3번째 교정 단계를 거친다.

    검색 키워드의 편집거리가 1인 키워드 목록을 만든다. 그리고 이 키워드가 단어사전에 있는지 확인한다. 

   단어 사전에 포함되어있는 경우, 해당 단어를 반환한다.

4. 편집거리 1인 키워드 목록에서도 표준 단어를 찾지 못하는 경우, 4번째 교정 단계를 거친다. 

   편집거리가 2인 키워드 목록을 구한 후, 3번째 단계와 동일하게 단어 사전을 찾는다. 

5. 만약 4번째 단계에서도 단어를 찾지 못한다면, 원본 키워드를 반환한다

 

편집 키워드 목록 구하기 

편집거리, 편집단어 등으로 의역하니 좀 어색하다. 여기서 편집이란, 영어로는 edit을 의미한다. 즉, 문자를 변경한 단어라는거다. 

피터 노빙 알고리즘에서는 edit word를 구하기위해 총 4개의 문자 수정 (deletes, transposes + replaces + inserts) 과정을 거친다.

 

예를 들어, americano라는 키워드의 문자를 변형한 예시는 다음과 같다. 

1. deletes: americano -> mericano, aericano, amricano..

2. transposes: americano-> maericano, aemricano..

3. replaces : americano -> abericano, acericano

4. inserts : americano -> abmericano, acmericano

 

코드

알고리즘 원본 코드는 다음과 같다.

import re
from collections import Counter

def words(text): return re.findall(r'\w+', text.lower())

WORDS = Counter(words(open('big.txt').read()))

def P(word, N=sum(WORDS.values())): 
    "Probability of `word`."
    return WORDS[word] / N

def correction(word): 
    "Most probable spelling correction for word."
    return max(candidates(word), key=P)

def candidates(word): 
    "Generate possible spelling corrections for word."
    return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

def known(words): 
    "The subset of `words` that appear in the dictionary of WORDS."
    return set(w for w in words if w in WORDS)

def edits1(word):
    "All edits that are one edit away from `word`."
    letters    = 'abcdefghijklmnopqrstuvwxyz'
    splits     = [(word[:i], word[i:])    for i in range(len(word) + 1)]
    deletes    = [L + R[1:]               for L, R in splits if R]
    transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
    replaces   = [L + c + R[1:]           for L, R in splits if R for c in letters]
    inserts    = [L + c + R               for L, R in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

def edits2(word): 
    "All edits that are two edits away from `word`."
    return (e2 for e1 in edits1(word) for e2 in edits1(e1))

 

마무리

피터노빙의 알고리즘은 편집단어를 구하는 데에 많은 연산 비용이 든다. 그래서 라이브환경에 바로 적용하기 어렵고, 중국어처럼 복잡한 언어에 적용할 수 없단 한계점이 있다. 때문에 delete 편집 방식을 활용한 symspell 알고리즘이 오타교정 알고리즘으로 활용되기도 한다. 

 

참고

https://norvig.com/spell-correct.html