회화 녹음결과물과 실제 정답을 비교할 때의 알고리즘

쉽게 생각했지만..

최근 회화 연습 서비스를 구현하면서 사용자의 녹음 결과를 정답 문장과 비교해야 하는 일이 있었다.

사용자는 화면에 제시된 문장을 보고 말하고, 서비스는 녹음 결과를 텍스트로 변환한다. 이후 해야 할 일은 간단해 보인다.

• 사용자가 정확히 말한 단어는 그대로 표시한다.
• 빠뜨린 단어는 누락으로 표시한다.
• 불필요하게 추가한 단어는 추가 입력으로 표시한다.
• 잘못 말한 단어는 교체된 단어처럼 보여준다.

예를 들어 정답은 나는 밥을 먹었다 인데, 녹음 결과가 나는 빵을 먹었다 로 인식되었다고 해보자. 사람이 보기에는 간단하다. 밥을 을 빵을 로 잘못 말했다.

그런데 코드 입장에서는 이 판단이 생각보다 애매하다.

정답에만 있는 단어를 누락으로 봐야 할지, 녹음 결과에만 있는 단어를 추가로 봐야 할지, 아니면 둘을 묶어 잘못 말한 단어로 봐야 할지 결정해야 한다. 결국 필요한 것은 두 문장 사이에서 어떤 단어 흐름이 유지되었는지 를 먼저 찾는 일이다.

이 기준점을 잡기 위해 LCS 를 활용할 수 있었다.

먼저 문제를 조금 더 단순하게 보자

회화 연습 서비스에서 비교하려는 대상은 크게 두 가지다.

• 정답 스크립트
• 사용자의 녹음 결과를 텍스트로 변환한 문장

내부 구현에서는 이 둘을 토큰 배열로 바꿔 비교한다. 문장 전체를 문자열 하나로 비교하기보다는, 단어 단위로 쪼개야 어떤 단어가 맞고 틀렸는지 표시할 수 있기 때문이다.

const answerTokens = ["나는", "밥을", "먹었다"];
const spokenTokens = ["나는", "빵을", "먹었다"];

여기서 바로 밥을 과 빵을 을 비교해서 틀렸다고 판단할 수도 있지 않을까 싶다. 하지만 실제 회화 문장에서는 사용자가 단어를 빠뜨리거나, 중간에 불필요한 단어를 넣거나, 순서가 어긋난 형태로 말할 수 있다.

그래서 단순히 같은 인덱스끼리 비교하면 금방 한계가 생긴다.

예를 들어 사용자가 단어 하나를 앞에서 빠뜨렸다면, 그 뒤의 모든 단어 인덱스가 밀린다. 그러면 실제로는 맞게 말한 단어들까지 전부 틀린 것처럼 보일 수 있다.

결국 먼저 찾아야 하는 것은 “같은 위치의 단어” 가 아니라, 순서를 유지하면서 양쪽 문장에 공통으로 남아있는 단어 흐름 이다.

결국 기준점은 LCS 이다

LCS 는 Longest Common Subsequence, 즉 최장 공통 부분 수열을 의미한다.

정의만 보면 조금 딱딱하지만, 문장 비교 관점에서는 꽤 직관적이다. 두 배열이 있을 때 순서는 유지하되, 양쪽 모두에 존재하는 가장 긴 흐름을 찾는 것이다.

앞선 예제를 다시 보자.

const answerTokens = ["나는", "밥을", "먹었다"];
const spokenTokens = ["나는", "빵을", "먹었다"];

양쪽 문장에 공통으로 남는 흐름은 다음과 같다.

["나는", "먹었다"]

그렇다면 이 흐름에 포함되지 못한 밥을 은 정답 쪽에만 남은 단어이고, 빵을 은 녹음 결과 쪽에만 남은 단어이다.

이제 비교 결과는 아래처럼 해석할 수 있다.

[
  { type: "same", answer: "나는", spoken: "나는" },
  { type: "changed", answer: "밥을", spoken: "빵을" },
  { type: "same", answer: "먹었다", spoken: "먹었다" },
]

