[Algorithm] Trie자료구조

이성훈·2022년 11월 2일
Triealgorithmdatastructurestruct
0

Algorithm

목록 보기
11/16

개요

문자열의 집합이 주어졌을때, 여기서 원하는 문자열을 탐색하려면
브루트포스방법으로 생각하면 문자열 갯수N, 문자열길이가 M이면 최대 O(N*M) 시간이 걸린다.(문자열길이는 제각각 다르겠지만..)
이것을 우리가 배운 이진트리를 이용하여 이진탐색을 한다고하면
한문자를 검색하는데 이진검색은 O(log N)가 걸리지만, 문자열의 길이가 M으로 늘어난이상 최대 O(M log N)의 시간이 걸릴것이 분명하다.
이를 문자의 트리형태인 트라이 구조로 나타내면 O(M) 시간만에 해결이 가능하다.

트라이 자료구조

root에서 모든 문자열의 0번째인덱스부터 하나의 문자를 담는 노드를 만들어 연결한다. 이때 노드는 실제값이아닌 인덱스만으로도 구현이 가능하다.(뒤에서 설명하겠다.)
그다음에는 트리구조처럼 그다음 인덱스의 문자를 이전 인덱스문자 아래의 자식 노드로 삽입시키면된다.
끝으로 문자열의 끝부분에는 별도의 체크를해두어
탐색하고자하는 문자가 존재하는지 파악하는데 사용하면된다.

구현 1 : 포인터배열로 자료 저장

  1. 트라이 구조체를 선언한다. 우리는 구조체로 구현할것이다.
    여기서 Trie포인터형 node가 26개 존재하는데, 이것이 위에서 설명한
    노드의 값이아닌 인덱스만으로 탐색에 사용한다는 의미다.
    이미 고정형으로 26개의 공간이 마련되있는데,
    해당 공간에 nullptr 형이면 그에 해당하는 문자(0~25 == A~Z)
    가 존재하지않음 나타내는것이다.
    여기에 finish변수를 두어, 문자열의 끝부분에 체크를 해줄것이다. (정확히 말하면 문자열의 끝 + 1위치의 노드에 체크하게된다. 자세한건 1번과정)

  2. insert 함수 : 문자열을 트라이자료구조로 저장하는 함수

  • line 99 : string이아닌 char형배열을 받는다.
  • line 101 : 문자열의 길이가 K면 문자열[K] = '\0'값이 들어가게된다. 따라서 K번째인덱스는 사실상 문자열의 길이에 + 1한 위치고, 이 위치에 해당하는 노드의 finish를 true로 두게된다.
    이후 탐색 함수 두군데에서 같은 로직을 사용할것이므로 기억해두자.
  • line 106 : 현재 탐색중인 문자를 숫자 0~25값으로 치환하는 코드이다.
  • line 107~108 : 0번에서 설명했듯 다음 위치가될 node[cur]포인터가 nullptr이면 새로 객체를 생성해준다. 이렇게 node[cur]포인터가 객체를 가지는것이 cur에 해당하는 문자를 트라이 자료구조에 추가한것이다.
  • line 110 : 앞서 생겨난 Trie객체를 가리키는 포인터node[cur]로 Trie객체를 insert()함수를 새롭게 호출한다.
    이때 str + 1로 다음 문자를 탐색하도록 지시한다.


    각 과정을 간단하게 그림을 그려보면 아래와 같다.

    Trie형 객체를 선언후 insert함수를 사용하면 이와같이
    trie객체내부에 여러 trie포인터들이 겹겹히 생성된다.
    내부 구성요소로 node[0]~node[25]포인터와finish가 있는모습이다.
    마지막에 '\0'을 만난시점은 이미 문자열을 이루는 데이터는 그전단계에서 마무리된 상태임을 알수있다.
    어찌됬는 문자열원래길이 + 1 번째 객체공간의 finish = true가 된다.
    여기서 만약 "abc" 란 문자열이 트라이 구조로 들어오면
    그림의 세번째공간에 node[2] = new Trie(); 로 새로 공간이생기고
    생겨난 공간이 사실상 '\0'이 매칭되는 공간으로 finish = true가 될것이다.


  1. find 함수 : 찾고자하는 문자열과 완벽히 일치하는 문자열이 있는지 탐색
  • line 114 : char 배열을 전달 받는다.
  • line 116 : insert함수와 같은 논리로 문자열의끝 +1위치에 finish체크가 되있는지 함께 확인한다. 두 조건모두 참이어야 str과 완벽히 일치하는 문자열이 존재하는것이다.
  • line 119 : 완벽히 일치하는 문자열을 찾은경우다.
  • line 123 : 현재 탐색중인 문자를 인덱스값으로 치환한다.
  • line 124 : 현재포인터가 nullptr이란것은 위의 insert에서 그림으로 봤듯이 다음 객체가 없는상태를 의미한다. 따라서 더이상 탐색을 진행할 수 없으니 false를 리턴한다.
  • line 125 : 다음 노드가 존재하면 재귀적으로 탐색을 진행한다.



  1. findPrefix 함수 : 찾고자하는문자열의 부분문자열이 트라이 구조에 존재하는지 탐색
  • line 132 : 찾는문자열의 처음문자부터 현재문자까지의 부분문자열(접두사)이 트라이구조에 존재하는것을 의미한다. 따라서 접두사가 존재하므로 true 리턴
  • line 135 : 문자열끝에 도달했으니 탐색종료
  • line 143 : 2번과정의 line 124와 같은 논리다.
  • line 146 : 2번과정의 line 125와 같은 논리다.
  1. 구조체 사용법

    line 152 처럼 포인터도아니고 그냥 객체 타입선언하듯 사용하면된다.
    이를 실행하면
    해당 search 문자열이 집합내에 존재는안하지만 seach문자열의 일부분이 집합내에 존재한다고 한다. 정확한 결과이다.

