검색어와 일치하는 인덱스 -> 검색어로 시작하는 인덱스

[namjals]

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

기존 방법의 경우 속도는 빠르지만 "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

[namjals]

결과 (Trie vs Dictionary)

1. 인덱싱

• 약 4MB의 명사 문서를 인덱싱하는데 걸리는 시간
• Dictionary
  1.51 s ± 66.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
• Trie
  19.8 s ± 291 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
• 약 13배 느림 (19.8 s/ 1.51 s).

2. 검색

• 다음 9개의 단어 검색하는데 걸리는 시간
  words = ['프로', 'c++', 'c#', 'c', '프로그래밍', '야근', '하드웨어', '저수준', '포프']
• n : 인덱스 단어 수, m : 검색 단어 길이
• Dictionary
  -. 검색어와 인덱스가 일치하는 검색, O(1)
  806 µs ± 13.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
  -. 검색어로 시작하는 인덱스 검색, O(n)
  29 ms ± 482 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
• Trie
  -. 검색어로 시작하는 인덱스 검색, O(m)
  1.42 ms ± 20 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
• 약 20배 빠름 (29 ms/1.42 ms).

3. 결론

• Trie가 Dictionary 대비 인덱싱은 13배 느리고 검색은 20배 빠르다.
• 문서의 양이 적을 때는 Dictionary, Trie의 검색 속도는 체감상 차이가 안난다.
• 테스트 단계에서는 인덱싱이 빠른 Dictionary를 사용하고 실 사용 단계에서는, 문서의 양이 많아지면 Trie를 고려해보자.