SymSpell 알고리즘을 이용하여 한글 맞춤법 교정 적용해보기

회사 업무로 검색엔진 구축을 진행하면서 기획부터 검색 api 개발까지 많은 부분을 맡아서 하고 있다.
그 중 오타교정 api 를 만들 당시 SymSpell 알고리즘에 대해 알게 되었고 이 알고리즘을 활용하여 오타교정 api 1차 데모도 진행하였다.
최종적으로 이 알고리즘으로 오타교정을 구현하진 않았지만 SymSpell 알고리즘에 대해 정리해보고 오타교정 api 에서 어떻게 테스트를 했는지 기록해 보고자 한다.

오타교정

입력 중 발생하는 실수나 띄어쓰기 오류를 찾아서 적절한 단어로 교체하는 방법을 말한다.

Symspell 알고리즘은 오타 수정 및 철자 교정을 위한 알고리즘이다.
오늘은 파이썬에서 Symspell 알고리즘을 이용해서 한글 맞춤법 교정을 어떻게 적용했는지 알아보고자 한다.

편집거리 알고리즘이란?

먼저 편집거리 알고리즘을 알아보자.

편집거리란 두 문자열을 비교하는 방법 중 하나로 , 한 문자열 A를 다른 문자열 B로 바꾸기 위해서 몇 번의 편집을 거치는지를 수치로 나타내는 방식이다.

편집거리 중 레벤슈테인 편집거리는 세가지 연산으로 이루어진다

1. 삽입(insertion): 문자열에 새로운 문자를 삽입한다.

2. 삭제(delection) : 문자열에서 문자를 제거한다.

3. 교체(subsititution) : 문자열의 문자를 다른 문자로 대체한다.

예를 들어 문자열 apple이 있다면
1. 마지막 e를 빼서 appl을 만들면 appl은 apple의 deletion가 된다.
2. appl의 뒤에 y를 추가해서 apply는 appl의 insertion가 된다.
3. 이러면 apply와 apple의 편집 거리가 2인가? 싶지만 apple의 e를 y로 바꾸기만 하면(substitution) apply가 된다.
4. 따라서 편집 거리는 1이다.

이렇게 편집거리가 작은 두 문자열은 서로 유사한 문자열이라고 판단할 수 있다.
이 세가지 연산 중 SymSpell 알고리즘은 오직 deletion만 사용한다.

그럼 앞서 설명한 알고리즘을 토대로 맞춤법 교정에 관해 예시를 알아보자.

1. 한 어절을 입력받는다 → “안뇽하세요”
2. 맞춤법이 올바른지 확인한다. 단어 사전(vocabulary, dictionary) 안에서 “안뇽하세요” 라는 문자열이 없다는 것을 확인한다.
3. “안뇽하세요”와 가장 유사한 어절을 찾는다 → “안녕하세요” 발견
4. “안녕하세요”로 바꾼다.

예시에서 볼 수 있듯이 이렇게 맞춤법이 올바른지를 알기 위해서는 단어 사전을 구축해야한다.
우리는 현재 농업과 관련된 곳과 연계하여 일을 하고 있기 때문에 농업관련 데이터를 모아 명사 키워드를 추출한 키워드 사전을 만들었다.

생각보다 많은 데이터에서 명사가 아닌 키워드를 지워주는 수작업도 필요했다. 비록 우리가 만든 키워드 사전을 공개할 수는 없지만 공개된 맞춤법 파일도 있으니 테스트 할 시엔 이걸 사용하는 것도 좋을 것 같다 . (https://raw.githubusercontent.com/hermitdave/FrequencyWords/master/content/2018/ko/ko_50k.txt )

키워드 사전 형식은 이렇게 되어있다.

키워드, 빈도수

각 줄마다 키워드와 빈도수가 함께 있는데 편집거리가 동일한 경우 빈도수가 높은 키워드를 선택하기 위해 해당 형식으로 사용된다고 한다.

SymSpell 알고리즘이란?

이제 SymSpell 알고리즘에 대해 알아보자 .
SymSpell 알고리즘은 앞서 말한 것 처럼 오직 deletion 만 사용한다. (성능을 향상 시키기위해 불필요한 비교를 막기 위함이다)
제일 먼저 Symspell 알고리즘은 사전에 있는 단어의 deletion을 계산하고 자료 구조로 저장한다.
예를 들어 단어 apple과 apply가 있다면 이들의 편집거리가 1인 deletions는 appl, pply 등이 있을 것이다.
또한, 편집 거리가 2인 deletions에는 app, ppl 등이 있을 것이다.
이들과 원래 단어를 해시 테이블 같이 빠르게 찾을 수 있는 자료구조로 저장한다.

자세한 설명은 해당 글에 자세히 나와있다.
https://wolfgarbe.medium.com/1000x-faster-spelling-correction-algorithm-2012-8701fcd87a5f

SymSpell 알고리즘 사용하기

이제 SymSpell 알고리즘을 사용해보자

1.오픈소스 라이브러리를 사용하여서 pip 을 이용하여 설치한다.

pip install symspellpy

2.앞서 만든 키워드 사전을 불러와서 사전을 구축하고 lookup 메서드를 이용해서 유사 어절을 찾아주자.
Verbosity.ALL을 이용하여 가장 가까운 편집거리와 가장 큰 빈도수를 갖는 어절을 모두 반환하여 어떠한 키워드가 유사한지 알아보려고 ALL을 사용했다. 더 자세한 사용법은 API 문서를 참고하자.

from symspellpy import SymSpell,Verbosity
from hangul_utils import split_syllable_char, split_syllables, join_jamos

sym_spell = SymSpell(max_dictionary_edit_distance=1)  # max_dictonary_edit_distance => 편집 거리(값이 클 수록 실행 시간 늘어남)
dictionary_path = "jaso_correction_dictionary.txt"

sym_spell.load_dictionary(dictionary_path, term_index=0, count_index=1, separator=",", encoding='utf-8')

참고: https://symspellpy.readthedocs.io/en/latest/examples/index.html?source=post_page-----3def9ca00805--------------------------------

3.한글은 초성, 중성, 종성 세 종류의 자소로 구성되기 때문에 자소 단위로 분리 해주어야 정확한 오타교정이 가능하다.
한글 자소 분해를 위한 파이썬 라이브러리 hangul-utils를 사용하였다.
자소 분해를 한 단어를 이용하여 다시 Symspell을 사용하여 더 정확한 어절을 추천할 수 있게 되었다.

word = split_syllables(word)
corrections = sym_spell.lookup(word, Verbosity.ALL, max_edit_distance=1)
for corr in corrections:
    print(corr.term, join_jamos(corr.term), corr.distance, corr.count)
if corrections:
    corrected_word = join_jamos(corrections[0].term)
    word = corrected_word
    print(f"오타 교정 결과: {word}")
else:
    print("오타 교정 결과를 찾을 수 없습니다.")

비록 내부적인 이유로 Symspell 알고리즘을 쓰지 않게 되었지만 해당 알고리즘으로 이런저런 테스트를 하면서 한글 맞춤법이 어떻게 교정되는지 알 수 있었다.

이 알고리즘을 쓰지 않게 된 아쉬움이 다 없어지기전에 이 블로그에 글로 남기고자 한다.

참고:
https://americanopeople.tistory.com/349
https://heegyukim.medium.com/symspell%EC%9D%84-%EC%9D%B4%EC%9A%A9%ED%95%9C-%ED%95%9C%EA%B8%80-%EB%A7%9E%EC%B6%A4%EB%B2%95-%EA%B5%90%EC%A0%95-3def9ca00805