Trie辞書ツリーの実装
今日Trieの原理を見て、以前面接で出会った答えのない質問を思い出して、コードを書いてみました.
Trieの典型的な応用は統計と並べ替え、大量の文字列(ただし文字列に限らない)をクエリーするために用いられるため、検索エンジンシステムではテキストの語周波数統計などによく用いられる.キーワード長が最大5であればtrieツリーを用い,5回の比較で26^5=11881376個の可能なキーワードから指定したキーワードを検索できる.一方,二叉ルックアップツリーでは少なくともlog 2 n回の比較を行う.
ワード周波数を計算するには、ノードクラスを変更する必要があります.与えられた熟語表の場合、不良語表検索テキストの単語は、このデータ構造を使用することができます.
Trieの典型的な応用は統計と並べ替え、大量の文字列(ただし文字列に限らない)をクエリーするために用いられるため、検索エンジンシステムではテキストの語周波数統計などによく用いられる.キーワード長が最大5であればtrieツリーを用い,5回の比較で26^5=11881376個の可能なキーワードから指定したキーワードを検索できる.一方,二叉ルックアップツリーでは少なくともlog 2 n回の比較を行う.
ワード周波数を計算するには、ノードクラスを変更する必要があります.与えられた熟語表の場合、不良語表検索テキストの単語は、このデータ構造を使用することができます.
package algorithm;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
public class Trie {
private Node root=new Node();
public static void main(String[] args) {
Trie trie = new Trie();
List keyWords=new ArrayList();
keyWords.add("ca123");
keyWords.add("mu456");
keyWords.add("zh789");
trie.buildTrie(keyWords);
trie.search("ca123");
trie.search("ca124");
trie.search("mu445");
trie.search("zh789");
}
public void buildTrie(List keyWords){
for(String key:keyWords){
Node parent=root;
for (int i = 0; i < key.length(); i++) {
char nodeKey=key.charAt(i);
Node node = parent.getChildNodes().get(nodeKey);
if (node!=null) {
parent=node;
} else {
Node childNode = new Node();
parent.getChildNodes().put(nodeKey, childNode);
parent=childNode;
}
}
parent.setValue(key);
}
}
public void search(String key){
Node parent=root;
for (int i = 0; i < key.length(); i++) {
Node node = parent.getChildNodes().get(key.charAt(i));
if (node == null) {
System.out.println("The word "+key+" is not in dictionary");
return;
}
parent=node;
}
System.out.println("The word "+parent.getValue()+" is in the dictionary");
}
}
class Node {
private String value;
private HashMap childNodes;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public HashMap getChildNodes() {
if (childNodes==null) {
childNodes=new HashMap();
}
return childNodes;
}
public void setChildNodes(HashMap childNodes) {
this.childNodes = childNodes;
}
}