트라이 (Trie)

• 생략. 검색하면 많이 나옴

• 파이썬에서는 트라이가 정해인 문제도 트라이를 안쓰는 것이 더 빠른 경우가 종종 있다.
  • 트라이를 활용하는 문제 유형은 다양하지만, 기본적으로는 단어들의 접두사들을 갖고서 어찌저찌 해보는 문제들이 대부분인데. 이런 문제들중 다수는 단어들을 정렬한 뒤, 인접한 단어들끼리 비교해보는 식으로도 풀리는 문제들이 많다.
  • 이때, 이 문제의 시간 복잡도가, 트라이로 풀 때는 O(nl)에 트라이를 구축하고, 비교를 O(nl)에 해야하지만, 정렬로 풀 때는 O(nl*logn)에 정렬해서 O(nl)에 비교를 해야 한다고 하자. 즉, 전처리(트라이 구축 vs 정렬)에서만 시간 복잡도 차이가 나고, 비교부분은 동일하다면, 정렬로 푸는 것이 실제로는 보통 더 빠르다.
    • 정렬하는 것이 트라이를 구축하는 것보다 시간 복잡도로는 logn배 만큼 느림에도 불구하고, 보통 더 빠르다.
    • trie에 add할때 연산이 많아서 느린것도 있고. 반면 내장 sort가 c로 구현되어서 워낙 빠른것도 있고.. 문자열에 기수정렬 하면 O(nl)이지만 그냥 O(nl*logn)인 sorted를 쓰는 것이 보통 더 빠른것과 같은 느낌이다.
  • 그래서, 트라이가 꼭 필요한 문제는 제한이 되는 편이다. 뒷단에서의 비교나 이런 작업에서도 트라이를 쓰는 것이 더 빠른 문제에서만, 트라이를 쓸 필요가 있다.
    • 오히려 문제를 풀다보면 문자열보다도 정수의 XOR 연산 용도로 트라이를 쓰는 경우도 많다.
  • 전화번호 목록의 경우, 정렬을 사용해서 푼 코드는 170ms 정도, 트라이는 가장 빠른 코드도 900ms 정도가 걸렸다.
    • 반면 파이썬이 아닌 경우, 예를 들어 c의 경우는 트라이를 쓰는 것이 정렬하는 것보다 더 빨랐다.

• 아이디어는 간단하지만, 디테일한 구현 방식은 꽤나 다양하다.
  • 단어의 끝에 해당하는 노드를 어떻게 표현할 것인가
    • 노드에 단어의 끝일때만 True가 되는 bool 플래그를 만든다. 또는 노드에 단어의 끝일때만 아예 전체 단어를 저장하는 변수를 만든다
    • 끝을 의미하는 특수문자를 추가해서 노드로 만든다
  • 자식 노드들을 a-z까지의 길이 26의 리스트로 할것인가, 딕셔너리로 할것인가
    • 확장성 및 범용성에서는 딕셔너리가 낫다. 트라이에 대문자도 넣어야 한다면? 특문도 널어야 한다면? 이러면 딕셔너리지..
    • 메모리도 딕셔너리가 적게 들 것이다
    • 검색 속도는 리스트가 빠를 것이다.
    • 리스트를 쓰면 노드들을 알파벳 순으로 순회하는 것이 가능하다 (트라이가 자체적으로 radix sort 역할을 해준다)
  • 중복된 단어가 들어오면? 그냥 무시할것인가 카운트를 세어서 저장할것인가. 아니 애초에 중복된 단어를 고려하기는 해야 하나?
  • 어떤 함수를 제공해줘야 하는가??
    • 사실 이게 제일 제각각이다. 트라이라는 아이디어를 갖고서 할 수 있는 작업들이 다양하다보니 어떤 것을 라이브러리가 지원해줘야 하는지를 결정하기가 어렵다
    • add(word) - 트라이를 생성해야 뭐든 할테니 이건 당연히 필요.
    • contains(word), listAllWords() - 어떤 word가 트라이 안에 있는지 체크하고, 트라이 안의 모든 word를 리턴하는 것은 기본적인 기능이지만, 오히려 기본적이어서 저것만 물어보는 문제는 없다. (저것만 물어본다면 그냥 set을 써도 똑같은 시간 복잡도로 처리 가능)
    • listAllWords(prefix), countWords(prefix) - prefix로 시작하는 모든 word의 리스트 / 모든 word의 갯수 리턴. 느낌적으로는 이것이 trie의 핵심 기능같은데..

