플젝을 열심히 구현하다 보면
잠시 주위를 환기하기 위해 관련된 유사 주제들로 눈을 돌리는 것도 도움이 되는 것 같다.
이번에도 사용자가 서비스에 등록한 문서들을 관리하기 위해 문자열 관리를 좀 공부하던 중
개발자 테스트에도 단골로 출제된다는 Trie자료형이라는 것을 처음 알게 되었다.
Trie 자료형이란?
Tree 자료구조를 응용해 문자열 중 중복되는 부분을 한번만 저장하도록 정리,
많은 양의 문자열을 저장할 때에 탐색 속도와 메모리 사용량을 개선하는 데 사용 되는 기법!
파이썬에서 이 트라이 자료형을 쉽게 사용할 수 있도록 구현된 코드가 있는지
웹을 이곳저곳 뒤지던 중 눈이 번쩍 뜨이는 코드를 찾았다.
자료형 구현 코드
def make_trie(*words):
root = dict()
for word in words:
current_dict = root
for letter in word:
current_dict = current_dict.setdefault(letter, {})
current_dict[_end] = _end
return root꽤 많은 사람이 Trie를 파이썬과 다양한 다른 언어로 구현해놨지만 이 코드만큼 간결하고
기본 데이터 타입의 동작원리를 효과적으로 이용한 것이 없었던 것 같다.
물론 이 함수에서 구현된 방식을 사용하면 Dict자료형을 사용해서
자료 저장시 필요한 용량 외에 연산과 관련된 부분은 그리 효율화되지 않는다는 게
함정이지만, Dict라는 자료형을 이렇게도 Navigating할 수 있구나 라는 점에서
잘 봐뒀다가 써먹을 만한 코드라고 생각했다.
실제 사용 결과
위 함수로 생성한 Trie 구조는 아래와 같다
make_trie('hi', 'he', 'hip', 'help', 'hell', 'hello', 'dream', 'file')
코드 실행 결과 :
자기가 _end 변수로 정한 문자열 표시를 만난 시점에서
해당 브랜치에 있는 키를 전부 이으면 단어가 완성된다.
효과
dream과 file은 공통되는 문자가 없기 때문에 효율화가 일어나지 않지만
h로 시작하는 단어들은 전부 매우 효과적으로 Depth별 알파벳 중복없이 저장된 것을 알 수 있다.
~Fin~
