How to write a spelling corrector

이번 포스팅에서는 Peter Norving의 spelling corrector가 어떻게 작동하는지에 대해 포스팅을 진행해 보도록하겠습니다.

Spelling Correcter의 확률적 이론

Call correction(w)은 w에 대해 가장 가능성이 높은 맞춤법 수정을 선택하려고 시도합니다. 하지만 확실히 알 수 있는 방법은 없습니다. 예를들어, "late"를 "late", "latest" 또는 "lattes"으로 수정해야 하기때문입니다. 따라서 가능한 모든 후보 중에서 원래 단어 w가 주어졌을 때 c가 의도한 수정일 확률을 최대화하는 수정 c를 찾으려고 합니다.

 

Bayes정리에 따르면 아래와 같이 표현할 수 있습니다.

 

또한, P(w)는 모든 가능한 후보 c에 대해 동일하므로 아래와 같이 인수분해할 수 있습니다.

 

Spelling Correcter의 특징

• Selection Mechanism: argmax :
  • 결합 확률이 가장 높은 후보를 선택합니다.
• Candidate Model: c ∈ candidates
  • 고려할 c를 알려줍니다. 즉 단어에 대한 간단한 편집은 삭제(한 문자 제거), 전치(인접한 두 문자 교환), 대체(한 문자를 다른 문자로 변경) 또는 삽입(문자 추가)입니다. edits1 함수는 한 번의 간단한 편집으로 만들 수 있는 모든 편집된 문자열(단어이든 아니든) 집합을 반환합니다. 이러한 집합은 큰 세트가 될 수 있는데, 길이가 n인 단어의 경우 n개의 삭제, n-1개의 전치, 26n개의 변경 및 26(n+1)개의 삽입이 발생하여 총 54n+25개가 됩니다.
• Language Model: P(c)
  • c가 영어 텍스트의 단어로 나타날 확률. 예를 들어 ""의 출현은 영어 텍스트의 약 7%를 구성하므로 P(the) = 0.07이어야 합니다. 더나아가, 각 단어가 약 백만 단어의 텍스트 파일인 big.txt에 나타나는 횟수를 세어 단어 P(단어)의 확률을 추정할 수 있어야합니다. 단어 기능은 텍스트를 단어로 나눈 다음 변수 WORDS는 각 단어가 나타나는 빈도에 대한 카운터를 보유하고 P는 이 카운터를 기반으로 각 단어의 확률을 추정합니다.
• Error Model: P(w|c)
  • c를 의미할 때 w가 텍스트에 입력될 확률. 예를 들어, P(teh|the)는 상대적으로 높지만 P(theeexyz|)는 매우 낮게됩니다.

Spelling Correcter의  소스코드

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)

해당 correcter는 인풋에따라 아래와 같이 글자를 수정해 줍니다.

>>> correction('speling')
'spelling'

>>> correction('korrectud')
'corrected'