[🧱|CS] 알잘딱깔센 오타 고쳐주는 레벤슈타인 거리 알고리즘

늘 적당한 거리를 두자.

상상력 대장 LLM

최근 프로젝트를 진행하면서, LLM 모델에게 프롬프트 엔지니어링을 통해 약 400개 정도의 감정 단어 리스트를 고정적으로 제공한 뒤, 인풋 문장의 상황과 문맥에 가장 어울리는 단어를 추출하는 기능을 구현하게 되었다.

예를 들어 "오늘은 나의 생일이다!"라는 문장에 대해서 LLM은 '기쁘다', '행복하다', '기대하다' 등의 감정 단어를 선택해야한다.

그런데 기본적으로 LLM은 상상력이 넘치는 아이다. 분류 문제 등을 해결하는 분류기 등과는 목적부터 다르기 때문이다.

따라서 가끔씩 제시된 단어 목록인 기분 좋다를 무시하고 기분이 좋다를 출력하였다.!

우리의 서비스는 LLM의 출력을 적절히 파싱하고, 실제 DB 상의 감정 단어와 매핑해야했기 때문에 기분이 좋다와 같은 잘못된 출력은 DB 상에 존재하지 않는 데이터 취급을 받고 버려지게 된다.

심각성을 느끼고 LLM의 뛰어난 창의력을 제한해보고자 Temperature 등의 여러 파라미터를 조정하였지만, 동일한 문제는 지속적으로 발생했다.

이런식으로 띄어쓰기와 약간의 조사가 다르다는 이유로 잘못된 결과물 취급을 받는 데이터들이 너무나 아까웠기에, 이를 DB상에 존재하는 정상 단어로 적절히 매핑하고자 고민하게 되었다.

그러다 평소 git 명령어를 사용할 때, 오타가 발생하면 다음과 같은 상황이 발생한다는 사실을 기억하게 되었다.

명령어에 오타가 발생하면 알아서 눈치있고 센스있게 교정해주는 착한 git

어떻게 이렇게 빠른 시간 내에, 내가 원하는 대답을 찾아서 추천해줬던 걸까?
아주 부러운 능력이다.
그 능력의 비밀은 레벤슈타인 거리 알고리즘에 있다.

레벤슈타인 거리(Levenshtein Distance)는 두 문자열 간의 편집 거리를 측정하는 알고리즘이다. 문자열을 다른 문자열로 변환하기 위해 필요한 삽입, 삭제, 교체 연산의 최소 개수를 계산한다. 이 알고리즘은 주로 오타 교정, 문자열 유사도 계산, DNA 서열 분석 등에서 사용된다.

---

레벤슈타인 거리 알고리즘 설명

1. 동작 원리

레벤슈타인 거리 계산은 동적 계획법(Dynamic Programming)을 사용한다.
두 문자열 (A)와 (B)의 길이가 각각 (m)과 (n)일 때, (m * n) 크기의 표를 만들고, 각 칸에 부분 문자열 간의 편집 거리를 기록한다. 총 3가지 기본 편집 연산이 있다.

• 삽입: 한 문자를 추가 (AC -> ABC)
• 삭제: 한 문자를 제거 (ABC -> AC)
• 교체: 한 문자를 다른 문자로 변경 (ABC -> ACC)

2. DP 테이블 구성

테이블의 D[i][j]는 (A)의 처음 (i)개 문자와 (B)의 처음 (j)개 문자 사이의 레벤슈타인 거리를 뜻한다.

테이블의 초기 조건은 다음과 같다.

• (D[0][j] = j): (B)의 처음 (j)개 문자를 만들기 위해 (j)번 삽입
• (D[i][0] = i): (A)의 처음 (i)개 문자를 삭제

"kitten"과 "sitting"에 대해서

	""	s	i	t	t	i	n	g
""	0	1	2	3	4	5	6	7
k	1
i	2
t	3
t	4
e	5
n	6

이후 다음의 점화식에 따라 테이블을 채운다.

• 만약 A[i-1] == B[j-1]라면, D[i][j] = D[i-1][j-1]
• 만약 A[i-1] != B[j-1]라면, D[i][j] = 1 + min(D[i-1][j], D[i][j-1], D[i-1][j-1])
  • 이때 D[i-1][j]는 삭제 연산을 의미
  • D[i][j-1]는 삽입 연산을 의미
  • D[i-1][j-1]는 교체 연산을 의미

이에 따라 테이블을 채우면

	""	s	i	t	t	i	n	g
""	0	1	2	3	4	5	6	7
k	1	1	2	3	4	5	6	7
i	2	2	1	2	3	4	5	6
t	3	3	2	1	2	3	4	5
t	4	4	3	2	1	2	3	4
e	5	5	4	3	2	2	3	4
n	6	6	5	4	3	3	2	3

최종적으로 D[m][n] = 3, 즉 "kitten"을 "sitting"으로 변환하기 위한 최소 연산 횟수는 3이다.

• k → s (교체)
• e → i (교체)
• "" → g (삽입)

---

대반전

구현이 어렵지 않고 직관적인 알고리즘이다.
그러나 해당 부분을 작업할 때 너무 바쁜 나머지 다음의 금단의 기술을 사용했다. (비밀, 꿀팁)

# pip installl levenshtein
import Levenshtein

Levenshtein.distance(target_word, word)

이제 더 쉬운 알고리즘이 됐다.

너무 자주 사용되는 알고리즘이라 아예 라이브러리로 존재하는 것 같다.
싼 게 비지떡이라고, 그냥 import하고 넘어가기에는 뭔가 찝찝하니까 그 원리도 한 번씩 알아두면 좋을 것 같다. (이런 지식은 언젠간 도움이 되기에...)

---

반전의 반전

이렇게 열심히 구현하고 테스트해 본 결과...!!

놀랍게도 안도하다를 애도하다로, 조용하다를 처참하다로 바꿨다..!!!! (처참한 건 나의 마음이다)
한글의 한 글자를 유니코드 1개로 인식하는 문제로 보인다.

찾아보니 고차원적인 위대한 한글을 제대로 분석하기 위해서는, 자음과 모음을 분리해서 알고리즘을 적용해야한다는 것을 알게 되었다.

# pip install jamo
from jamo import h2j, j2hcj
# ...

그러나 이보다 근본적인 문제점이 있다.
레벤슈타인 거리는 단어의 의미론적 유사도는 측정하지 못한다는 것이다.

사실 우리의 서비스가 감정 단어를 제대로 매핑시키기 위해서는 단순 오타 교정이 아닌, 단어의 의미론적인 유사성까지도 고려해야한다.
레벤슈타인 거리는 편집 거리만을 고려하기에 알고리즘의 선택 자체가 부적절하다고 판단했다.

따라서 텍스트 벡터 임베딩 기법을 사용하기로 결정하고, 모든 레벤슈타인 거리 관련 코드는 삭제하였다.

pip uninstall levenshtein

---

그래도 잠깐이지만 만나서 반가웠어 levenshtein. 🥹