본문 바로가기

소프트웨어 이야기/데이터과학

Symspell 알고리즘 살펴보기 Symspell은 "오타교정", "유사검색어 제안" 기능에서 활용되는 알고리즘이다. Peter Norving도 오타교정에서 유명한 알고리즘이다. 그러나 연산비용이 높기 중국어 같은 언어에서는 활용할 수 없다는 한계점이 있다. ( 글자를 표현하는 유니코드의 종류가 다양하기 때문에 후보군을 모두 계산하기 어렵다. ) Symspell 알고리즘은 Peter Norving 알고리즘의 단점을 보강한 알고리즘이다. 그래서 Peter Norving에 비하여 빠르고, 여러 자연어에서도 활용할 수 있단 장점이 있다. Symspell은 두가지 접근방법 덕분에 연산 비용을 줄이고, 속도를 개선할 수 있었다. 오타 후보군을 사전에 계산하기 DELETE 방식으로만 후보군 계산하기 오타 후보군을 사전에 계산하기 symspell은 ..
Peter Norvig’s 알고리즘 살펴보기 Peter Norvig’s은 대표적인 오타교정 알고리즘이다. 피터노빙 알고리즘을 사용하면 오탈자 키워드가 Input 값으로 주어졌을 때, 해당 오타 키워드를 교정한 단어를 Output으로 주는 함수를 만들 수 있다. 동작 원리 첫번째 단계 : 단어 사전 구축 하기 1. 교정 사전으로 활용할 텍스트 파일을 준비한다. 2. 텍스트 파일에서 단어와 언급수를 계산해둔다. 단어가 언급된 수는 오타 교정 후보 단어가 여러개 나온 경우, 교정 단어의 우선순위를 정할때 사용한다. 두번째 단계 : 키워드 교정하기 1. 검색 키워드를 오타교정 함수에 전달한다. 2. 단어 사전에 있는 키워드인 경우, 그대로 키워드를 반환한다. 이 경우, 검색 키워드가 표준어라고 볼 수 있기 때문이다. 3. 단어사전에서 키워드를 찾지 못한 ..