파이썬에서 Trie (트라이) 구현하기
자료구조들어가며: "자동 완성" 기능에 대한 이야기
구글에서 어떤 단어를 검색창에 치면 그 단어로 시작하는 다른 키워드를 보여주는데요, 이런 걸 자동 완성(Autocomplete) 라고 합니다. 자동 완성을 구현 하려면 키워드들을 리스트에 담아서, 유저 인풋이 들어올 때 마다 인풋으로 시작하는 키워드를 리스트에서 빼오면 될 겁니다. 하지만, 만약 550만 개의 글을 갖고 있는 영어 위키백과의 제목들을 가지고 자동 완성을 구현하라고 한다면 (실제 일본 모 회사의 올해 인턴 모집 스크리닝 과제였음 ㅋㅋ) 리스트 따위로는 안 되고, 훨씬 더 효율적인 자료구조가 필요합니다. 오늘 배울 Trie 가 이럴 때 필요한 자료구조입니다.
Trie: 트라이? 트리? 기본적인 개념
사실 Trie 는 트리(Tree) 자료 구조의 일종입니다. 미리 말씀드리자면 Trie 에서 어떤 문자열을 검색할 때의 시간 복잡도는 O(m) 밖에 안 됩니다. (m: 문자열의 최대 길이) 그래서 다른 자료 구조에 비해 문자열을 검색하는 데 특화된 자료 구조임을 알 수 있습니다.
위 그림은 names = ['Joe', 'John', 'Johnny', 'Jane', 'Jack'] 을 Trie 에 삽입한 결과인데요.
각 Node 는
(1) 글자를 갖는 key = 한 글자 (ex. J, A, C, K)
(2) 단어의 마지막 글자인지를 알려주는 flag (Terminal)
로 이루어져 있습니다.
예를 들어 John 의 경우 J > O > H > N 으로 차례대로 Trie 에 삽입이 되었고 마지막 글자 N 의 노드에는 Terminal 이라는 flag 를 박아줍니다. 이 flag 때문에 John 이 한 단어임을 알 수 있습니다.
Johnny 의 경우 John 까지는 이미 노드가 있으니 ( J > O > H > N )원래 있는 노드를 활용하고, John 뒤에 n 과 y를 넣은 다음 y를 마지막 글자로 flag해주면 되는 겁니다.
파이썬에서 Trie 를 구현해볼까요?
첫번째. Node 구현
1. key 필드는 단어의 글자 하나를 담는 데 이용합니다. 영어라면 알파벳만 들어갈 수 있겠죠.
2. data 필드는 사실상 마지막 글자를 나타내주는 flag 입니다. 원래 boolean 형 으로 간단하게 true/false 로 구분할 수도 있지만
저는 마지막 글자인 경우에 단어 전체를 data 필드에 저장하고, 아닌 경우에는 그냥 널로 두려고 합니다. 그 이유는 밑에 구현할 starts_with 메소드 때문인데요, 곧 설명 드리겠습니다.
(즉, Jack 의 경우 J > A > C > K 에서 마지막 글자인 K 노드의 data 필드에만 "Jack" 이 들어가고, 그 외 노드의 data 필드는 널 (None) 으로 놔둡니다.)
두번째. Trie 구현
1. insert(string)
트라이에 문자열 삽입
2. search(string)
주어진 단어 string이 트라이에 존재하는지 여부 반환
3. starts_with(prefix)
주어진 prefix 로 시작하는 단어들을 BFS로 트라이에서 찾아 리스트 형태로 반환
마지막 글자 flag 를 boolean 으로 안하고 data 필드로 한 이유가 바로 이 메소드 때문인데요... 잘 생각해보세요. BFS 로 단어들을 찾을 때 결국 마지막에 우리에게 반환되는 것은 Terminal 노드, 즉 마지막 글자입니다. 그래서 단어 자체를 알려면 BFS 경로를 역추적해야 합니다... 이 과정이 귀찮기 때문에 ㅋㅋ Terminal 노드만 찾으면 BFS 역추적 할 필요 없이 단어가 뭔지 알 수 있도록 data 필드에 전체 단어를 넣어 놓은 것이죠.
위 세 가지만 구현하면 됩니다! 아래는 제가 간단히 파이썬으로 구현해본 Trie 입니다.
(파이썬 전체 코드는 여기를 클릭하면 보실 수 있습니다.)
끝!!
학교 자료구조 수업에서는 비중이 많이 있는 놈은 아니지만, 기술 면접이나 코딩 대회에서 많이 다루어진다고 하니 열심히 공부합시다!! 우리의 핵심 목표는 Trie다 하는 것으로 정신을 차리고 나아가면 취직할 수 있는 에너지가 분산되어 우주가 나서서 도와준다는 그런 마음을 가질 수 있을거다, 그렇게 생각합니다.
'자료구조' 카테고리의 다른 글
파이썬에서 Trie (트라이) 구현하기 (3) | 2017.12.03 |
---|---|
리스트 (List) - 2. LinkedList 구현 (1) | 2017.10.02 |
리스트 (List) - 1. ArrayList 구현 (1) | 2017.10.01 |
[알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법 (2) | 2016.07.05 |
[알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법 (3) | 2016.07.05 |
댓글을 달아 주세요
감사합니다
2017.12.05 18:45좋은 글 잘 읽었습니다. 질문이 하나 있습니다
노드의 children 필드로 굳이 dict 형을 쓴 이유가 있으신가요?
자바나 다른 언어에서 구현을 살펴봤는데 대부분 그냥 배열로 놓는 게 많은 것 같아서요
헉 정말 예리하고 좋은 질문입니다!!
사실 저는 구글에서 만든 pygtrie 를 참고하면서 만들어서... 구글 성님들이 dict형을 썼으니까 저도 그렇게 했다고 시인할 수 밖에 없겠군요 (__)
그래도 곰곰히 생각해봤습니다..
search() 에서 자손들 중에서 key 를 찾을 때의 시간 복잡도와 관련 된 것 같습니다. 어레이는 key 를 찾을 때 시간 복잡도가 O(n) 이지만 딕셔너리/해시맵은 O(1) 로 constant 합니다. 물론 나올 수 있는 문자가 한정이 되어있다면 (예를 들어 알파벳 26자) 어레이나 딕셔너리나 비등비등할 겁니다. 그러나!! 문자열 검색은 영문 알파벳만 있는 것이 아니죠... 예를 들어 한글까지 포함을 해버리면 가능한 문자 개수가 몇 만개가 되어버리잖아요... 아마 이런 이유 때문에 dict 를 쓴 것 아닌가 싶습니다.
안그래도 자손들을 어레이로 구현해 놓은 코드를 보면 대부분 제약 사항으로 a부터 z까지 알파벳만 올 수 있다고 못박아두었더라고요 ㅎㅎ
임정섭
2018.06.23 10:14starts_with 에서 bfs로 찾겠다고 하셨는데, 코드를 보니 dfs로 찾으신 것 같아요!
curr=queue.pop(0) 으로 해야 bfs로 찾는 것 아닐까요??