중요한 것은 처음부터 changed 를 바로 찾는 것이 아니라는 점이다. 먼저 LCS 로 유지된 단어 흐름을 찾고, 그 흐름에서 벗어난 단어를 누락 또는 추가로 분류한다. 그 다음 인접한 누락과 추가를 묶어 “잘못 말한 단어” 로 해석한다.

이렇게 나누면 구현 책임이 훨씬 명확해진다.

첫 번째 단계는 미래 점수표를 만드는 것이다

LCS 를 구현할 때는 보통 동적 계획법을 사용한다. 여기서는 각 위치에서 시작했을 때 앞으로 몇 개의 단어를 더 맞출 수 있는지 저장하는 2차원 표를 만든다.

이 표를 단순하게 “미래 점수표” 라고 부르겠다.

미래 점수표의 한 칸은 다음 의미를 가진다.

정답 문장의 현재 위치와 녹음 결과의 현재 위치에서 비교를 시작하면, 앞으로 최대 몇 개의 단어를 공통 흐름으로 인정할 수 있는가

예를 들어 scoreTable[answerIndex][spokenIndex] 라는 값이 있다면, 이는 정답 문장의 answerIndex 위치와 녹음 결과의 spokenIndex 위치에서 시작했을 때의 최대 매칭 개수라고 볼 수 있다.

계산 방식은 크게 두 가지다.

scoreTable[answerIndex][spokenIndex] =
  answerTokens[answerIndex].comparable === spokenTokens[spokenIndex].comparable
    ? scoreTable[answerIndex + 1][spokenIndex + 1] + 1
    : Math.max(
        scoreTable[answerIndex + 1][spokenIndex],
        scoreTable[answerIndex][spokenIndex + 1],
      );

두 단어가 같다면 현재 위치에서 1점을 얻는다. 그리고 정답과 녹음 결과를 모두 한 칸씩 뒤로 보낸 위치의 점수를 더한다.

scoreTable[a][s] = scoreTable[a + 1][s + 1] + 1;

반대로 두 단어가 다르다면 현재 위치에서는 점수를 얻지 못한다. 대신 두 선택지 중 더 나은 미래를 고른다.

• 정답 단어 하나를 건너뛰었을 때의 점수
• 녹음 결과 단어 하나를 건너뛰었을 때의 점수

이 중 더 큰 값을 현재 위치에 저장한다.

여기서 표를 뒤에서부터 채우는 이유도 있다. 앞에서부터 비교 결과를 추적하려면, 현재 위치에서 어느 쪽으로 이동하는 것이 더 유리한지 이미 알고 있어야 한다. 그래서 끝 지점부터 앞으로 오면서 미래 점수를 미리 계산해두는 것이다.

이 표가 완성되면, 이후 실제 비교 결과를 만들 때 일종의 나침반처럼 사용할 수 있다.

두 번째 단계는 점수표를 따라가며 차이를 기록하는 것이다

미래 점수표가 만들어졌다면 이제 실제 비교 결과를 만들어야 한다.

이 단계에서는 정답 문장과 녹음 결과를 앞에서부터 걸어가며 다음 세 가지 중 하나를 기록한다.

• 두 단어가 같으면 그대로 맞은 단어로 기록한다.
• 정답 쪽 단어를 건너뛰는 것이 유리하면 사용자가 해당 단어를 빠뜨린 것으로 기록한다.
• 녹음 결과 쪽 단어를 건너뛰는 것이 유리하면 사용자가 불필요한 단어를 말한 것으로 기록한다.

흐름을 단순하게 적으면 다음과 같다.

현재 정답 단어와 녹음 결과 단어를 비교한다

1. 두 단어가 같다
   - 맞은 단어로 기록한다
   - 정답 위치와 녹음 결과 위치를 모두 한 칸 이동한다

2. 두 단어가 다르다
   - 정답 단어를 건너뛰었을 때의 미래 점수와
     녹음 결과 단어를 건너뛰었을 때의 미래 점수를 비교한다
   - 정답을 건너뛰는 쪽이 유리하면 누락으로 기록한다
   - 녹음 결과를 건너뛰는 쪽이 유리하면 추가 입력으로 기록한다