전체 코드

struct Trie {
	Trie* node[26]; //노드를 나타내는 포인터
	bool finish; //문자열의 끝체크 : K번째 노드에 true체크되있으면 문자열의 길이는 K-1임.
	//0. 생성자 : 초기화
	Trie() : node(), finish(false) {}

	//1. 문자열을 트라이 자료구조로 만드는 함수
	void insert(char* str) {
		//1-1. 문자열의길이가 K면 K+1번쨰 노드에 finish = true체크하는겁니다
		if (*str == '\0') {
			finish = true;
			return;
		}
		//1-2. 트라이구조에 다음노드가 업으면 생성
		int cur = *str - 'A';
		if (node[cur] == nullptr)
			node[cur] = new Trie();
		//1-3. 현재 노드와 다음 노드를 이어감. (이미 만들어져있었으면 이미 이어져있었을것)
		node[cur]->insert(str + 1);
	}

	//2. 일치하는 문자열이 존재하는지 확인하는 함수
	bool find(char* str) {
		//2-1. 문자열의끝 + 1에 도달했지만 종료체크가 안되있으면 문자열 탐색 실패
		if (*str == '\0' && !finish) return false;

		//2-2. 문자열의끝 + 1에 도달했지만 종료체크가 되있으면 문자열 탐색에 성공
		if (*str == '\0' && finish) return true;

		//2-3. 트라이자료구조에 다음 문자가 존재하지 않으면 문자열 탐색 실패
		int cur = *str - 'A';
		if (node[cur] == nullptr) return false;
		return node[cur]->find(str + 1); //트라이자료구조에 다음 문자가 존재하면 계속 탐색진행
	}

	//3. 접두사로만 문자열이 존재하는지 확인하는 함수
	//문자열을 포함한 다른 문자열이 존재하는 여부를 리턴함
	bool findPrefix(char* str) {
		//3-1. 문자열 끝 + 1까지 탐색하는중 종료체크된 노드를 찾으면 접두사가존재, 탐색 성공
		if (finish) return true; //str[0]~이전문자  까지로 구성된 접두사가 존재할거에옹

		//3-2. 문자열끝 + 1에 도달했으면 탐색 실패
		if (*str == '\0') return false;

		////////////////////////////////////////////////////////////////////////////////////////////////
		//만약 ' if(finish) return true '를 이 위치로 바꾸면 완벽히일치하는 문자열은 결과에서 제외가능//
		////////////////////////////////////////////////////////////////////////////////////////////////

		//3-3. 트라이구조를에 다음 문자가 없으면 탐색 실패
		int cur = *str - 'A';
		if (node[cur] == nullptr) return false;

		//3-4. 트라이구조의 다음문자를 따라서 계속 탐색 진행
		return node[cur]->findPrefix(str + 1);
	}

	//4. DFS in Trie
	void DFS(int depth) {
		for (int i = 0; i < 26; i++) {
			if (node[i] == nullptr) continue;
			////////////////////////////////////////////////////////////////////////////////////////////
			//////////////////////////////////DFS탐색하며 쓸 코드 작성//////////////////////////////////
			////////////////////////////////////////////////////////////////////////////////////////////
			node[i]->DFS(depth + 1);
		}
	}

	//5. BFS in Trie
	//???
};

구현 2 : map객체로 자료저장

