[🔔TIL] 맞춤법 검사 시스템을 설계하려면 어떻게 해야 할까?

본 내용의 출처는 262가지 문제로 정복하는 코딩 인터뷰 in Java에 있으며, 추가한 내용이 있을 수 있습니다.

Day1

---

☁️ 레벤슈타인 거리에 대해서 알아보자.

먼저, 맞춤법 검사 시스템을 설계하려면 레벤슈타인 거리를 구할 수 있어야 한다.

레벤슈타인 거리?

• 철자가 틀린 문자열이 주어졌을 때, 맞춤법 검사기는 사전에서 해당 문자열과 가장 가까운 단어를 반환
• 문자열이 얼마나 비슷한지를 계산하는 것, 편집 거리라고도 부름.
• 두 단어의 거리 = 최소 편집 횟수
  • 철자가 틀린 단어에서 철자가 올바른 단어로 변환하는 데 필요한 횟수

편집?

• 문자의 삽입, 삭제, 치환을 일컬음.
• ex) "Saturday"에서 "Sundays"로 변환
  • 첫 번째 'a'와 't'를 삭제, 'r'을 'n'으로 치환, 마지막에 's'를 삽입해야 함.
  • 즉, 이 둘 사이의 레벤슈타인 거리는 4가 됨.

Day2

---

☁️ 레벤슈타인 거리 구해보기

🔎 문자열 2개가 입력으로 주어졌을 때, 첫 번째 문자열에서 두 번째 문자열로 변환하는 데 필요한 최소 편집 횟수를 구하라.

Hint : 범위를 좁혀 두 문자열의 접두사를 대상으로 동일한 문제 풀어보기

• Solution 01
  • 두 번째 문자열과 같은 문자열을 찾을 때까지 첫 번째 문자열과 거리가 1, 2, 3,..인 모든 문자열을 나열
  • 나열해야 할 문자열의 개수가 방대해지는 문제가 있음.
  • ex) 첫 번째 문자열의 길이가 n인 0이고 두 번째 문자열이 길이가 n인 1이라고 했을 때, 모든 가능한 $2^n$개의 문자열을 살펴봐야 함.

• Solution 02

  • 탐색 도중 '가지 치는' 방법
  • 첫 번째 문자열의 마지막 문자가 두 번째 문자열의 마지막 문자와 같다면, 이 문자를 무시해도 됨.
  • 다르다면, 기존 문자열에 초점을 맞춰 최종 편집을 수행하면 됨.
  • 최종 편집은 삽입, 삭제, 치환 중의 하나가 됨.
  
  

• a와 b가 각각 문자열 A와 B의 길이라고 했을 때의 레벤슈타인 거리

  • $E(A[0, a - 1], B[0, b - 1])$