여기서 한 가지 규칙이 필요하다. 두 방향의 미래 점수가 같다면 어느 쪽을 먼저 건너뛸 것인가?

현재 구현에서는 정답 쪽을 먼저 건너뛰는 방식으로 볼 수 있다. 즉, 같은 점수라면 먼저 “정답 단어를 사용자가 빠뜨렸다” 라고 기록한다.

이 규칙은 작아 보이지만 결과 형태에는 영향을 준다. 같은 점수에서 정답 쪽을 먼저 건너뛰면, 이후 녹음 결과 쪽 단어가 추가 입력으로 붙으면서 자연스럽게 “누락 + 추가” 형태가 만들어진다. 그리고 이 둘을 후처리 단계에서 “잘못 말한 단어” 로 합칠 수 있다.

실제 예제로 흐름을 따라가보자

다시 아래 예제를 기준으로 보자.

const answerTokens = ["나는", "밥을", "먹었다"];
const spokenTokens = ["나는", "빵을", "먹었다"];

처음 위치는 양쪽 모두 0번 인덱스다.

정답: "나는"
녹음 결과: "나는"

두 단어가 같다. 따라서 맞은 단어로 기록하고 양쪽 위치를 모두 한 칸 이동한다.

{ type: "same", answer: ["나는"], spoken: ["나는"] }

다음 위치에서는 아래 두 단어를 비교한다.

정답: "밥을"
녹음 결과: "빵을"

두 단어가 다르다. 이제 미래 점수표를 확인한다.

• 정답의 밥을 을 건너뛰면, 이후 먹었다 를 맞출 가능성을 본다.
• 녹음 결과의 빵을 을 건너뛰면, 이후 먹었다 를 맞출 가능성을 본다.

원문 예시 기준으로 두 방향의 점수가 같기 때문에 정답 쪽을 먼저 건너뛴다. 즉, 밥을 을 사용자가 빠뜨린 단어로 기록한다.

{ type: "missing", answer: ["밥을"], spoken: [] }

이제 정답 위치는 먹었다 로 이동했지만, 녹음 결과 위치는 아직 빵을 에 머문다.

정답: "먹었다"
녹음 결과: "빵을"

여전히 두 단어가 다르다. 다시 미래 점수표를 본다.

이번에는 녹음 결과의 빵을 을 건너뛰면 그 다음에 먹었다 를 맞출 수 있다. 따라서 빵을 은 사용자가 추가로 말한 단어로 기록한다.

{ type: "extra", answer: [], spoken: ["빵을"] }

마지막으로 양쪽 모두 먹었다 를 바라본다.

정답: "먹었다"
녹음 결과: "먹었다"

두 단어가 같으므로 맞은 단어로 기록하고 비교가 끝난다.

{ type: "same", answer: ["먹었다"], spoken: ["먹었다"] }

이 시점의 원시 비교 결과는 다음과 같다.

[
  { type: "same", answer: ["나는"], spoken: ["나는"] },
  { type: "missing", answer: ["밥을"], spoken: [] },
  { type: "extra", answer: [], spoken: ["빵을"] },
  { type: "same", answer: ["먹었다"], spoken: ["먹었다"] },
]

여기까지는 아직 “잘못 말한 단어” 라는 결과가 직접 나오지 않는다. 정답에만 있는 단어와 녹음 결과에만 있는 단어를 각각 기록했을 뿐이다.

마지막 단계는 사람이 이해하기 쉬운 결과로 합치는 것이다

회화 연습 화면에서 사용자에게 보여주고 싶은 것은 보통 원시 비교 결과가 아니다.

밥을 은 누락이고 빵을 은 추가라고 따로 보여줄 수도 있지만, 실제 사용자가 이해하기에는 밥을 을 빵을 로 잘못 말했다고 보여주는 편이 더 자연스럽다.

그래서 마지막 단계에서는 인접한 누락과 추가를 하나로 합친다.

{ type: "missing", answer: ["밥을"], spoken: [] },
{ type: "extra", answer: [], spoken: ["빵을"] },

