트라이 알고리즘(Trie Algorithm)

트라이 알고리즘(Trie Algorithm)

트라이 알고리즘

트라이 알고리즘 : 문자열을 효율적이게 저장하고 탐색하기 위한 트리 형태의 구조.

시간 복잡도 : 가장 긴 문자열의 길이를 m이라 할 때, O(m)

트라이 알고리즘 개요:

- 트라이 알고리즘은 k진 트리 구조이다.

- 루트 노드(최상위 노드)에는 어떠한 단어도 들어가지 않는다.

- 트라이는 접두사(prefix)를 이용하여 저장과 탐색을 수행한다. 이 때문에 접투사 트리(prefix tree)라고도 불린다.

- 트라이는 탐색에서 매우 좋은 시간 복잡도를 갖지만 공간 복잡도에서 치명적인 단점을 갖고있다.

1. 주어진 문자열에서 현재 문자를 가져온다.

2. 현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하고, 노드가 없다면 그 노드를

새로 할당 받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다.

예제로 [FCFS, SJF, SRTF, RR, MLQ, MLFQ]을 삽입하겠습니다.

먼저 FCFS를 삽입하겠습니다.

현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하지만, 노드가 없으므로 새로운 노드를 할당받는다.

계속해서 같은 과정이 반복 될 것이다.

최종적으로 FCFS가 삽입된 모습은 위와 같은 것이다.

다음은 SJF를 삽입해보겠습니다.

현재 문자로 이루어진 노드가 존재한다면, 그 노드로 그 다음 문자열을 탐색하지만, 노드가 없으므로 새로운 노드를 할당받는다. 이 과정은 FCFS를 삽입했을 때 과정이랑 같다.

따라서 SJF를 삽입하면 위와 같은 상태일 것이다.

다음은 SRTF를 삽입하겠습니다.

현재 문자 S로 이루어진 노드가 존재하기 때문에, 그 노드로 그 다음 문자열을 탐색합니다.

다음 문자 R이 들어갈 때는 문자에 해당하는 노드가 없으므로 새로운 노드를 할당받아 삽입될 것입니다.

이어 T와 F를 삽입하면 위와 같은 형태로 될 것이다.

이어서 나오는 RR과 MLQ도 해당하는 문자 노드가 없으므로 새로 할당을 받을 것이다. 이 과정은 위에 FCFS와 SJF를 넣는 과정과 같으므로 생략하겠습니다.

RR과 MLQ를 삽입하면 위와 같을 것입니다.

다음은 MLFQ를 삽입하겠습니다.

현재 문자 M으로 이루어진 노드가 존재하기 때문에, 그 노드로 그 다음 문자열을 탐색합니다. 또한 이후 문자인 L로 이루어진 노드가 존재하므로 그 느드로 다음 문자열을 탐색합니다. 이 후 나오는 F는 존재하지 않으므로 새로운 노드를 할당 받을 것입니다.

따라서 MLFQ를 삽입 했을 때, 위와 같을 것이고 모든 문자열을 삽입했으므로 결과적으로 위와 같은 트리가 완성될 것 입니다.

완성된 트리를 이용하여 원하는 문자열이 있는지 탐색하는 것이 바로 트라이 알고리즘이다.

정리 :

- 트라이는 문자열의 탐색에 특화된 트리 자료 구조이다.

- 트라이 구조에서 탐색은 O(m) (m은 문자열의 길이)의 시간 복잡도를 갖는다.

- 트라이 구조는 문자에 대해 노드를 생성해야하므로 공간 복잡도 상에서는 치명적인 단점을 갖는다.(위의 예제에서 17의 알파벳 노드를 갖고 있다.)

다음 포스트에서는 트라이 알고리즘의 구현과 이를 이용한 예제 하나를 풀어보겠습니다.

참고 자료 :

https://yabmoons.tistory.com/379

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)#%EC%9E%90%EB%8F%99_%EC%99%84%EC%84%B1

https://namu.wiki/w/%ED%8A%B8%EB%9D%BC%EC%9D%B4

from http://dabonee.tistory.com/46 by ccl(A) rewrite - 2021-10-02 17:26:42