AncomWiki

Alignment 설명

Properties1
description입력 텍스트의 단어를 타임스탬프가 포함된 word_info 와 매핑하는 Alignment 알고리즘의 설계와 시간 복잡도 분석을 다룹니다. Trie 구조를 활용한 검색 전략과 중복 처리 방식을 제시하며, 전체 연산 복잡도를 O((O+T)L + O * MlogM) 으로 도출합니다.

37 min read

Alignment 설명

Source

  • Field Notes/ReturnZero/Daily Notes/Day 651. 2023-04-12.md

Summary

입력 텍스트의 단어를 타임스탬프가 포함된 word_info 와 매핑하는 Alignment 알고리즘의 설계와 시간 복잡도 분석을 다룹니다. Trie 구조를 활용한 검색 전략과 중복 처리 방식을 제시하며, 전체 연산 복잡도를 O((O+T)L + O * MlogM) 으로 도출합니다.

Key Points

  • 목표: 입력 텍스트 단어를 word_info(타임스탬프) 에 대응시키는 Alignment
  • 전략: Trie 구조에 word_info 단어 저장 및 노드별 word_info_index 로 중복 처리
  • 시간 복잡도: Trie 생성 O(TL), 탐색 및 유사도 계산 O(OL + MlogM), 전체 O((O+T)L + O * MlogM)

그래프 뷰

백링크