해당 글은 한국어 특성 기반의 STT 엔진 정확도를 위한 정량적 평가방법 연구 : 민소연, 이광형, 이동선, 류동엽(2020) 논문을 참고하여 작성되었습니다.

Levenshtein distance란?

문자열 처리에서 Levenshtein 거리는 두 문자열 간의 유사성을 측정하는 데 사용되는 중요한 개념입니다. 이것은 "편집 거리" 또는 "문자열 거리"로도 알려져 있습니다.

Levenshtein 거리는 두 문자열 사이의 차이를 나타냅니다. 이 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 횟수를 측정합니다. 이러한 "편집"은 문자열에서 문자를 삽입(insert), 삭제(delete) 또는 대체(replace)하는 작업을 의미합니다.

예를 들어, "kitten"과 "sitting" 두 문자열 간의 Levenshtein 거리를 계산해보겠습니다.

"k"를 "s"로 대체합니다.
"e"를 "i"로 대체합니다.
"en"을 "ing"으로 대체합니다.

총 3회의 편집이 필요하므로 Levenshtein 거리는 3입니다.

위의 과정을 Metrix로 표현해 보겠습니다.

"kitten"과 "sitting"의 경우 다음과 같은 행렬이 만들어집니다.

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

최종적으로 마지막 셀의 값인 3이 Levenshtein 거리가 됩니다.

Levenshtein 기본 알고리즘

해당 알고리즘은 구현되어 있는 기본 알고리즘을 바탕으로 Dart 코드로 구현되었습니다.

1. 함수 levenshtein은 두 개의 문자열 s1과 s2를 입력으로 받습니다.
2. 두 문자열 중 짧은 문자열을 s2로 설정합니다. 그리고 s2가 빈 문자열인지 확인하여, 만약 그렇다면 s1의 길이를 반환하여 두 문자열의 길이 차이를 계산합니다.
3. 이전 행(혹은 이전 배열)을 나타내는 previousRow라는 리스트를 초기화합니다. 이 리스트는 s2의 길이 + 1 만큼의 요소를 가지며, 각 요소는 인덱스를 가진 값으로 초기화됩니다.
4. s1의 각 문자에 대해 반복합니다. 각 반복에서 currentRow 리스트를 초기화합니다. 이 리스트의 첫 번째 요소는 현재 인덱스 i에 1을 더한 값입니다.
5. s2의 각 문자에 대해서도 반복합니다. 각 반복에서 삽입, 삭제, 대체 연산의 비용을 계산하고, 그 중 최소 비용을 currentRow에 추가합니다.
6. 모든 반복이 완료되면, 마지막 previousRow의 요소를 반환하여 두 문자열 간의 편집 거리를 반환합니다.

int levenshtein(String s1, String s2, {bool debug = false}) {
  if (s1.length < s2.length) {
    return levenshtein(s2, s1, debug: debug);
  }

  if (s2.isEmpty) {
    return s1.length;
  }

  List<int> previousRow = List<int>.generate(s2.length + 1, (int index) => index);

  for (int i = 0; i < s1.length; i++) {
    List<int> currentRow = [i + 1];

    for (int j = 0; j < s2.length; j++) {
      int insertions = previousRow[j + 1] + 1;
      int deletions = currentRow[j] + 1;
      int substitutions = previousRow[j] + (s1[i] != s2[j] ? 1 : 0);
      currentRow.add(min(insertions, deletions, substitutions));
    }

    if (debug) {
      print(currentRow.sublist(1));
    }

    previousRow = currentRow;
  }

  return previousRow.last;
}

앞전 글에서 언급한 바와 같이, 해당 알고리즘은 한국어와 함께 사용하였을 때 문제가 발생합니다. 한글은 영어처럼 알파벳으로 이루어지지 않 고 초,중,종성이 하나의 글자를 이루기 때문에, 한 글자 단위로 levenshtein 거리를 계산할 경우 실제로는 비슷한 단어임에도 더 많은 distance를 가진다고 계산될 수 있습니다.

예를들면 아래와 같은 3가지 단어는 동일한 distance를 가진다고 판단됩니다.

A : 산토끼
B : 산톡희
C : 산사람

이를 위해 한국어에 해당 알고리즘을 적용하기 위해서는 크게는 3가지 단계가 필요합니다.

1. 한국어의 초/중/종성을 분리한다.
2. 분리된 초/중/종성마다 Levenshtein Distance를 게산한다.
3. 정확성을 높이기 위해, 초/중/종성에 따라 계산 가중치를 부여한다.

한국어 초/중/종성 분리

한글은 유니코드 상에서 초성, 중성, 종성이 서로 연결된 형태로 구성되어 있으므로, 각 글자를 유니코드로 분석하여 나눌 수 있습니다.

