namjals / youtube_caption_analyzer Goto Github PK

검색어를 인덱스에서 찾을 때,
기존 : 검색어와 인덱스가 일치하는 경우만 반환,
수정 : 검색어로 시작하는 인덱스를 반환

기존 방법의 경우 속도는 빠르지만 "c++"검색 시, "c++11"이나 "c++17"를 검색하지 못함.

인덱스의 단어 수 : n, 검색어 길이 : m일 때,
trie라는 자료구조로 dictionary의 key를 O(n)으로 검색하지 않고 O(1)을 m번한 O(m)으로 검색.
c - + - + : {video1 : 10, video2: 3, video10:22, ...}
c - + - + - 1 - 1 : {video5 : 1, video6: 3, video13: 23, ...}
https://stackoverflow.com/questions/18066603/fastest-way-to-search-python-dict-with-partial-keyword
https://stackoverflow.com/questions/17106819/accessing-python-dict-values-with-the-key-start-characters

위키
https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4