Autohotkey DTW(Dynamic Time Warping) 를 사용한 글자 매칭

Autohotkey에서 DTW(Dynamic Time Warping) 를 사용한 글자 매칭

Autohotkey 는 간단한 단축키 활용에 쓰기 좋지만 복잡한 알고리즘 들도 만들어 사용하기 편리 합니다. 

우리가 프로그래밍 시에 사용하는 웬만한 데이터 타입들은 대부분 제공을 해 주고 Class 등도 만들 수도 있으니

프로그래밍 언어로 사용하지 않을 이유가 없는거죠.

요즘 저는 영어 단어에서 틀린 글자가 있는지 찾는 작업을 하고 있습니다. 

예를 들어 Autohotkey 라는 단어가 맞는 표현인데 Autuhotkey, autohutky 와 같이 잘못 씌여진 경우에 대해 찾아보는 작업 입니다.

Autohotkey, Autoit, Python, Powershell, Ruby 와 같은 단어가 정상적인 단어의 세트라고 할때

위 단어 셋트 중에 Autuhotkey 라고 잘못 쓴 단어가 어떤 단어와 얼마나 유사한지를 확인해 보고 싶은 겁니다.

이를 위해 패턴인식 책에 있는 알고리즘 중 DTW(Dynamic Time Warping)을 적용해 봐야 겠다고 생각 했습니다.

DTW(Dynamic Time Warping) 는 시계열 데이터 즉, 순서가 있는 데이터의 유사성을 측정하는 알고리즘입니다. 

https://en.wikipedia.org/wiki/Dynamic_time_warping

우리가 사용하는 단어도 사실은 순서가 매우 중요하죠. 

Autohotkey 라는 단어와 Atuoohtkey 라는 단어는 글자수나 그 구성된 알파벳은 같지만 엄밀히 다른 단어라고 볼 수 있습니다. Atuoohtkey 는 Autohotkey 를 잘못 타이핑 했을 가능성이 높은 단어인 거죠.

인간이 타이핑을 하다보면 이렇게 오타를 내는 경우는 비일 비재 하고 이런 오타들을 DTW와 같은 알고리즘을 이용해서 찾을 수 있을 거라고 생각 했습니다. 

이 이외에도 언듯 생각할 수 있는 분야는 다운로드 받은 드라마를 폴더 별로 정리한다던지 하는 등의 분류 작업 들입니다.

DTW 에 대한 공부를 위해 아래 웹 페이지들을 참조했고, 

http://www.speech.zone/exercises/dtw-in-python/

https://nipunbatra.github.io/blog/2014/dtw.html

http://www.smallake.kr/?p=17918

https://jeremykun.com/2012/07/25/dynamic-time-warping/

유사한 단어를 찾는 것이므로 dtw 의 Backtracking  과정은 생각 했습니다.

결과적으로 다음과 같은 dtw(ByRef testV) 함수를 만들 수 있었고 코드는 아래와  같습니다. 

reference 로 할 단어의 셋은 아래와 같이 설정했고~ 

refArray := ["Autohotkey", "Autoit", "Python", "Powershell", "Ruby"]

각 단어들을 dtw 알고리즘을 사용하여 어떤 단어와 가장 유사한가를 추천 받을 수 있습니다. 

아래와 같이 실행하면 

dtw("Autuhotkey")

dtw("autohutky")

dtw("Pithon")

각 단어들이 다음과 같이 어떤 reference 단어 셋과 일치하는 지를 확인 할 수 있습니다.