AncomWiki

다듬이: 단어 정렬 및 매핑 알고리즘 개선

Properties1
description이 노트는 음성 인식 결과나 텍스트 입력에서 발생하는 단어 단위의 정렬(alignment) 및 매핑 문제를 해결하기 위한 알고리즘 개발 과정을 기록한 것이다. 기존 알고리즘이 단어의 추가, 삭제, 합쳐짐, 띄어쓰기 변화 등에 취약하여 타임스탬프 손실이나 잘못된 매핑이 발생하는 문제를 지적한다. Needleman-Wunsch 알고리즘, Trie 구조, 유사도 점수(similarity score), 인덱스 차이(index_dif…

39 min read

다듬이: 단어 정렬 및 매핑 알고리즘 개선

Source

  • Field Notes/ReturnZero/Daily Notes/Day 646. 2023-04-07.md

Summary

이 노트는 음성 인식 결과나 텍스트 입력에서 발생하는 단어 단위의 정렬(alignment) 및 매핑 문제를 해결하기 위한 알고리즘 개발 과정을 기록한 것이다. 기존 알고리즘이 단어의 추가, 삭제, 합쳐짐, 띄어쓰기 변화 등에 취약하여 타임스탬프 손실이나 잘못된 매핑이 발생하는 문제를 지적한다. Needleman-Wunsch 알고리즘, Trie 구조, 유사도 점수(similarity score), 인덱스 차이(index_diff) 등을 활용한 다양한 접근법을 시도하며, 특히 숫자나 특수한 토큰이 매핑되지 않아 -1 인덱스가 발생하는 에러 케이스와 병렬화 성능 저하 문제를 디버깅하고 있다.

Key Points

  • 기존 알고리즘의 한계: 단어 순서 변경, 추가, 삭제 시 타임스탬프 손실 및 매핑 오류 발생
  • 목표: original_words와 target_words 간의 정확한 alignment 생성 (합쳐짐, 분리, 삭제, 수정 케이스 포함)
  • 시도된 방법: Needleman-Wunsch 알고리즘 적용, Trie 기반 매칭, 유사도 및 인덱스 차이 기반 스코어링
  • 주요 문제점: 숫자/특수 토큰 매핑 실패(-1 인덱스 발생), 포지셔널 정보 왜곡, 병렬화 시 성능 저하
  • 해결 방향: -1 인덱스 처리 로직 개선, reconstruct 단계에서의 에러 핸들링, 단일 스레드 실행 선호

그래프 뷰

백링크