• 여기서 알 수 있는 사실

  • A의 마지막 문자가 B의 마지막 문자와 같다면

    • $E(A[0, a - 1], B[0, b - 1]) = E(A[0, a - 2], B[0, b - 2])$

  • A의 마지막 문자가 B의 마지막 문자와 다르다면
    $E(A[0, a - 1], B[0, b - 1]) = 1 + min( E(A[0, a - 2], B[0, b - 2]), E(A[0, a - 1], B[0, b - 2]), E(A[0, a - 2], B[0, b - 1], )$

• A에서 B로 변환하는 방법 3가지($A[0, a - 1]$에서 $B[0, b - 1]$로 변환)
  • $A[0, a - 2]$에서 $B[0, b - 2]$로 변환한 뒤에, A의 마지막 문자를 B의 마지막 문자로 치환
  • $A[0, a - 1]$에서 $B[0, b -2]$로 변환한 뒤에, B의 마지막 문제를 뒤에 추가
  • $A[0, a - 2]$에서 $B[0, b - 1]$로 변환한 뒤에, A의 마지막 문자를 삭제

• 증명
• 임의의 최적해를 선택한 뒤, 그 순서를 재배치하는 방법에 기반을 두고 있음.
• 동적 프로그래밍으로 해결 -> $E(A[0, a - 1], B[0, b - 1])$을 구하는 중간 결과를 캐시에 저장

• 실제 예시 확인하기
  • 단어 "carthorse"와 "Orchestra"의 레벤슈타인 거리(E)
  • 풀이 : 대문자와 소문자는 다른 문자로 취급, 레벤슈타인 거리는 8
    

• 코드로 확인하기

  • k < a, l < b에 대해 $E(A[0.k], B[0, l])$을 이미 알고 있다면 -> $E(A[0, a - 1], B[0, b - 1])$을 구하는 시간은 O(1)
  • 즉, 해당 알고리즘의 전체 시간 복잡도 및 공간 복잡도 = $O(ab)$

  public static int levenshteinDistance(String A, String B) {
      int[][] distanceBetweenPrefixes = new int[A.length()][B.length()];
      for(int[] row : distanceBetweenPrefixes) {
          Arrays.fill(row, -1);
      }
      return computeDistanceBetweenPrefixes(A, A.length() - 1, B, B.length() - 1, distanceBetweenPrefixes);
  }
  
  private static int computeDistanceBetweenPrefixes(String A, int A_idx, String B, int B_idx, int[][] distanceBetweenPrefixes) {
  
      if(A_idx < 0) {
          // A가 비어있으므로 B의 모든 문자를 추가한다.
          return B_idx + 1;
      } else if (B_idx < 0) {
          //B가 비어있으므로 A의 모든 문자를 삭제한다.
          return A_idx + 1;
      }
  
      if(distanceBetweenPrefixes[A_idx][B_idx] == -1) {
          if(A.charAt(A_idx) == B.charAt(B_idx)) {
              distanceBetweenPrefixes[A_idx][B_idx] = computeDistanceBetweenPrefixes(A, A_idx - 1, B, B_idx - 1, distanceBetweenPrefixes);
          }
  
          else {
              int substituteLast = computDistanceBetweenPrefixes(A, A_idx - 1, B, B_idx - 1, distanceBetweenPrefixes);
  
              int addLast = computDistanceBetweenPrefixes(A, A_idx - 1, B, B_idx, distanceBetweenPrefixes);
  
              distanceBetweenPrefixes[A_idx][B_idx] = 1 + Math.min(substituteLast, Math.min(addList, deleteLast));
          }
      }
      return distanceBetweenPrefixes[A_idx][B_idx];
  }

😎 응용 5문제
1. $O(min(a,b)$ 공간 복잡도와 $O(ab)$ 시간 복잡도의 레벤슈타인 거리를 구하라.
2. A와 B가 주어졌을 때, 가장 긴 A와 B의 부분 수열을 구하라. 예를 들어 위 그림(표)에 나온 문자열에서 가장 긴 부분 수열은 $<r, h, s>$이다.
3. 문자열 A가 주어졌을 때, 회문을 만들기 위해 삭제해야 하는 최소 문자의 개수를 구하라.
4. 문자열 A와 정규표현식 $r$이 주어졌을 때, $r$로 표현할 수 있는 문자열 중에서 A와 가장 가까운 문자열은 무엇인가? 문자열 사이의 거리는 레벤슈타인 거리를 사용한다.
5. 문자열 $t$는 문자열 $s_1$과 $S_2$를 왼쪽에서 오른쪽 순서대로 번갈아 배치시켜서 만들 수 있는 문자열을 말한다.
예를 들어, $s_1$이 "gtaa"이고, $s_2$가 "atc"라고 했을 때, "gattaca"와 "gtataac"는 $s_1$과 $s_2$를 번갈아 배치시켜서 만들 수 있지만, "gatacta"는 만들 수 없다.
문자열 $s_1$, $s_2$, $t$가 주어졌을 때, $t$가 문자열 $s_1$, $s_2$를 번갈아 배치시켜서 만들 수 있는지 확인하는 알고리즘을 설계하라.

Day3

---

☁️ 맞춤법 검사 설계

• 맞춤법 검사기에서는 전체 사전에서 주어진 문자열과 가장 가까운 단어의 집합을 반드시 찾아야 함.
• 레벤슈타인 거리는 맞춤법 검사기에 적합한 거리 측정 함수가 아닐 수도 있음.
• 흔한 철자 오류 혹은 키보드 위에서의 가까운 문자의 상황을 고려하지 않음.

🔎 이러한 조건을 고려할 때, 맞춤법 검사 시스템은 어떻게 만들 것인가?

Hint : 두 단어 사이의 거리에 대한 개념을 먼저 정의하기

✨ IDEA : 맞춤법 검사 시스템은 대부분 철자 오류가 발생한 단어와 의도한 단어 사이의 레벤슈타인 거리가 작은(1 or 2개 차이) 경향이 있다.

• 해시 테이블에 사전 안에 있는 모든 단어 넣기 + 레벤슈타인 거리가 2인 단어만 탐색 -> 높은 확률로 의도한 단어를 찾을 수 있음.
  • 필요한 해시 테이블 탐색 횟수 : 주어진 알파벳 개수가 m이고, 탐색할 문자열의 길이가 n이라면 $O(n^2m^2)$

• 주어진 문자열 길이가 n이라면 -> 임의의 문자 두 개를 선택한 뒤 각 문자를 임의의 다른 알파벳으로 치환해보기
  • 임의의 두 문자를 선택하는 방법의 개수 : 총 $n(n-1)/2$이며, 각 문자를 $(m - 1)$개의 다른 문자로 바꾸는 시도를 해야하므로 총 $n(n-1)(m-1)^2 / 2$ 만큼 해시 테이블 탐색

• 레벤슈타인 거리가 2 이하인 모든 문자열 집합과 사전 내의 모든 문자열 집합 사이의 교집합은 매우 클 수 있음.
• 각 후보 문자열에 랭킹을 매기고, 가장 그럴듯한 문자열부터 차례대로 보여주는 것이 좋음.

1️⃣ 타이핑 오류 모델

• 타이핑 오류는 키보드 자판 배열에 따라 모델링 가능

2️⃣ 음성 모델링

• 단어를 들을 때와 실제 맞춤법 사이의 차이에서 오는 경우에 해당
• 문장의 음소와 같은 음성의 단어 리스트를 매핑하기

3️⃣ 수정했던 기록

• 사용자들의 경우, 잘못 입력한 뒤 수정하는 경우도 많음.
• 이를 모아서 -> 가장 많이 틀리는 철자에 대한 방대한 데이터를 얻을 수 있음.

4️⃣ stemming(스테밍)

• 각 단어를 형태소별로 저장 -> 사전 크기 줄일 수 있음.
• 이 경우, 입력으로 들어온 문장에도 스테밍을 적용해야 함.

Day4-5

---

☁️ 스테밍 문제의 해법 설계하기

스테밍이란?

• 주어진 단어의 활용형을 쿼리 문자열과 문서 모두에서 하나의 공통된 원형으로 줄이는 것
  ex) {computers, computer, compute} -> compute라는 단어로 매핑 가능

🔎 빠르고 효과적인 스테밍 알고리즘을 설계하라.

Hint : 주어진 예제 ("computation, "computers", "compute", "computing")을 통해 일반적인 규칙을 찾기

• 대부분의 스테밍 시스템은 간단한 재작성 규칙을 바탕으로 하고 있음.
• ex1) "es", "s", "ation"과 같은 접미사는 제거
• ex2) 복수형 표현이 다른 경우 -> wolves의 스테밍 결과는 wolf이기 때문에 "ves"는 "f"로 치환하는 규칙도 필요함.