한국어의 초/중/종성을 분리하기 위해서 필요한 값은 아래와 같습니다.

• 한국어 유니코드 시작 숫자 = 44032
• 한국어 초성 값의 시작 숫자 = 588
• 한국어 중성 값의 시작 숫자 = 28

1. 문자를 유니코드 숫자 값으로 변경합니다.
2. 한국어 초성 값의 시작 숫자(588)로 나눈 몪이 초성의 index값이 됩니다.
3. 나눈 후, 초성값을 빼고 중성 값의 시작 숫자(28)로 나눈 몪이 중성의 index값이 됩니다.
4. 위의 작업을 수행한 후의 나머지 값이 종성의 index값이 됩니다.

  static List<String>? _decompose(String c) {
    if (!isKoreanChar(c)) return null;
    int i = c.codeUnitAt(0);
    if (_jaumBegin <= i && i <= _jaumEnd) return [c, ' ', ' '];
    if (_moumBegin <= i && i <= _moumEnd) return [' ', c, ' '];

    // decomposition rule
    i -= _korBegin;
    int cho = i ~/ _chosungBase;
    int jung = (i - cho * _chosungBase) ~/ _jungsungBase;
    int jong = (i - cho * _chosungBase - jung * _jungsungBase);
    return [_chosungList[cho], _jungsungList[jung], _jongsungList[jong]];
  }

초/중/종성 분리를 적용한 Levenshtein 알고리즘

int jamoLevenshtein(String s1, String s2, {bool debug = false}) {
  if (s1.length < s2.length) {
    return jamoLevenshtein(s2, s1, debug: debug);
  }

  if (s2.isEmpty) {
    return s1.length;
  }

  double substitutionCost(String c1, String c2) {
    if (c1 == c2) {
      return 0;
    }
    return levenshtein(decompose(c1), decompose(c2)) / 3;
  }

  List<double> previousRow = List<double>.generate(s2.length + 1, (int index) => index.toDouble());

  for (int i = 0; i < s1.length; i++) {
    List<double> currentRow = [i + 1.0];

    for (int j = 0; j < s2.length; j++) {
      double insertions = previousRow[j + 1] + 1;
      double deletions = currentRow[j] + 1;
      double substitutions = previousRow[j] + substitutionCost(s1[i], s2[j]);
      currentRow.add(min(insertions, deletions, substitutions));
    }

    if (debug) {
      print(currentRow.sublist(1).map((double v) => v.toStringAsFixed(3)).toList());
    }

    previousRow = currentRow;
  }

  return previousRow.last.toInt();
}

String decompose(String c) {
  // 구현된 초,중,종성 분리 알고리즘 사용
  return c;
}

int levenshtein(String s1, String s2) {
  // 구현된 levenshtein 알고리즘 사용
  return 0;
}

초/중/종성에 따른 가중치

여기까지 구현했다면, 한국어에 대해서 높은 정확도를 가진 Levenshtein 알고리즘을 이미 구현했다고 볼 수 있습니다. 하지만 여기서 더 높은 정확도를 가진 알고리즘으로 개선해 보겠습니다.

  /// Computes the Levenshtein distance between two Korean strings based on character level.
  ///
  /// Parameters:
  /// - [s1] : The first Korean string.
  /// - [s2] : The second Korean string.
  /// - [phonemeCost] : Customized weights for different phonemes.
  /// - [debug] : Whether to print debugging information.
  ///
  /// Returns the Levenshtein distance between the two strings.
  static double _levenshtein(String s1, String s2,
      {PhonemeCost? phonemeCost, bool debug = false}) {
    if (s1.length < s2.length) {
      return _levenshtein(s2, s1, phonemeCost: phonemeCost, debug: debug);
    }

    if (s2.isEmpty) return s1.length.toDouble();

    List<double> previousRow =
        List<double>.generate(s2.length + 1, (int index) => index.toDouble());

    for (int i = 0; i < s1.length; i++) {
      final cost = (phonemeCost != null)
          ? phonemeCost.getCostByOrderOfPhoneme(i)
          : _defaultDistanceCost;

      List<double> currentRow = [i + cost];

      for (int j = 0; j < s2.length; j++) {
        double insertions = previousRow[j + 1] + cost;
        double deletions = currentRow[j] + cost;
        double substitutions = previousRow[j] + (s1[i] != s2[j] ? cost : 0);
        currentRow.add([insertions, deletions, substitutions]
            .reduce((a, b) => a < b ? a : b));
      }

      if (debug) print(currentRow.sublist(1));

      previousRow = currentRow;
    }

    return previousRow.last;
  }

