파이썬, 자바 Trie[트라이] 비교

 

@wikipedia

Trie [트라이]

또는 디지털 트리, suffix/prefix (접두/접미) 트리

 

1. 소개

Trie는 탐색 트리의 일종이며 주로 문자열로 이루어진 트리 자료 구조이다.

Boggle Board 같은 알고리즘에서 원하는 단어를 얻어낼 때 유용하다.

Boggle Board

 

이 글 Trie 구조는 아래 words(String[]) 배열을 결과물처럼 만들 것이다.

endSymbol = asterisk(*)로 지정해서 *까지 도달하면 그 문자열은 찾은 걸로 표시한다. (full word)

words = [
    "안녕하세요",
    "안녕",
    "하세요",
    "반갑습니다",
    "트라이",
    "트라이앵글",
]

# 결과물
{'안': {'녕': {'하': {'세': {'요': {'*': '안녕하세요'}}}, '*': '안녕'}}, '하': {'세': {'요': {'*': '하세요'}}}, '반': {'갑': {'습': {'니': {'다': {'*': '반갑습니다'}}}}}, '트': {'라': {'이': {'*': '트라이', '앵': {'글': {'*': '트라이앵글'}}}}}}

 

2. 클래스 생성

파이썬

: 간단하게 딕셔더리 하나와 endSymbol을 지정하면 끝

(Node를 만들어서 해도 되지만, dictionary만 이용했다.)

class Trie:
    def __init__(self):
        self.root = {}
        self.endSymbol = "*"

 

자바

: "A" : {TrieNode{ "B" : { TrieNode{....}} ... } 구조를 이용하기 위해

HashMap<Character, TrieNode>를 만들고, Trie 클래스를 만들어준다.

class TrieNode {
    HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
    String word = "";
}

class Trie {
    TrieNode root;
    char endSymbol;

    public Trie() {
        this.root = new TrieNode();
        this.endSymbol = '*';
    }
}

// 자바 결과
{안=TrieNode@312b1dae, 하=TrieNode@7530d0a, 반=TrieNode@27bc2616, 트=TrieNode@3941a79c}

 

3. add 함수

파이썬

: 파이썬은 Hash 맵을 쉽게 이용할 수 있다.

"A" : { "B" : {} } 와 같이 있으면, hash["A"] = "B", hash["A"]["B"] = {} ...

def add(self, word):
    node = self.root
    for letter in word:  # char
        if letter not in node:  # 사전 key 목록에 없으면 빈 노드를 하나 만든다.
            node[letter] = {}  # ex) "A" : {}
        node = node[letter]  # nested 딕셔너리 탐색, "A" : { "B" : {}}면 "B"값 불러오기 
    node[self.endSymbol] = word  # 최하위 노드에 "*"를 추가하고 "*" : { word }로 설정

 

자바

: HashMap을 노드로 설정 후, String의 각 char이 키로 있는지 확인하고

없으면 새로운 TrieNode를 만들고, 이 노드를 안에 집어넣는다.

public void add(String word) {
    TrieNode node = this.root;  // TrieNode
    for (int i = 0; i < word.length(); i++) {  // = for (char c : Arrays.asList(word))
        char letter = word.charAt(i);  // word[i]
        if (!node.children.containsKey(letter)) {  // node.children = HashMap
            TrieNode newNode = new TrieNode();  // 없으면 새 노드 만든 후
            node.children.put(letter, newNode);  // 값 넣기
        }
        node = node.children.get(letter);  // 하위 노드 값으로 업데이트
    }
    node.children.put(this.endSymbol, null);  // key="*", value=null
    node.word = word;  // 마지막 노드 word = word로 지정
}

 

4. 결과 출력

파이썬

: 간단하게 print() 함수를 이용하면 끝

words = [
    "안녕하세요",
    "안녕",
    "하세요",
    "반갑습니다",
    "트라이",
    "트라이앵글"
]

if __name__ == "__main__":
    trie = Trie()

    for word in words:
        trie.add(word)

    print(trie.root)

# 결과
# {'안': {'녕': {'하': {'세': {'요': {'*': '안녕하세요'}}}, '*': '안녕'}}, '하': {'세': {'요': {'*': '하세요'}}}, '반': {'갑': {'습': {'니': {'다': {'*': '반갑습니다'}}}}}, '트': {'라': {'이': {'*': '트라이', '앵': {'글': {'*': '트라이앵글'}}}}}}

 

자바

Trie 생성

String[] words = {"안녕하세요",
        "안녕",
        "하세요",
        "반갑습니다",
        "트라이",
        "트라이앵글",};

Trie trie = new Trie();

for (String word : words) {
    trie.add(word);
}

 

1. JDK8+, 최상위 키와 값들 표시

trie.root.children.forEach((key, value) -> System.out.println(key + " " + value));

/* 결과
안 TrieNode@312b1dae
하 TrieNode@7530d0a
반 TrieNode@27bc2616
트 TrieNode@3941a79c
*/

 

2. System.out.println

System.out.println(trie.root.children);
// {안=TrieNode@312b1dae, 하=TrieNode@7530d0a, 반=TrieNode@27bc2616, 트=TrieNode@3941a79c}

 

3. 재귀 함수

static void print(TrieNode node) {
    for (Map.Entry<Character, TrieNode> t : node.children.entrySet()) {
        TrieNode value = t.getValue();
        String val = value != null ? "HashMap<Character, TrieNode>" : node.children.containsKey('*') ? node.word : "null";
        // 값이 hashmap이면 주소보단 hashmap으로 표시, key 값이 '*'이면 node.word 아니면 null

        System.out.println("Key: " + t.getKey() + ", Value: " + val);
        if (value instanceof TrieNode) {  // value가 TrieNode면 print()
            print(t.getValue());
        }
    }
}

print(trie.root);

/* 결과
Key: 안, Value: HashMap<Character, TrieNode>
Key: 녕, Value: HashMap<Character, TrieNode>
Key: 하, Value: HashMap<Character, TrieNode>
Key: 세, Value: HashMap<Character, TrieNode>
Key: 요, Value: HashMap<Character, TrieNode>
Key: *, Value: 안녕하세요
Key: *, Value: 안녕
Key: 하, Value: HashMap<Character, TrieNode>
Key: 세, Value: HashMap<Character, TrieNode>
Key: 요, Value: HashMap<Character, TrieNode>
Key: *, Value: 하세요
Key: 반, Value: HashMap<Character, TrieNode>
Key: 갑, Value: HashMap<Character, TrieNode>
Key: 습, Value: HashMap<Character, TrieNode>
Key: 니, Value: HashMap<Character, TrieNode>
Key: 다, Value: HashMap<Character, TrieNode>
Key: *, Value: 반갑습니다
Key: 트, Value: HashMap<Character, TrieNode>
Key: 라, Value: HashMap<Character, TrieNode>
Key: 이, Value: HashMap<Character, TrieNode>
Key: 앵, Value: HashMap<Character, TrieNode>
Key: 글, Value: HashMap<Character, TrieNode>
Key: *, Value: 트라이앵글
Key: *, Value: 트라이
*/

 

Trie 위키백과 링크

Trie - Wikipedia