• 방법 1: 모든 규칙에 대해 유한 상태 머신(finite state machine) 을 만드는 것
  • 대부분의 경우, 어떤 접미사 집합을 만나면 그에 상응하는 다른 문자열로 대체하는 것

• 방법 2: Martin Porter가 개발한 포터 스테머(stemmer) 사용
  • 일반적인 규칙에서 벗어나는 단어를 예외상황으로 처리함.
  • 영어를 스테밍하는 권위 있는 알고리즘 중 하나임.
  • 모음과 자음의 패턴을 바탕으로 여러 가지 규칙을 만들었음.

• 방법 3: 스토캐스틱(stochastic) 방법을 사용해 규칙을 재작성
  • M-그램 방법 -> 주변 단어를 통해 현재 단어의 올바른 스테밍 결과를 찾음.

🦕 또 다른 맞춤법 검사 알고리즘 알아보기

1️⃣ Symspell 알고리즘

• Symspell을 이용한 한글 맞춤법 교정

2️⃣ Deep-speller

• [영상] 딥(Deep)하게 오타 교정하기
• [정리] 딥(Deep)하게 오타 교정하기

3️⃣ 한글 맞춤법 검사 관련

• py-hanspell
• VSCode 익스텐션 개발 경험 (Korean Grammar Checker 맞춤법 검사기)
• [NLP] 한국어 구어체(대화체) 맞춤법 교정 모델 (Korean typos corrector) : ET5 Text2Text Generation