• 결국 고민끝에 결정해서 구현한 Trie v1.0은 다음처럼 만들어졌다. (코드)
  • 노드에, word_count라는 변수를 둔다. 그 노드에서 끝나는 단어의 갯수이다. 이것이 0인지 1이상인지로 노드가 단어의 끝인지 파악할수도 있다
  • 자식들로의 링크는 딕셔너리에 저장한다
  • 제공할 메소드는 trie로 태깅되어있는 문제들을 몇개 풀면서 필요한 것이 뭔지 확정해본다. 아래의 4문제를 대상으로 했다
    • 가사 검색: trie.getNode(word), node.child_count
    • [3차] 자동완성: trie.prefixes(word), node.word_count, node.child_count
    • 전화번호 목록: trie.getitem(word), node.child_count(또는 node.child_type_count)
    • 휴대폰 자판: trie.words(), trie.prefixes(word), node.word_count, node.child_type_count
      • 또는 trie.nodes(), node.child_type_count, node.child_count 으로 풀 수도 있다
  • 결론은, 노드의 구현을 사용자에게 감추는 것은 너무 힘들고, 함수들이 노드를 리턴해주고 사용자가 노드를 억세스해서 정보를 얻는 식으로 하게 해야 한다. 다음을 구현하면 된다.
    • 노드를 리턴하는 함수들
      • 어떤 prefix에 대응되는 노드를 리턴하는 함수 (trie[prefix])
      • 어떤 word의 각 prefix들에 대응되는 노드를 이터레이트 함수 (trie.prefixes(word))
      • 모든 노드를 이터레이트 하는 함수 (trie.nodes())
      • 모든 단어노드를 이터레이트 하는 함수 (trie.words())
    • 노드의 멤버들
      • 이 노드로 끝나는 단어의 갯수: node.word_count
      • 이 노드로 시작하는 모든 단어의 갯수: node.child_count
      • 이 노드의 자식노드들로의 링크 node.children
        • 이 노드 다음에 오는 글자의 종류의 갯수: len(node.children)

• 그러나 Trie v1.0으로 코드를 제출하다보니 문제가 생겼다. 휴대폰 자판 문제를 푸는데 시간 초과가 발생하는 것. Pypy로는 2408ms에 통과했지만 Python3으로는 5000ms의 시간 제한을 통과하지 못하고 시간 초과가 났다. 한참의 고생을 거쳐 알아낸 것은, 구하려는 값을 계산하는 단계에 들어가기도 전에 트라이를 구축하는 과정에서 이미 시간이 초과된다는 것과, 그것을 해결하기 위해서는 구현을 대폭 수정하는 방법밖에 없다는 것. (멤버로 dict를 갖는 노드 클래스를 따로 만들어서 노드 객체를 생성하다보면 이미 시간 초과가 난다. 통과된 코드들은 아예 그냥 dict자체를 노드로 사용하고 있었다)
• 그래서 아예 싹 갈아 엎고 Trie v2.0 을 다시 만들었다.
  • 가장 핵심은 속도를 위해 노드 클래스를 따로 정의하지 않는다. 그냥 dict를 노드로 써서 해결한다.
    • child_node = node.children['a'] 가 아니라 child_node = node['a'] 이렇게 된다.
  • 그러면 노드가 단어의 끝임을 확인하는 것은 어떻게? 단어마다 단어에 끝에 해당하는 특수문자를 붙이는 식으로 하면 할 수는 있다. 아예, 그 특수문자를 키로 갖는 값을 단어의 갯수로 해버리면, 좀 구리기는 하지만 어찌어찌 단어의 갯수도 처리가 된다
    • word_node = {'a': a_child, 'e', e_child, '***': 3} 뭐 이런식으로 말이다..
  • 그치만 child_count는 어떻게? 이 기능을 제공 안하기에는 이걸 필요로 하는 문제가 많다. 노드에 다시 child_count에 해당하는 키를 갖게 하자니, 이건 너무 편법이 심한 느낌에, 탐색같은 다른 함수를 구현하는 데에도 악영향을 미친다.
    • 사실 속도면에서는 이게 가장 빠르기는 했다..
• 이런 저런 고민끝에 나온 Trie v2.0 최종 구현은,
  • Node는 그냥 정수 인덱스이다. 그 인덱스를 진짜 노드와 매칭시키는 것은, childrens라는 리스트가 그 역할을 한다. 즉, child_node = childrens[node]['a'] 이렇게 트레버스하게 된다.
  • 깔끔하게 객체 기반으로 구현되는 게 아니라 지저분하고, 역참조를 여러번 하면서 가야 되니까 성능이 저하되지만, 이 방법의 장점은 필요한 값들만 리스트로 추가로 제공할 수가 있다는 것.
    • 트라이에는 처음 생성되면 childrens와 word_counts 리스트만 갖고 있다. child_counts를 생성해주는 함수는 따로 뽑아서, 필요한 경우에만 호출해서 쓸수 있게 했다
    • 트라이 구축 단계에서 자동으로 child_counts를 계산했던 것에 비해서, 이 계산을 제외하니까 휴대폰 자판 문제 기준으로 대략 500ms 정도가 단축되었다
      • (물론 child_counts를 트라이 생성 단계가 아니라, 이 후에 노드를 순회하면서 계산하는 데에는 1500ms 정도가 걸리기는 했다)
  • 그래도 어느정도 깔끔하면서 유연한 구조를 유지하면서도 성능이 크게 떨어지는 것은 막은듯한 느낌..

teflib.string.Trie

• 가사 검색
• [3차] 자동완성
• 전화번호 목록
• 휴대폰 자판