- Learn about Wiki
- Lectures
- Study
- Tips
트라이는 다음과 같은 특징이 있다.
이진 검색 트리와 트라이의 시간 복잡도.
데이타 구조 | 시간 복잡도 |
---|---|
(정수/실수) 이진 검색 트리 | O(logN) |
문자열 이진 검색 트리 | O(MlogN) |
트라이 | O(M) |
문자열 집합 : S = {“BE”, “BET”, “BUS”, “TEA”, “TEN”} 의 트라이 구성
// 알파벳 소문자를 저장하는 경우 각 노드는 26개의 자손을 가질 수 있다 const int ALPHABETS = 26; int toNumber(char ch) { return ch - 'A'; } struct LinkedListNode { int elem; LinkedListNode* next; LinkedListNode(int _elem, LinkedListNode* _next) : elem(_elem), next(_next) { } }; // 트라이의 한 노드를 나타내는 객체 struct TrieNode { TrieNode* children[ALPHABETS]; // 이 노드가 종료 노드인가? bool terminal; TrieNode() : terminal(false) { memset(children, 0, sizeof(children)); } ~TrieNode() { for(int i = 0; i < ALPHABETS; i++) if(children[i]) delete children[i]; } // 이 노드를 루트로 하는 트라이에 문자열 key 를 추가한다. void insert(const char* key) { // 문자열이 끝나면 terminal 만 참으로 바꾸고 종료 if(*key == 0) terminal = true; else { int next = toNumber(*key); // 해당 자식 노드가 없다면 생성한다 if(children[next] == NULL) children[next] = new TrieNode(); // 해당 자식 노드로 재귀호출 children[next]->insert(key + 1); } } // 이 노드를 루트로 하는 트라이에 문자열 key 와 대응되는 노드를 찾는다. // 없으면 NULL 을 반환한다. TrieNode* find(const char* key) { if(*key == 0) return this; int next = toNumber(*key); if(children[next] == NULL) return NULL; return children[next]->find(key+1); } };
; 맵으로 노드 표현 ; {:id 정수 문자 {...} 문자 {...} ...} ; :id 는 현재 노드가 중간 노드인지 아니면 종료 노드인지 표시 ; 이후 자식에 해당하는 문자를 키로 하고 해당 자식 노드를 값으로 한다. (defn find-word [trie word] (get-in trie (seq word))) (defn insert-word [trie word] (reduce #(if (get-in % %2) % (assoc-in % %2 {:id (if (= (count word) (count %2)) 1 0)})) trie (reduce #(conj % (str (last %) %2)) [] (seq word)))) (defn make-trie [col] (reduce insert-word {} col)) (def trie (make-trie ["BUS" "BE" "BET" "TEA" "TEN"])) trie ;=> {:id 0 \B {:id 0 \U {:id 0 \S {:id 1}} \E {:id 1 \T {:id 1}}} \T {:id 0 \E {:id 0 \A {:id 1} \N {:id 1}}}} (find-word trie "BUS") ;=> {:id 1} (find-word trie "BE") ;=> {\T {:id 1}, :id 1} (find-word trie "TE") ;=> {\A {:id 1}, \N {:id 1}, :id 0}
위 C++ 코드에서 terminal을 불린형에서 정수형으로 바꾸면 사전 자료 구조로 사용할 수 있다. terminal을 정수로 바꾸면 map<string, int> 형의 사전 자료 구조가 된다.
한 문자열 S의 모든 접미사를 트라이에 넣는 것을 말한다. 이렇게 해서 부분 문자열을 빠르게 검색할 수 있다.
단어 | ALL | AND | FISH | FOR | SO | THANKS | THE |
---|---|---|---|---|---|---|---|
출현빈도 | 4 | 3 | 8 | 6 | 4 | 9 | 9 |
단어 | 추천 단어 | 타이핑 문자수 |
---|---|---|
SO | S→ [SO], TAB | 2 |
LONG | L→[], LONG | 4 |
AND | A → [ALL], AN → [AND], TAB | 3 |
THANKS | T → [THANKS], TAB | 2 |
FOR | F → [FISH], FO→[FOR], TAB | 3 |
ALL | A → [ALL], TAB | 2 |
THE | T → [THANKS], TH→[THANKS], THE | 3 |
FISH | F → [FISH], TAB | 2 |
TOTAL | 21 | |
SPACE | 단어 사이 공백 문자 | 7 |
WHOLE | 28 |
*inp 파일
2 7 8 ALL 4 AND 3 FISH 8 FOR 6 SO 4 THANKS 9 THE 9 SO LONG AND THANKS FOR ALL THE FISH 7 8 ALL 4 AND 5 FISH 3 FOR 6 SO 8 THANKS 1 THE 2 SO LONG AND THANKS FOR ALL THE FISH
(ns trie (:use [clojure.string :only [split]] [clojure.java.io]) (:import [java.io BufferedReader StringReader])) (defn recommend [dic prefix] (let [sv (filter #(.startsWith % prefix) (keys dic))] (sort (reduce (fn [col s] (let [n (dic s) k (dic (first col))] (cond (nil? k) (conj col s) (< n k) col (= n k) (conj col s) (> n k) (conj [] s)))) [] sv)))) (defn count-typing [dic word] (some #(let [r (recommand dic %)] (cond (empty? r) (count word) (= (first r) word) (if (= % word) (count %) (inc (count %))) :else nil)) (reduce #(conj % (str (last %) %2)) [] (seq word)))) (defn count-min-typings [dic sentence] (let [s (split sentence #"\s")] (reduce #(+ % (count-typing dic %2)) 0 s))) (defn make-dic [lines] (reduce (fn [col [k v]] (assoc col k (read-string v))) {} (map #(split % #"\s") lines))) (defn try-case [rdr] (let [[wc1 wc2] (map read-string (split (.readLine rdr) #"\s")) dic (make-dic (take wc1 (line-seq rdr))) input-string (.readLine rdr)] (+ (dec wc2) (count-min-typings dic input-string)))) (defn solve [input] (let [rdr (BufferedReader. (StringReader. input)) case-count (read-string (.readLine rdr))] (for [n (range case-count)] (try-case rdr)))) (solve (slurp "inp")) ;=> (28 29)
(ns solong (:use [clojure.string :only [split]] [clojure.java.io]) (:import [java.io BufferedReader StringReader])) (defn find-word [trie word] (get-in trie (seq word))) (defn insert-word [trie [word freq]] (reduce #(if (get-in % %2) % (assoc-in % %2 {:id (if (= (count word) (count %2)) freq 0)})) trie (reduce #(conj % (str (last %) %2)) [] (seq word)))) (defn make-trie [lines] (reduce insert-word {} (map #(let [[k v] (split % #"\s")] [k (read-string v)]) lines))) (defn children [trie] (keys (dissoc trie :id))) (defn iterate-children [trie] (let [t (fn [col] (mapcat #(map (fn [c] (conj % c)) (children (get-in trie %))) col))] (take-while seq (iterate t (map vector (children trie)))))) (defn find-prefix [trie col] (let [trie (get-in trie col)] (if (and (:id trie) (nil? (children trie))) (list col) (map #(concat col %) (apply concat (iterate-children trie)))))) (defn recommend [trie col] (apply str (first (sort-by (juxt #(- ((get-in trie %) :id)) #(apply str %)) (find-prefix trie (seq col)))))) (defn count-typing [trie word] (some #(let [r (recommand trie %)] (cond (empty? r) (count word) (= r word) (if (= % word) (count %) (inc (count %))) :else nil)) (reduce #(conj % (str (last %) %2)) [] (seq word)))) (defn count-min-typings [trie sentence] (let [s (split sentence #"\s")] (reduce #(+ % (count-typing trie %2)) 0 s))) (defn try-case [rdr] (let [[wc1 wc2] (map read-string (split (.readLine rdr) #"\s")) trie (make-trie (take wc1 (line-seq rdr))) input-string (.readLine rdr)] (+ (dec wc2) (count-min-typings trie input-string)))) (defn solve [input] (let [rdr (BufferedReader. (StringReader. input)) case-count (read-string (.readLine rdr))] (for [n (range case-count)] (try-case rdr)))) (solve (slurp "inp")) ;=> (28 29)
#include<algorithm> #include<cstring> #include<cstdio> #include<iostream> #include<string> #include<vector> using namespace std; // 알파벳 소문자를 저장하는 경우 각 노드는 26개의 자손을 가질 수 있다 const int ALPHABETS = 26; int toNumber(char ch) { return ch - 'A'; } // 트라이의 한 노드를 나타내는 객체 struct TrieNode { TrieNode* children[ALPHABETS]; // 이 노드에서 종료하는 문자열의 번호 int terminal; // 이 노드를 루트로 하는 트라이에 가장 먼저 추가된 단어의 번호 int first; TrieNode() { memset(children, 0, sizeof(children)); terminal = first = -1; } ~TrieNode() { for(int i = 0; i < ALPHABETS; i++) if(children[i]) delete children[i]; } // 이 노드를 루트로 하는 트라이에 번호 id 인 문자열 key 를 추가한다 void insert(const char* key, int id) { // first 를 우선 업데이트 if(first == -1) first = id; // 문자열이 끝났다면 terminal 만 바꾸고 종료 if(*key == 0) terminal = id; else { int next = toNumber(*key); // 해당 자식 노드가 없다면 생성한다 if(children[next] == NULL) children[next] = new TrieNode(); // 해당 자식 노드로 재귀호출 children[next]->insert(key + 1, id); } } // 이 노드까지 타이핑해 왔을 때, 번호 id 인 key 를 타이핑하기 위해 // 최소 몇 번의 키를 더 눌러야 하나? int type(const char* key, int id) { // 문자열 종료시 if(*key == 0) return 0; // 이 노드에서 추천되는 문자열이 이 문자열이면 탭 누르고 종료 if(first == id) return 1; // 아니면 다음 문자를 타이핑한다 int next = toNumber(*key); return 1 + children[next]->type(key + 1, id); } // 이 노드를 루트로 하는 트라이에 문자열 key 와 대응되는 노드를 찾는다. // 없으면 NULL 을 반환한다. TrieNode* find(const char* key) { if(*key == 0) return this; int next = toNumber(*key); if(children[next] == NULL) return NULL; return children[next]->find(key+1); } }; // 사전을 나타내는 트라이가 주어질 때, 단어 word 를 타이핑하는 데 // 몇 번이나 키를 눌러야 하는지 계산한다 int countKeys(TrieNode* trie, const char* word) { // 이 문자열이 사전에 있는지 확인하고, 있다면 번호를 구한다 TrieNode* node = trie->find(word); // 사전에 없으면 직접 타이핑할 수밖에 없다 if(node == NULL || node->terminal == -1) return strlen(word); // 탐색하면서 타이핑할 방법을 찾는다 return trie->type(word, node->terminal); } // 입력에 주어지는 단어들을 정렬해서 트라이로 변환한다 TrieNode* readInput(FILE *fp, int words) { // 단어들을 출현 빈도의 내림차순, 단어의 오름차순으로 정렬한다 vector<pair<int,string> > input; for(int i = 0; i < words; i++) { char buf[11]; int freq; fscanf(fp, "%s %d", buf, &freq); input.push_back(make_pair(-freq, buf)); } sort(input.begin(), input.end()); // 이 때 앞에 있는 단어일 수록 우선 순위가 높다. // 배열의 인덱스를 각 단어의 번호로 쓰자. TrieNode* trie = new TrieNode(); for(int i = 0; i < input.size(); i++) trie->insert(input[i].second.c_str(), i); // 아무 문자도 입력하지 않은 상황에서는 자동 완성되지 않아야 한다 trie->first = -1; return trie; } int main() { FILE *fp = fopen("inp", "r"); int cases; fscanf(fp, "%d", &cases); for(int cc = 0; cc < cases; ++cc) { int n, m; fscanf(fp, "%d %d", &n, &m); TrieNode* trie = readInput(fp, n); int ret = 0; for(int i = 0; i < m; i++) { char buf[11]; fscanf(fp, "%s", buf); int add = countKeys(trie, buf); ret += add; } delete trie; printf("%d\n", ret + m-1); } }
문제점 :
예제 입력에서 입력 문자열을 받아와서 어떤 문자열을 입력할 지를 미리 파악한 후 그 문자열의 ID로 추천어를 생성하고 있다. 즉 다음과 같다.
하지만 실제 상황에서는 돌고래가 어떤 문자열을 입력하게 될지는 실제로는 알 수 없기 때문에 추천어를 생성하는 로직은 좀 더 복잡해질 것이다.
원문에서 여러 개의 문자열을 검색하는 문제에 트라이를 이용할 수 있다.
짚더미 문자열 H : “CACACHEFCACHY” 바늘 문자열 : “CACHE”, “HE”, “CHEF”, “ACHY”
20 장 2 절에 소개됨.
바늘 문자열의 각 접두사마다 이 접두사의 접두사도 되고 접미사도 되는 문자열의 최대 길이 미리 계산
바늘 문자열 : “CACHE” 대응되는 문자열 : “CAC” 이후 실패 이 때 접미사도 되고 접두사도 되는 문자열은 “C” 이다. 그러면 대응되는 문자열은 세 글자가 아니라 한 글자라 생각하고, 다음 “A”부터 찾는다.
C :접두사도 되고 접미사도 되는 최대 문자열 _ | | 1차매칭: CACH |||x 짚더미: CACACHEFCACHY ||||| 2차매칭: CACHE
이런 과정때문에 짚더미 문자열의 각 문자를 한 번만 보고 모든 출현 위치를 찾아 낼 수 있다. 대응에 실패했을 때 어디로 가서 검색을 계속해야 할지 알려준다고 해서, 이런 정보를 실패 함수라고 한다.
다음은 네 개의 바늘 문자열 “CACHE”, “HE”, “CHEF”, “ACHY”에 대한 KMP 알고리즘이 생성하는 실패 함수를 보여준다.
위 그림에서 겹치는 접두사를 모아서 다시 그리면…
이와 같은 실패 함수를 전처리 과정에서 만든 뒤, 짚더미 문자열의 글자를 순회하면서 트라이의 상태들을 서로 오가면 모든 바늘 문자열들에 대해 동시에 KMP 알고리즘을 수행하는 것과 같은 효과를 낸다.
이것을 아호-코라식 문자열 검색 알고리즘이라고 부른다. 이 알고리즘은 긴 문서에서 많은 문자열을 동시게 창아야 하는 검색 엔진등에서 특히 유용하게 사용된다.
아호-코라식 알고리즘을 사용하기 위해서는 각 노드마다 다음과 같은 정보를 추가해야 한다.
// 트라이의 한 노드를 나타내는 객체 struct TrieNode { TrieNode* children[ALPHABETS]; // 현 위치에서 끝나는 문자열의 번호 int terminal; // 이 노드에서 매칭이 실패했을 때 이 곳으로 가서 계속한다. // 이 노드에 대응되는 문자열의 접미사이면서 트라이에 포함된 최대 문자열. TrieNode* fail; // 이 노드가 방문되었을 때 등장하는 문자열들의 번호 vector<int> output; TrieNode() : terminal(-1) { memset(children, 0, sizeof(children)); } ~TrieNode() { for(int i = 0; i < ALPHABETS; i++) if(children[i]) delete children[i]; } // 이 노드를 루트로 하는 트라이에 번호가 id 인 문자열 key 를 추가한다 void insert(const char* key, int id) { // 문자열이 끝나면 terminal 만 참으로 바꾸고 종료 if(*key == 0) terminal = id; else { int next = toNumber(*key); // 해당 자식 노드가 없다면 생성한다 if(children[next] == NULL) children[next] = new TrieNode(); // 해당 자식 노드로 재귀호출 children[next]->insert(key + 1, id); } } TrieNode* find(const char* key) { if(*key == 0) return this; int next = toNumber(*key); if(children[next] == NULL) return NULL; return children[next]->find(key+1); } };
무식한 방법 : 해당 노드에 대응된 문자열의 모든 접미사들을 하나하나 시도하면서 이 중 트라이에 포함되어 있는 첫 번째 문자열을 찾는 것.
빠른 방법 : 부모 노드의 실패 연결을 이용해서 자식 노드의 실패 연결을 쉽게 알 수 있다.
"CAC" -> "AC" "CACH" -> "ACH"
실패 연결을 계산하는 방법:
// 트라이가 주어질 때 각 노드에 대해 실패 연결과 출력 문자열 목록을 계산한다. void computeFailFunc(TrieNode* root) { // 루트에서부터 시작해 한 단계씩 아래로 내려가며 각 노드의 실패 연결을 계산한다. queue<TrieNode*> q; // 루트의 실패 연결은 자기 자신 root->fail = root; q.push(root); while(!q.empty()) { TrieNode* here = q.front(); q.pop(); // here 의 모든 노드에 대해 실패 연결을 계산하고 이들을 큐에 넣는다 for(int edge = 0; edge < ALPHABETS; ++edge) { TrieNode* child = here->children[edge]; if(!child) continue; // 1레벨 노드의 실패 연결은 항상 루트 if(here == root) child->fail = root; else { // 아닌 경우 부모의 실패 연결을 따라가면서 실패 연결을 찾는다 TrieNode* t = here->fail; while(t != root && t->children[edge] == NULL) t = t->fail; if(t->children[edge]) t = t->children[edge]; child->fail = t; } // 출력 문자열 목록: 실패 연결에서 가져온 뒤, 이 위치에서 끝나는 문자열이 있으면 추가한다 child->output = child->fail->output; if(child->terminal != -1) child->output.push_back(child->terminal); q.push(child); } } }
// trie 에 포함된 패턴들을 s 에서 찾는다. // s 내에서 패턴이 출현할 때마다 (마지막 글자, 패턴 번호) 의 쌍을 저장한다 vector<pair<int,int> > ahoCorasick(const string& s, TrieNode* trie) { vector<pair<int,int> > ret; TrieNode* state = trie; // 실제 루프 내는 KMP 와 별로 다를 것이 없다 for(int i = 0; i < s.size(); i++) { int chr = toNumber(s[i]); while(state != trie && state->children[chr] == NULL) state = state->fail; if(state->children[chr]) state = state->children[chr]; for(int j = 0; j < state->output.size(); ++j) ret.push_back(make_pair(i, state->output[j])); } return ret; }
설명