이 둘은 같은 위치 주변에서 정답과 녹음 결과가 서로 어긋난 상태라고 볼 수 있다. 따라서 사람이 보기 쉬운 형태로 바꾸면 아래처럼 된다.

[
  { type: "same", answer: "나는", spoken: "나는" },
  { type: "changed", answer: "밥을", spoken: "빵을" },
  { type: "same", answer: "먹었다", spoken: "먹었다" },
]

개인적으로 이 구조가 좋은 이유는 단계별 책임이 나뉘기 때문이다.

• 먼저 공통 단어 흐름을 계산한다.
• 그 흐름을 기준으로 원시 차이 결과를 만든다.
• 마지막으로 화면에 보여주기 쉬운 형태로 합친다.

처음부터 모든 판단을 한 번에 하려고 하면 조건문이 복잡해질 가능성이 크다. 반대로 이렇게 나누면 알고리즘이 담당하는 영역과 화면 표시를 위해 다듬는 영역이 분리된다.

구현할 때 조심해야 하는 부분

가장 먼저 봐야 할 것은 실제 비교 기준이다.

화면에 보여주는 단어와 알고리즘이 비교하는 단어가 항상 같을 필요는 없다. 예를 들어 화면에는 원래 텍스트를 보여주더라도, 비교할 때는 공백, 대소문자, 특수문자, 발음 정규화 등을 반영한 값을 사용할 수 있다.

그래서 각 토큰에 원본 값과 비교용 값을 분리해두면 좋다.

{
  text: "밥을",
  comparable: "밥을"
}

이렇게 해두면 렌더링에는 text 를 사용하고, 알고리즘 비교에는 comparable 을 사용할 수 있다. 회화 서비스처럼 음성 인식 결과를 다룰 때는 이 분리가 꽤 중요할 수 있다.

두 번째는 같은 점수에서의 선택 규칙이다.

미래 점수가 같을 때 정답 쪽을 먼저 건너뛸지, 녹음 결과 쪽을 먼저 건너뛸지에 따라 원시 비교 결과의 모양이 달라질 수 있다. 특히 같은 단어가 반복되는 문장에서는 LCS 가 하나로만 정해지지 않을 수 있다.

이 경우 어떤 결과가 사용자에게 더 자연스럽게 보이는지까지 고려해야 한다. 단순 알고리즘 문제가 아니라 피드백 UI 의 문제이기도 하다.

세 번째는 성능이다.

LCS 테이블은 정답 토큰 수와 녹음 결과 토큰 수를 곱한 만큼의 공간을 사용한다. 시간복잡도와 공간복잡도 모두 대략 O(n * m) 이다.

짧은 회화 문장을 비교할 때는 큰 문제가 아닐 가능성이 높다. 하지만 긴 대화문 전체를 한 번에 비교한다면 표의 크기가 빠르게 커진다. 이 경우에는 문장 단위로 먼저 나누거나, 비교 토큰 수를 제한하거나, 다른 diff 전략을 섞는 식의 고민이 필요하다.

정리하자면

회화 녹음 결과와 실제 정답을 비교할 때 중요한 것은 단순히 같은 인덱스의 단어를 비교하는 것이 아니다.

사용자가 단어를 하나 빠뜨리거나 중간에 불필요한 단어를 넣는 순간, 인덱스 기반 비교는 쉽게 무너진다. 그래서 먼저 두 문장 사이에서 유지되는 단어 흐름을 찾아야 한다.

이때 LCS 를 사용하면 기준이 꽤 명확해진다.

• 공통 흐름에 들어간 단어는 맞게 말한 단어로 본다.
• 정답 쪽에만 남은 단어는 빠뜨린 단어로 본다.
• 녹음 결과 쪽에만 남은 단어는 추가로 말한 단어로 본다.
• 인접한 누락과 추가는 잘못 말한 단어로 합쳐 보여줄 수 있다.

처음에는 단순한 문장 비교처럼 보였지만, 실제 회화 연습 서비스에서 사용자에게 납득 가능한 피드백을 주려면 생각보다 많은 판단이 필요했다. 그 기준점으로 LCS 를 두면, 비교 과정과 결과 가공 과정을 꽤 안정적으로 분리할 수 있다.