TRIE (정적 메모리로 구현)

TRIE 기본 개념은 많은곳에서 자료를 구할 수 있으므로 자세한 설명은 여기에 기록 하지 않습니다.

WIKI 참고 바랍니다.

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

장점

- HASH를 대체할 수 있다.

- 충돌이 일어나지 않는다.

- 사전순 정렬이 되어있다.

단점

- 단순 조회는 HASH보다 느릴 수 있음

- 메모리 사용량이 많음

C언어로 구현한 코드는 map이나 dictionary가 없기 때문에 배열을 이용한 index(문자-'a')로 예제가 되어있습니다.

typedef struct {

int child[ALPHA];

int done;

}trie_type;

Wiki 설명예제 python 코드에서는 Dict 예제로 되어있는점 참고바랍니다.

self.children: Dict[str, Node] = {}  # 문자를 노드로 대응

전체 코드

#include <stdio.h>

#define ALPHA 26
#define MAX_TRIE_VERTEX 100

typedef struct {
	int child[ALPHA];
	int done;
}trie_type;

trie_type trie[MAX_TRIE_VERTEX];
int trie_count = 1;

int init()
{
	int i,j;
	trie_count = 1; // for root node
	for(i=0;i<MAX_TRIE_VERTEX;i++){
		for(j=0;j<ALPHA;j++){
			trie[i].child[j] = 0;
		}
		trie[i].done = 0;
	}
}

void trie_insert(const char data[])
{
	int i;
	int node_vertex = 0; // 0 : root node
	int next_node_vertex = 0;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node_vertex = trie[node_vertex].child[data[i]-'a'];
		if( next_node_vertex == 0 ){
			// empty chiled need to add
			trie[node_vertex].child[data[i]-'a'] = trie_count;
			node_vertex = trie_count;
			trie_count++;
		}else{
			node_vertex = next_node_vertex;
		}
	}
	if(node_vertex!=0){
		// string end
		trie[node_vertex].done = 1;
	}
}

int trie_search(const char data[])
{
	int i;
	int node_vertex = 0; // 0 : root node
	int next_node_vertex = 0;
	for(i=0;;i++){
		if (data[i]==0) break;
		
		next_node_vertex = trie[node_vertex].child[data[i]-'a'];
		if( next_node_vertex == 0 ){
			// empty child 
			return 0;
		}else{
			node_vertex = next_node_vertex;
		}
	}
	if(node_vertex!=0){
		if (trie[node_vertex].done==1) return 1;
	}
	return 0;
}

int main()
{
	init();
	trie_insert("abc");
	trie_insert("ksg");
	trie_insert("abefg");
	trie_insert("tg");
	
	printf("%d\n",trie_search("abf"));//0
	printf("%d\n",trie_search("ksg"));//1
	printf("%d\n",trie_search("abdfg"));//0
	printf("%d\n",trie_search("abefg"));//1
	printf("%d\n",trie_search("ab"));//0
}

위 내용은 정적 메모리로 구현되어 있습니다. 다음 노드의 배열을 아래와 같은 코드로 구현하여 indexing이 빠르게 됩니다. 이 부분을 일일이 loop를 사용하여 확인한다면 성능이 떨어지게 됩니다.

next_node_vertex = trie[node_vertex].child[data[i]-'a'];

코드 간단설명

trie_insert 함수에서 문자열이 입력되면 문자열을 하나씩 확인하면서 node를 찾아갑니다.

node가 없다면 새로운 노드를 추가하게 됩니다. 

마지막은 done flag를 추가해서 문자열이 끝남을 기록해 둡니다.

done flag는 필요에 따라 유용하게 사용가능합니다.