이번에는 조금더 범용성있는 map객체를 활용한 구현을 살펴보겠다.
0. 구조체 선언
map객체의 키값이 우리가 찾고자하는 문자에 해당한다. node[key] == nullptr이면 key가 존재하지않는것이고 그렇지않다면 value인 pointer로 다음 Trie객체를 따라 내려 갈 수 있다!. 이것으로 트리구조를 간단히 구현가능하다.

  1. insert함수 : 재귀적인 방법으로 전달받은 char문자배열을 문자단위로 Trie구조에 편입한다.
  • line28 : 문자열을 char배열로 전달받는다.
  • line29 : 문자의 끝처리를 위한 조건이다. [구현1] 방법에서 설명한내용이므로 map객체를 활용하는 부분에서만 집중적으로 설명하겠다.
  • line36 : map객체에서 *str즉 문자하나를 키값으로 검색하여
    그 밸류에 해당하는 포인터를얻어서 그 포인터가 가리키는 다음 Trie객체 내부의 insert 함수를 호출한다! 여기서 (str + 1)을 전달하여 str문자열의 다음 인덱스를 탐색 하도록한다.
  1. find함수 : 재귀적인 방법으로 찾고자하는 문자열과 정확히 일치하는 문자열이 있는지 확인하는 함수.
    insert함수와 비슷하게 작동한다. 그 말은 재귀적으로 find(str + 1)을 호출하며, 문자열의 끝부분에대한 조건부도 *str == '\0'으로 같다는것이다.
  • line48 : node[*str] 에해당하는 값은 포인터고 그 포인터로 다음 Trie객체의 find함수를 실행하고있다.

  1. findPrefix함수 : 재귀적인 방법으로, 찾는 문자열의 일부분이라도 Trie구조에 저장되있는지 확인하는 함수다. 정확히 일치하는경우는 false이다.

    이에대한 설명은 충분히 앞서 진행했다.

  2. DFS전용 함수 : 재귀적으로 Trie구조의 모습을 탐색할 수 있도록 코드를 짜보았다.
    키값을 검색할때 모든 아스키코드값을 검색하도록 0~127값을 검색하도록 했다.
    이때 호출할때마다 고유의 특정값을 전달하고 싶으면 인자인 depth를 수정하거나 또 다른 인자를 추가하여
    이후 line70의 재귀호출부분에서 다르게 호출하면 된다.
    여튼 line70의 코드 또한 앞서 본 3가지 함수처럼 재귀적으로 포인터를 이용해 DFS함수를 호출 하는 모습이다.

이 코드가 작동하는 과정을 그림으로 보고싶다면 >> https://velog.io/@cldhfleks2/14725

아래는 전체 코드이다.

struct Trie {
	std::map<char, Trie*> node;
	bool finish;

	Trie() : node(), finish(false) {}

	//string을 Trie자료구조로 편입
	void insert(char* str) {
		if (*str == '\0') {
			finish = true;
			return;
		}
		if (node[*str] == nullptr)
			node[*str] = new Trie();

		node[*str]->insert(str + 1);
	}

	//완벽히 일치하는 문자열이 있는가
	bool find(char* str) {
		if (*str == '\0' && finish)
			return true;
		if (*str == '\0' && !finish)
			return false;

		if (node[*str] == nullptr)
			return false;
		return node[*str]->find(str + 1);
	}

	//접두사로만 일치하는 문자열이 있는가
	bool findPrefix(char* str) {
		if (*str == '\0')
			return false;
		if (finish)
			return true;

		if (node[*str] == nullptr)
			return false;
		return node[*str]->findPrefix(str + 1);
	}

	//4. DFS in Trie
	void DFS(int depth) {
		for (int c = 0; c < 128; c++) {
			if (node[c] == nullptr) continue;
			////////////////////////////////////////////////////////////////////////////////////////////
			//////////////////////////////////DFS탐색하며 쓸 코드 작성//////////////////////////////////
			////////////////////////////////////////////////////////////////////////////////////////////
			node[c]->DFS(depth + 1);
		}
	}

	//5. BFS in Trie
	//???
};

관련문제

https://www.acmicpc.net/problem/5052 >> https://velog.io/@cldhfleks2/5052
https://www.acmicpc.net/problem/14725 >> https://velog.io/@cldhfleks2/14725
https://www.acmicpc.net/problem/16934 >> https://velog.io/@cldhfleks2/16934

profile
이성훈
I will be a socially developer
이전 포스트

[Algorithm] KMP, Knuth-Morris-Pratt 효율적인 문자열 탐색

다음 포스트

[Algorithm] LCS, Longest Common Substring 최장공통부분수열

0개의 댓글