ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 트라이 자료구조Trie datastruct
    Discrete mathmatics and Problem Solving/11 트리 2018. 1. 12. 19:21

    Trie Introduction

    트라이는 자료를 찾는데 특화된 자료 구조이다. 트라이(Trie)의 어원은 retrieval (찾는다)의 중간글자 trie에서 유래되었다.

    트라이 자료구조는 종종 radix tree, prefix tree라고도 불린다. 앞 문자를 기준으로 차차 트리의 자식 vertex로 한글자씩 진행해 나가기 때문이다. 잘 이해하지 못 해도 다음 그림을 보면 이해할 수 있다.

    아래의 그림은 to, tea, ted, ten, a, in, inn 7 글자에 대해 트라이 자료구조로 만들어 본것이다. 위키피디아에서 퍼왔다.

     

    이렇게 트라이 자료구조를 만드는 것은 내가 저런 단어들을 가지고 있어요~
    라는 뜻과 같다. 우리가 구현할 트라이 자료구조는 위 그림과는 좀 다르다.

    차차 더 읽어가면 트라이 자료구조에 대해좀 더 많은 정보를 볼 수 있을 것이다.


    트라이 자료구조를 이용하면 M 길이의 문자열을 검색을 하는데 O(M) 시간 복잡도를 가진다.

    이게 얼마나 효율적이냐면, 위에 상황과 같이 내가 7글자를 가지고 있다고하자.

    to
    tea
    ted
    ten
    a
    in
    inn

    내가 이런 글자들을 가지고 있는데, tem이라는 글자를 찾는다고 해보자.
    (stem에서의 tem을 찾는 부분문자열이 아닌 tem 단어자체를)

    나같은 초보자는 결국엔 

    for i 1 ~7
        if( !strcmp( my[i], "tem") ) printf(" find! ");

    이렇게 할 것이다. 이런경우 시간복잡도는 O( n * m ) 이다. (n은 내가 가진 갯수, m은 문자열의 길이)


    그렇게 나쁜 시간복잡도가 아닌데? 내가 가지고 있는 단어가 3,000만개라고 해보자. 그리고 단어의 길이가 8이라고 하면 수행복잡도는 2억 4천이다. 연산속도는 2초를 넘는다. (1억을 1초로 가정했을때)

    그러나 트라이 자료구조를 이용하면 수행복잡도는 8이다. 캐사기당. 아직 어떻게 계산하는지는 모르지만 사기라고 와닿는다. 하지만 위 트라이 트리처럼 트라이 자료구조를 생성해내야 하므로 용량을 많이 잡는다는 trade off 가 있다.


    Trie Implementation In C

    C로 하지만, ㅡ.ㅡ.... 그래도 이해하는데 상당한 도움이 될겁니다.,, 짜루짜루 진짜루

    (용서받기위해 귀여운 짤 투척)



    이제 트라이 자료구조를 생성해보자.

    가장 먼저 해야하는 것은, 링크드 리스트를 만드는 것이다. 
    링크드 리스트에 사용되는 구조체는
    "저장 문자열에 들어올수 있는 가능성있는 문자 원소 개수a~z, A~Z, a~zA~Z 크기만큼의 노드주소"
    "해당 노드가 단어의 끝인지 체크 변수"

    의 정보를 가지고 있다. 이제 이 두가지에 대해서 자세히 설명하고자 한다.


    트리는 보통, 해당 vertex의 키 값과 자식 vertex에 대한 정보를 가지고 있다.

    위의 코드에서 보듯이 링크드 리스트에서, 노드의 자식 들의 정보는 node *child[Alphabet_size]에 담기고 트리의 키값은 end에 담긴다. 우선 child에 대해서 살펴보자.


    이 node 구조체를 바로 사용한다고 하면 다음과 같은 그림을 연상할 수 있다. (편의상 트리처럼그렸다. 실제론 링크드 리스트이겠지만)


    각 노드는 최대 26개까지의 자식 노드에 대한 주소를 가지고 있다. 왜 하필 26개일까? 난 예제로 소문자 알파벳 사전을 만들것이기 때문이다. (대문자여도 상관없음) 그림에선 child를 빨간동그라미로 으로 표현하였다.


    방금 내가 한 말에서 유추해보건데, 이 노드 한개는 한 알파벳과 같다라고 생각될 것이다. 그렇다면 트리의 depth는? 저장되거나 찾아야 할 문자열의 인덱스를 뜻한다.


    그러니까  소문자 알파벳a~z만을 사용해서 길이 3의 모든 단어를 저장한다고 하자.  그렇다면 트리의 모양은 아래와 같이 된다. 트리의 depth는 최대 3이다. 아주... 아주 멋지다. gorgeous!


    이 그림을 보면 생성한 트라이 자료구조에서 왜 시간 복잡도가 "찾으려는 단어의 길이" 만큼만 나오는지 대충 이해가 간다. 그냥 문자열을 따라가기만 하면되기 때문이다.

    한번 위 트라이 자료구조에서 단어를 탐색하는데 시뮬레이션 해보자. 

    나는 다음과같은 문자열을 가지고 있다.

    그렇다면 트라이 자료구조는 다음과 같이 정확히 생성된다. 다음과 같다. 정확하게.

    내가 "ban"를 찾는다면, root 노드에서 b에 해당하는 주소를 가져오고, 그곳으로 이동한다. 

    잠깐, 그런데 내가 가진 단어 집합에서 'b'로 시작하는 단어가 없다. 라면 root 노드에서 b에 해당하는 주소가 없을것이다 .(NULL, 즉 0 일것이다.) 만약 있다면 우리는 root 노드에서 b에 해당하는 주소를 받아 그곳으로 이동한다. 우리는 이제 첫글자가 b에 해당하는 노드로 이동했다. 아래의 그림에서 노란색으로 색칠한 것이다. 

    이렇게 해서 해당 노란색 노드에서 다시 a에 해당하는 주소를 찾는다. 그리고, 그뒤 그 노드로 이동한 뒤 다시 n에 해당하는 주소를 찾는다.  ban 문자열의 길이 만큼 내려왔으면, 즉 3만큼 내려왔으면, 해당 노드의 키값 변수 "end"가 1인지 체크한다. 1이면 해당 글자가 있다는 것이다. (해당 노드의 키값"end"변수를 설정하는 것은 insert 함수를 설명할 때 할 것이다.) 그렇다면 있다고 반환한다.

    만약 "ba"에 해당하는 문자열을 찾는다면, 우리의 기존 단어에는 ba가 없으므로 없다고 반환해야한다. ba로 가는 경로가 있더라도 ("ban"때문에) "ba" 문자열 길이만큼 이동해 a에 도착하더라도, 해당 노드의 키값이 0일 것이다. 

    따라서, 내가 가진 사전에서 특정 문자열 S를 찾을 때는 root 노드에서 최대 S 길이만큼 노드 이동을 한다. 만약 root서부터 문자열 S[0]에 해당하는 노드 주소가 없을 경우에는 그것을 체크하는 비교연산 1만큼 하겠지만.


    이로써, 내가 가진 단어에서 특정 단어를 찾는데에 시간복잡도가 찾을 문자열의 길이 m만큼 걸린다는 것을 설명했다. 내가 가진 단어를 트라이 자료구조에 삽입하는 Insert나, 찾는 search 또한 시간복잡도가 쿼리를 날리는 문자열의 길이 m만큼 걸린다 는 것을 이해하는 데 도움이 되었으면 한다. 삭제는 조금 더 걸린다. c*m, 여기서  c는 문자열이 가질 수 있는 모든 문자의 수이다.



    Trie Implementation In C 진짜로!!

    이제 정확하게 소스를 써내려보겠다.


    node for Trie data structure

    각 노드는 그 해당 문자가 문자인지 체크하는 word 변수 말고는 키값이 없다. 여기서 무심코 넘어갈 수 있겠지만, 정말 naive한 트라이구조는 해당 노드가 어떤 문자인지 저장하고 있지 않을 수 있다. 사실 저장할 필요까지 없다는 것이 핵심이다. 정말 naive 한 트라이 구조는 해당 문자와 매핑되는 0<= ( a~z)-'a' <=25 child 에 대한 주소만 가지고 있으면 된다. 이 정도로 설명해도 역시 직접 코드를 보는게 제일 이해가 빠르다, 빠르게 다음 소스로 넘어가보자.

    이제 node를 생성하는 함수를 작성해보자.

    모두 0으로 초기화해준다. 

    이렇게 선언하고 난뒤, main 함수로 가서 root 노드와 나의 단어 사전을 만들어 줄 것이다.



    Trie Insert

    그다음 root 노드서부터 차례차례 내 문자열을 트라이자료구조처럼 삽입할것이다. 삽입함수를 작성해보자.

    삽입함수는 총 전달반은 문자열 만큼 node 삽입을 반복한다. 앞에서 설명한 것을 이해하면 당연한것이다. 반복을 끝마친뒤 마지막 node는 word 멤버 변수 1로 저장한다.

    그런다음 우리는 main 함수에서 다음 줄을 추가 할 수 있다.

    이렇게 하면 우리는 트라이 자료구조에 정확히 모든 단어를 삽입했다.



    Trie ShowAll

    정확히 되었는지 모른다면, 트리에 모두 저장된 단어를 출력하는 방법을 살펴보겠다. 이것은 트리 탐색을 통해서 수행할 수 있다. 트리를 완전탐색하면서 해당 노드의 멤버변수 word가 1이면 출력하는 것으로 해보자. 다음과 같이 작성할 수 있다.


    만약 해당 노드의 word가 1이면 출력을한다. 그리고 해당 노드의 주소가 있는 곳을 골라 그것을 참조한 문자열 변수에 depth 인덱스에 추가한다. 그리고 depth+1에 null 문자를 추가하고, 다음 노드로 이동한다.  왜 노드 이동전에 문자열을 조작해주냐면, 기억날지 모르겠지만 해당 노드는 오로지 해당 노드가 글자의 끝인지 체크하는 word만을 가지고 있게 했기 때문이다. 어쨌든 가지게 해봤자, 참조하는 문자열 주소에 추가하는 동작은 같기에, 딱히... 불편한점은 없다.

    그다음 메인 함수에서 다음과 같이 소스를 작성하여 전부 찾아보자.


    printHead 함수는 걍 상수문자열을 받아서 깔끔하게 보여주는 출력함수이다. showtree 함수를 실행하면 다음과 같다.



    Trie Search

    이제 우리가 가진 사전에서 특정 문자열이 있는지 확인하자. 탐색하는 함수는 다음과 같다. 문자열의 길이만큼 root에서부터 문자열의 depth 인덱스에 존재하는 문자에 해당하는 node로 이동한다. 그리고 문자열의 길이만큼 이동해서 그 노드의 멤버변수 word가 1일경우에만 1을 반환한다. 만약 노드를 이동하는 중간에 문자열의 depth 인덱스에 있는 그런 문자에 해당하는 node가 없을 경우에는 0을 반환한다.


    메인 함수에서는 다음과 같이 호출 할 수있다.



    Trie Delete

    이제 특정 문자열을 삭제해보자. 문자열을 삭제하는 방법은 간단하지만, 약간의 트릭이 필요하다. 왜냐하면 단순히 길이만큼 반복해서 노드를 들어간뒤에 word 멤버변수를 0으로 만드는 것은 꽤 단순한 접근법이지만 확실하다. 왜냐하면 해당 노드의 멤버변수가 0이니까 search나 showtree 함수에서 1을 반환하거나 해당 단어를 보여주지 않을 것이기 때문이다.

    하지만, 메모리 효율성이 좋지않다. 제일 확실히 메모리 측면에서 효율 적인것은 그 단어로 가는 모든 노드를 삭제하는 것이다. 다만, 다른 단어에 종속적인 노드는 삭제하지 않는다. 예로 "blue" "blow" 에서 blue를 삭제하면 딱 "bl"만을 남겨두고 "ue" 에 해당하는 노드만을 삭제해야하 할것이다.

    자, 함수를 작성해보자. 일단 첫번째 문자에 해당하는 노드가 존재하면, 재귀적으로 계속 아래로 들어간다.  문자열의 길이만큼 들어갈수만 있다면야, 결국 문자열의 길이에 도착해서는 그 해당 노드가, 다른 단어에 종속적인 가를 체크한다. 종속적이라면, 다른 child의 주소를 가지고 있느냐에 결정된다.

    다른 단어에 종속적이라면 return 0을 하자. 이런 결과값은 다음 소스와 같이. delete 의 상위 delete 함수로 반환된다. 그래서 자식 delete의 반환값이 1이라면 해당 노드를 메모리 해제해줘도 된다. 메모리를 해제해준뒤, 해당 자식에 대한 주소를 0으로 할당한다. 그뒤 해당 부모 노드도 똑같이 종속적인지 아닌지 체크를 한다. 만약 종속적이지 않다면, 우리 이 노드도 삭제해줘도 된다. 따라서 return 1을 해준다. 그렇다면 이 delete 함수는 자신의 위 delete 함수에게 1을 반환하여 또 종속성 체크를 하게된다. delete 함수의 나머지 부분은 다음과 같다.



    recommendation feature with Trie

    추천어 기능을 트라이로 줄건데, 이것은 showtree와 크게 다를바없다. 내가 입력한 검색어까지만 노드를 이동하고, 그 뒤에 해당노드를 showtree의 인자로 넘겨준다.  showtree함수의 인자였던 node는 root 노드였음을 기억하자. 그렇다면 이번엔 내가 입력한 노드에서부터 모든 단어를 검색해서 제시해준다.


    메인함수에서는 다음과 같이 호출할 수 있다.


    모든 함수의 실행결과는 다음과 같다.



    전체적인 소스는 다음 주소에서 확인할 수 있다.

    https://github.com/ingyeoking13/algorithm/blob/master/tistory/tree/trie.c


    추가


    제 개인적인 필요에 의해서 시간 효율적인 트라이에 대해서 기술한 포스트가 있습니다.
    트라이 자료구조를 보러 오신 분들이 많아서 왠지 한번 보면 좋을것 같아 공유합니다.

    아래 링크의 2번 자료를 보시면됩니다. 동적할당이 사용되지 않습니다. 
    트라이에서 각 노드가 문자열 내의 문자들로 이루어져있고, 그 문자 하나 하나가 고유하다는 것에서 착안하여 미리 정적인 변수로 사이즈를 정하고 들어가는 것이 있습니다.

    동적할당을 사용하지 않기 때문에 시간적 성능이 눈에띄게 훨씬 좋습니다만, 사전에 들어갈 문자열 길이와 단어 갯수를 정적으로 주는 것은 보통 과제/ 알고리즘 문제 밖에 없으니 적극적으로 사용할 수 없는 부분은 있습니다.
    사용에 있어서도, memory allocation free 하는 것이 없기때문에 각 Testcase마다 새로운 사전을 생성하는데도, 동적할당이 없는 트라이를 사용하는것이 성능이 훨씬 훨씬 좋습니다.
      
       

    'Discrete mathmatics and Problem Solving > 11 트리' 카테고리의 다른 글

    Segment Tree with Lazy Propagation  (0) 2019.03.10
    AVL tree  (0) 2018.10.28
    B+ trees  (0) 2018.10.27
    Binary Search Tree, 이진 검색 트리  (0) 2018.10.25
    이진 힙과 힙정렬 binary heap && heap sort  (0) 2018.02.06
    트라이 자료구조Trie datastruct  (2) 2018.01.12

    댓글 2

    • 지나가다가 2019.08.31 00:30

      C로 간단하게 Trie 예제를 올려 주셔서 감사합니다!!^^
      예제 중에 delete 부분에서 chk가 1이 아닌 경우 바로 return 1을 하면 안되고, word가 아닐 경우까지 함께 체크 후에 delete해야 될 것 같아서 글 남겨요~^^

Designed by Tistory.