기존 Levenshtein알고리즘에 초,중,종성에 따라 PhonemeCost를 적용하도록 수정하였습니다.

/// Class to specify Levenshtein distance weights for Korean phonemes
class PhonemeCost {
  /// Sum of values for three phonemes that constitute one syllable
  static const _totalPhonemeCost = 3.0;

  /// Default cost assigned to a single phoneme
  static const _defaultSinglePhonemeCost = 1.0;

  /// Number of phonemes in a Korean syllable
  static const _koreanCharSyllableNumber = 3;

  /// Weight assigned to the first phoneme of a syllable
  final double chosungCost;

  /// Weight assigned to the second phoneme of a syllable
  final double jungsungCost;

  /// Weight assigned to the third phoneme of a syllable
  final double jongsungCost;

  /// Constructs a PhonemeCost object with specified weights for each phoneme
  const PhonemeCost({
    this.chosungCost = 1.5,
    this.jungsungCost = 1.0,
    this.jongsungCost = 0.5,
  }) : assert((chosungCost + jungsungCost + jongsungCost) == _totalPhonemeCost,
            'Total cost weight should be 3.0');

  /// Retrieves the weight based on the order of the phoneme in a syllable
  ///
  /// The [orderIndex] indicates the position of the phoneme within the syllable,
  /// with 0 being the first phoneme, 1 being the second, and 2 being the third.
  /// If the [orderIndex] is out of range, the default single phoneme cost is returned.
  double getCostByOrderOfPhoneme(int orderIndex) {
    int phonemeIndex = orderIndex % _koreanCharSyllableNumber;

    if (phonemeIndex == 0) {
      return chosungCost;
    } else if (phonemeIndex == 1) {
      return jungsungCost;
    } else if (phonemeIndex == 2) {
      return jongsungCost;
    } else {
      return _defaultSinglePhonemeCost;
    }
  }
}

기호에 대한 변환

퍼센트(%) 다시(-) 와 같은 기호 문자들에 대해 어떻게 읽도록 비교할지 사용자가 설정할 수 있습니다.

  static String replaceSpecialCharsWithKorean(
    String text, {
    required List<SpecialCharToSpeech> specialCharToSpeech,
  }) {
    Map<String, String> specialCharsToKoreanMap = {};

    if (specialCharToSpeech.isNotEmpty) {
      specialCharsToKoreanMap.addAll(
        {for (var v in specialCharToSpeech) v.specialChar: v.speech},
      );
    }

    String result = '';
    for (int i = 0; i < text.length; i++) {
      String char = text[i];
      if (specialCharsToKoreanMap.containsKey(char)) {
        result += specialCharsToKoreanMap[char] ?? '';
      } else {
        result += char;
      }
    }

    // Remove any special characters that were not replaced.
    result = result.removeAllSpecialCharsNotKorean();

    return result;
  }

숫자에 대한 변환

'2023년 3월 24일 새로운 소식이 발표되었습니다'와 같은 문자를 실제 발화된 문장과 비교하기 위해서는 숫자를 한글 발화 방식으로 바꿀 필요가 있습니다.

extension NumberExtension on int {
  /// Converts the integer number to Korean representation.
  ///
  /// Returns the Korean representation of the integer number.
  String numbersToKorean() {
    int number = this;
    List<String> koreanNumber = [
      '',
      '일',
      '이',
      '삼',
      '사',
      '오',
      '육',
      '칠',
      '팔',
      '구'
    ];
    List<String> tenUnit = ['', '십', '백', '천'];
    List<String> tenThousandUnit = ['조', '억', '만', ''];
    int unit = 10000;

    String answer = '';

    while (number > 0) {
      int mod = number % unit;
      List<String> modToArray = mod.toString().split('');
      int length = modToArray.length - 1;

      String modToKorean = modToArray.asMap().entries.fold('', (acc, entry) {
        int index = entry.key;
        int valueToNumber = int.parse(entry.value);
        if (valueToNumber == 0) return acc;
        // Do not output '일' character for units above ten. ex) 일십 -> 십
        String numberToKorean = index < length && valueToNumber == 1
            ? ''
            : koreanNumber[valueToNumber];
        return '$acc$numberToKorean${tenUnit[length - index]}';
      });

      answer = '$modToKorean${tenThousandUnit.removeLast()}$answer';
      number = (number / unit).floor();
    }

    return answer.trim();
  }
}

korean_levenshtein

위에서 언급한 자모음 분리, 숫자 및 기호변환, 초/중/종성별 가중치 적용을 반영한 korean_levenshtein 는 pub.dev에서 확인해보실 수 있습니다.

https://pub.dev/packages/korean_levenshtein