맞춤법 교정 혹은 오타 교정이라고 부르는 방법은 입력 중 발생하는 실수나 띄어쓰기 오류를 찾아서 적절한 단어로 교체하는 방법을 말합니다. 스마트폰 키보드 상단이나 검색창, 워드프로세서에 뜨는 단어추천이 대표적인 예시입니다.
이 글에서는 symspell 알고리즘을 이용해서 파이썬으로 한글 맞춤법 교정을 하는 방법에 대해서 소개하려고 합니다. 먼저 편집 거리 알고리즘에 대해서 알아보겠습니다.
편집 거리(Edit Distance)
편집거리란 두 문자열을 비교하는 방법 중 하나로, 한 문자열 A를 다른 문자열 B로 바꾸기 위해선 몇 번의 편집을 거치는지를 수치로 나타내는 방식입니다. 여기서 편집이란 문자열의 문자를 추가(insertion), 삭제(deletion), 교체(substitution), 인접한 문자를 뒤바꾸기(transposition) 등 여러 방법이 있습니다.
예를 들어 문자열 apple이 있다면
- 마지막 e를 빼서 appl을 만들면 appl은 apple의 deletions가 됩니다.
- appl의 뒤에 y를 추가해서 apply는 appl의 insertions가 됩니다.
- 이러면 apply와 apple의 편집 거리가 2인가? 싶지만 apple의 e를 y로 바꾸기만 하면(substitution) apply가 됩니다. 따라서 편집 거리는 1입니다.
- 인접한 문자를 바꾸는 예시는 abc → acb 가 있습니다.
또 다른 예로 문자열 rear 와 rare를 보겠습니다. 이 두 문자열의 편집 거리는 아래와 같이 계산 가능합니다.
- e를 뺀 뒤(rar) 마지막에 e를 붙여서(rare) 총 2번의 편집을 거칩니다.
- 인접한 e와 a를 바꾸고(transpose, raer), 다시 e와 r을 바꿔서(rare) 총 2번의 편집을 거칩니다.
편집 거리를 구하는 알고리즘마다 사용하는 편집 방법이 다른데, Levenshtein 알고리즘은 insertion, deletion, substitution만 사용하고Damerau-Levenshtein 알고리즘은 거기에 tranposition를 추가로 사용합니다.
편집 거리가 작은 두 문자열은 서로 유사한 문자열이라고 판단할 수 있습니다. 이 알고리즘을 소개한 이유는 맞춤법 오류가 발생했을 때 이를 고치기 위해서 가장 유사한 단어를 추천해주기 위함입니다. 그렇다면 아래와 같은 알고리즘으로 우리는 맞춤법 교정을 할 수 있습니다.
- 한 어절을 입력받는다 → “안뇽하세요”
- 맞춤법이 올바른지 확인한다. 단어 사전(vocabulary, dictionary) 안에서 “안뇽하세요” 라는 문자열이 없다는 것을 확인한다.
- “안뇽하세요”와 가장 유사한 어절을 찾는다 → “안녕하세요” 발견
- “안녕하세요”로 바꾼다.
위 알고리즘을 보면 알 수 있듯 맞춤법 교정을 위해서는 사전이 먼저 구축돼야 합니다. 여기서는 공개된 파일을 사용하겠습니다
https://raw.githubusercontent.com/hermitdave/FrequencyWords/master/content/2018/ko/ko_50k.txt
이 데이터는 여러 텍스트 데이터셋에서 어절을 추출하고, 어절이 출현한 빈도수를 함께 저장한 파일입니다. 각 줄마다 어절과 빈도수가 함께 있는데, 편집 거리가 동일한 경우 빈도수가 높은 어절을 선택하기 위해서사용합니다. 예를 들어 appl과 가장 유사한 단어로 apple과 apply가 있을 때, 더 자주 등장하는 단어로 apple을 선택할 수 있다는 의미입니다.
이제 이런 식으로 일정 편집 거리 이내의 후보 단어들을 찾은 뒤, 최대 편집 거리(보통 오타가 편집 거리 2이내이기 때문에 2를 사용합니다) 내에서 가장 빈도수가 높은 문자열을 고르거나 편집 거리가 가장 작고 빈도수가 높은 문자열을 선택합니다.
Peter Norvig의 알고리즘
유사한 어절을 찾기 위해서는 사전에 등록된 모든 어절과 비교해보면 됩니다. 하지만 이는 지나치게 비효율적입니다. 예를 들어 위 파일에 있는 어절만 5만개입니다. 이들과 일일이 편집 거리를 비교한다면 성능 저하가 심할 것입니다. Peter Norvig의 알고리즘은 간단한 방법으로 성능을 향상시킬 수 있습니다.
코드는 굉장히 짧습니다. 방법을 요약하면 이렇습니다
- 문자열을 받습니다
- 문자열에서 임의의 문자를 더하거나, 빼거나, 바꿔보거나, 위치를 변경해서 새로운 문자열을 만듭니다. 그러면 편집 거리가 1인 새로운 문자열이 만들어집니다. 문자열이 appl 이라면 apply, apple, app 등의 문자열을 만듭니다
- 그 문자열이 사전에 있는지 확인합니다. 있다면 그 중에서 가장 빈도수가 높은 문자열을 선택합니다.
- 만약 편집 거리가 2인 문자열을 만들고 싶다면, 편집 거리가 1인 문자열들에 같은 연산을 반복하면 됩니다.
이러면 사전 내의 모든 문자열과 비교하는 것보다 빠르게 유사한 문자열을 찾아낼 수 있습니다. 하지만 여전히 단점은 존재합니다.
영어의 알파벳 개수가 26개인데, 이 경우 길이가 n인 단어가 주어지면 n deletions, n-1 transpositions, 26n substitutions, 26(n+1) insertions 모두 합쳐서 54n+25개의 문자열이 생성됩니다. 심한 경우 중국어처럼 한 문자가 수십 수백만개가 존재해서 심각한 성능 저하가 발생하게 됩니다.
SymSpell 알고리즘
SymsSpell 알고리즘은 Peter Norvig의 알고리즘의 이런 단점을 개선하고 성능을 향상시킨 알고리즘입니다. Symspell 알고리즘은 오직 deletions만을 사용합니다.
제일 먼저 Symspell 알고리즘은 사전에 있는 단어의 deletions를 계산하고 사전을 구축합니다. 예를 들어 단어 apple과 apply가 있다면 이들의 편집거리가 1인 deletions는 appl, pply 등이 있을 것입니다. 편집 거리가 2인 deletions에는 app, ppl 등이 있을 것입니다. 이들과 원래 단어를 해시 테이블 같이 빠르게 찾을 수 있는 자료구조로 저장합니다.
이후 원래 문자열 appl과 사전 내 단어의 deletions중 일치하는게 있는지 확인합니다. appl은 사전 내 apply와 apple의 deletions이기 때문에 두 단어를 후보에 추가합니다.
그 다음 원래 문자열 appl의 deletions인 app, ppl을 가져와서 사전에 등록된 문자열이 있는지 확인하고 후보에 추가합니다. 사전에 app이라는 문자열을 후보에 추가합니다. 위의 두 경우는 모두 편집거리가 1입니다.
마지막으로 사전 내 문자열 중에서 appl과 같은 deletions를 갖는 걸 찾습니다. 이 경우 일치하는 문자열의 편집 거리는 1 혹은 2일 수 있습니다.
- 편집 거리가 1인 예로는 appl과 appe 라는 문자열이 있습니다. 둘 다 공통 deletions로 app를 가집니다
- 편집 거리가 2인 예로는 appl과 bapp가 있습니다. 둘 다 공통 deletions로 app을 가지지만 편집 거리는 2입니다.
deletions와 매칭되는 원래 문자열 목록을 hash table로 구축한다면 매우 빠른 속도로 찾아낼 수 있습니다. 또한 deletions는 언어와 상관없이 문자열 길이 n-1개의 deletions만을 만들어내기 때문에 영어 기준 54n+25 개의 문자열을 만들어내는 Peter Norvig 알고리즘보다 훨씬 빠릅니다. 알고리즘 개발자의 측정에 따르면 천배나 빠르다고 합니다. 중국어처럼 문자가 아무리 많아도 Symspell 알고리즘은 제약이 없습니다. 문자를 바꾸거나 추가해서 후보 문자를 찾지 않기 때문입니다.
symspellpy를 사용하기
직접 구현하지 않고 오픈소스 라이브러리를 이용해서 사용해보도록 하겠습니다. 개발자는 C#으로 코드를 공개했는데 여러 언어로 포팅된 버전이 많습니다. 그중에서 symspellpy를 사용하게보겠습니다. 전체 코드는 아래 코랩 노트북에 있습니다.
먼저 pip로 설치한 후 사용합니다. 또한 위에서 말한대로 공개된 한글 어절 빈도수 데이터를 가져옵니다. load_dictionary 메서드를 이용하여 빈도수 데이터를 불러와서 사전을 구축하고, lookup 메서드를 이용해서 유사 어절을 찾습니다.
두번째 인자인 Verbosity에는 가장 가까운 편집 거리와 가장 큰 빈도수를 갖는 어절을 반환해주는 Verbosity.CLOSEST와 max_edit_distance 내에서 가장 빈도수가 높은 어절을 반환하게 해주는 Verbosity.TOP, max_edit_distance 내의 모든 후보를 반환해주는 Verbosity.ALL이 있습니다. 반환 타입인 SuggestionItem 클래스는 원래 단어인 term, 편집 거리인 distance, 빈도수인 count 3개의 속성을 갖습니다. 더 자세한 사용법은 API 문서를 참고해주세요.
하지만 위 결과에서 보듯 안녕하세요와 안심하세요가 같은 편집 거리인 1을 갖습니다. 자소단위로 분해하지 않고 완성된 문자를 1개의 문자로 취급하기 때문입니다. 만약 자소단위로 편집 거리를 계산했다면, `뇽`과 `심`의 편집 거리는 초성 중성 종성 모두 다르기에 3으로 계산될 것이고, `뇽`과 `녕`의 차이는 중성의 차이만 있기 때문에 1로 계산되어 `안녕하세요`가 더 작은 편집 거리를 갖게될 것 입니다.
한글에 적용하기
즉 한글은 한 글자가 초성, 중성, 종성 세 종류의 자소로 구성되기 때문에 자소단위로 텍스트를 나눠주어야만 보다 정확한 오타교정이 가능합니다. 한글 자소 분해를 위한 여러 파이썬 라이브러리가 있는데 여기서는 hangul-utils를 사용해 보겠습니다.
pandas를 이용해서 빈도수 파일을 DataFrame으로 불러온 뒤, hangul_utils 패키지의 split_syllables 함수를 이용하여 자모 단위로 분해한 뒤 다른 파일로 저장합니다. “내가” →“ㄴㅐㄱㅏ” 이런 식으로 분해된 모습을 볼 수 있습니다. 이제 자소단위로 구축된 이 사전을 이용해서 다시 SymSpell을 사용해보겠습니다.
이제 lookup 메서드를 사용할 때는 자소단위로 분해해서 줘야합니다. 분해한 단어를 다시 조립할 때는 join_jamos 함수를 사용합니다. 이제는 “안심하세요”, “하세요” 같은 어절은 이전보다 훨씬 큰 edit distance를 갖고, 원래의 의도대로 “안녕하세요”라는 더 정확한 어절을 추천해줄 수 있게 됩니다.
다음 글에서는 Symspellpy를 이용해서 띄어쓰기와 오타교정을 한번에 하는 방법에 대해서 알아보겠습니다.
