트라이(Trie)알고리즘

트라이(Trie)

 

트라이란 문자열 검색을 빠르게 할 수 있는 알고리즘이다. 예를 들어 영어사전이 있을 때 특정 단어가 있는 지 빠르게 찾을 수 있다.

문자열을 특정 키값으로 변환해서 그 값으로 찾는 방법인 해시 테이블을 대체하기 위해 트라이를 사용할 수 있다. 불완전한 해시 테이블의 최악의 검색속도는 모든 데이터를 다 확인하는 것으로 O(N)이지만 트라이를 사용하게 되면 문자열 길이 만큼의 O(M)의 속도가 걸리기 때문에 훨씬 더 빠르게 적용이 될 수 있다.  

 

 

보통 트라이 알고리즘을 사용할 때 고려해야할 점이 단어의 길이, 그리고 파생되는 노드 child개수다. 위에 영어사전으로 예를 들었는데 영어는 알파벳이 26가지로 child 노드는 26개를 갖고 있을 수 있다. 전화번호 목록같은 경우도 0부터 9가지 10가지의 수를 가지고 있을 수 있다.

이처럼 적은child개수를 가지고 있는 데이터 구조일 경우에 사용하는 것이 유용하다. 만약 차수가 그 이상으로 크고, 단어길이가 길면 그만큼 메모리 낭비가 많고, 검색 속도가 느려질 수 있다.

 

위의 그림에서 보여주는 것은 알파벳을 트라이구조를 활용해 단어를 찾는 과정 그림을 보여준다. 실제 각 노드가 가지는 차수는 26개로 Root에서 접근해 내가 찾고자 하는 단어가 있는지 확인할 수 있다.

 

트라이를 구현하기 위해서 두가지의 함수 구현이 필요하다. 데이터를 삽입하는 함수와 데이터를 찾는 함수다. 

 

그림과 같이 문자열을 기준으로 단어를 입력하고, 그 단어를 찾는 함수를 구현했다.

 

[insert(char *arr)]

?

1 2 3 4 5 6 7 8 9 10 11 12

void insert(char *arr) {       if (*arr == '\0')finish = true; //문자끝을 알려준다.     else {         int cur = *arr - 'a';         if (next[cur] == NULL) {             next[cur] = new Trie();         }         next[cur]->insert(arr + 1); //다음문자로     } }

 

데이터를 삽입하는 기능의 함수다.  매개변수는 삽입하고자 하는 문자열을 받고, 그 문자를 찾아가면서 차수를 열어준다.  

 

1) cur는 문자열의 번호를 가리킨다.(소문자 영어단어를 기준으로 했을 때)

 

2) next[cur]가 0이라면 객체를 생성해서 길을 터준다.(없던 길을 새로 만들어준다고 생각하면 된다.) 

 

3)그리고 그 다음문자로 이동한다. arr+1은 그 다음 문자로 이동한 것을 말한다. 

 

4) 1)~3)을 문자가 끝날 때까지 반복하고, 문자열이 끝나면, finish를 true로 반환하고 리턴한다.

 

[find(char *arr]

?

1 2 3 4 5 6 7 8 9

bool find(char *arr) {     if (*arr == '\0')return false;       if (finish) return true; //중간에 끝나는 단어있음       int cur = *arr - 'a';     return next[cur]->find(arr + 1); }

 

문자를 찾는 기능을 하는 함수다. 여기서의 find함수는 문자열이 포함되어 있는지를 보고, 포함이라면 true를 반환하는 함수다. 이전에 insert 함수에서 문자열 삽입과정이 끝이 나는 곳에 finish를 true로 켜두었기 때문에 특정 문자를 찾을 때 중간에 finish가 true로 되어 있다면, 포함관계라는 것을 알 수 있다. 

 

이 함수에서는 찾는 문자가 이미 삽입된 문자일 경우에만 쓸 수 있다. 만약 새로운 문자를 확인하게 되면 next[cur]이 널값을 가리키기 때문에 오류를 범하게 된다.

포함관계를 알기 위함이지, 이 문자가 있는 지 확인하는 기능이 아니기 때문에 확인하기 위해서는 next[cur]이 널값인지 먼저 확인을 하고, 널값을 가진다면, 없는 문자가 되기 때문에 false를 반환하는 식으로 변경이 가능하다.

 

이처럼 find는 내가 원하는 데이터를 찾기위해 필요에 따라 변경이 가능하다. 그리고, 문자열 검색에 있어서 활용이 많기 때문에 알아두면 좋은 알고리즘이라고 생각한다. 

 

[Trie 예제]

 

[BOJ]5052번 전화번호 목록

 

[BOJ]5670번 휴대폰 자판

 

 

 

from : https://meylady.tistory.com/23