Symspell 알고리즘 살펴보기

Symspell은 "오타교정", "유사검색어 제안" 기능에서 활용되는 알고리즘이다. 

Peter Norving도 오타교정에서 유명한 알고리즘이다. 그러나 연산비용이 높기 중국어 같은 언어에서는 활용할 수 없다는 한계점이 있다. ( 글자를 표현하는 유니코드의 종류가 다양하기 때문에 후보군을 모두 계산하기 어렵다. )

Symspell 알고리즘은 Peter Norving 알고리즘의 단점을 보강한 알고리즘이다. 그래서 Peter Norving에 비하여 빠르고, 여러 자연어에서도 활용할 수 있단 장점이 있다. 

 

Symspell은 두가지 접근방법 덕분에 연산 비용을 줄이고, 속도를 개선할 수 있었다. 

• 오타 후보군을 사전에 계산하기
• DELETE 방식으로만 후보군 계산하기 

 

오타 후보군을 사전에 계산하기

symspell은 오타교정 함수를 실행하기 전에 미리 단어사전 파일을 읽고, delete 후보군을 계산한다.

peternorving 알고리즘은 입력 키워드의 후보군을 계산한다. 그리고 이 후보군이 단어 사전에 있는지를 확인한다.

반면, symspell은 단어 사전의 단어들의 후보군을 계산해서 저장해둔다. 그리고 오타교정 대상 키워드가 입력되면, 사전에 저장해둔 후보군을 활용한다.

이러한 구조 덕분에 후보군 계산을 미리 연산하고, 연산된 데이터를 저장해두는 것이 가능해졌다.

from itertools import islice
import pkg_resources
from symspellpy import SymSpell

sym_spell = SymSpell()
dictionary_path = pkg_resources.resource_filename("symspellpy", "frequency_dict.txt")
sym_spell.load_dictionary(dictionary_path, 0, 1)
sym_spell.save_pickle('symspell.pickle')

symspell 파이썬 라이브러리에서는 연산된 객체를 pickle으로 저장하고, 파일을 불러오는 함수도 제공하고 있다.

 

DELETE 방식으로만 후보군 계산하기 

peternoving 알고리즘에서는 insert, delete, transposes, replace 4가지 방식을 활용하여 후보군을 계산한다.

반면 symspell은 delete 후보군만 사용하여, 연산비용을 최적화했다.

 

symspell 알고리즘에서 전처리해둔 단어사전 delete 후보군으로 오타교정 단어를 찾아내는 플로우는 다음과 같다.

 

 

<끝>

자세한건 여기에 👉 1000x Faster Spelling Correction algorithm (2012)