4️⃣ SymSpell 알고리즘 + 한글

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

5️⃣ 검색 시스템에서의 오타 교정 및 보정 관련

• [Naver Developers] 검색 > 오타변환 API
• [한컴 디펠로퍼 포럼] 맞춤법 검사 API
• 검색 시스템 톺아보기 — 1. 검색어 자동완성과 오타 교정 기능
• 딥러닝 없이 검색어 오타 보정하기

번외) 맞춤법 관련 논문 정리

• 맞춤법 논문 정리

Day6

---

☁️ Symspell 알고리즘 톺아보기

내용 출처

• SymSpell 알고리즘을 이용하여 한글 맞춤법 교정 적용해보기
• 1000x Faster Spelling Correction algorithm (2012)

• Symspell 알고리즘이란?

  • 편집 거리 알고리즘에서 삭제(delection)만 사용
  • 성능을 향상시키기 위한 목적으로, 최소한의 연산만 사용하려는 것
  • 편집 거리를 통해 구한 어절과 원래의 단어를 해시 테이블과 같은 검색이 빠른 자료구조 형식으로 저장함.
  • 사전에 있는 단어의 delection을 계산해 자료 구조로 저장
  • ex) "apple"과 "apply"
    • 편집 거리가 1인 delection은 "appl", "pply" 등이 있음.
    • 편집 거리가 2인 delection은 "app", "ppl" 등이 있음.
  
  

• 사용하는 방법은? (Python ver.)

1. 오픈소스 라이브러리를 통해 pip 설치

   pip install symspellpy

2. 앞서 만든 키워드 사전을 불러와 사전 구축 & lookup 메서드를 통한 유사 어절 찾기
   a. Verbosity.ALL을 이용해 가장 가까운 편집 거리와 가장 큰 빈도수를 갖는 어절을 모두 반환
   b. 더 자세한 사용법은 API 문서 확인

3. 한글의 특성에 맞춰 자소 단위로 분리해 정확한 오타 교정하기
   a. 한글 자소 분해 : 파이썬 라이브러리 hangul-utils 사용

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("오타 교정 결과를 찾을 수 없습니다.")

Day7

---

☁️ 최종 정리

Q. 맞춤법 검사 시스템의 설계는 어떻게 하는 것이 좋을까?

A. 레벤슈타인 거리를 통해 편집 거리를 구하고, 각 후보 문자열에 랭킹을 매겨, 가장 그럴 듯한 문자열부터 차례대로 보여주는 방식이 가장 좋다.

• Solution 01 : 문자열을 나열해 두 번째 문자열과 같은 문자열을 찾을 때까지 첫 번째 문자열과 거리가 1, 2, 3, ...인 모든 문자열을 나열하는 방법
  • $2^n$개의 문자열을 살펴봐야 하는 문제점이 있음.

• Solution 02 : 탐색 도중 '가지 치는' 방법
  • 첫 번째 문자열의 마지막 문자가 두 번째 문자열의 마지막 문자와 같다면 "문자 무시", 다르다면 최종 편집 수행
  • 최종 편집은 삽입, 삭제, 치환 중의 하나