書き込みトライ実装

Question

この質問は何度も尋ねられていますが、私は多くの場所で検索しましたが、まだトライ実装を記述するためのステップバイステップの指示を得ることができる場所は1つも見つかりませんでした。 優先言語がJavaまたはPython
は、私はJavaやPythonのコーダないんだけど、あなたは非常に単純なC＃のトライの実装を与えることができ、あなたに

Answer 1

私はjavaで文字列を検索しようとしました。その非常に単純：ここ は、手順は次のとおりです。

Nodeクラスは、このようなものです：

public class Trienode { 
    char c; 
    Trienode parent; 
    ArrayList<Trienode> childs; 
} 

Trienode addString{ String str, Trienode root){ 
     if(str.length == 0) return root; 
     String newstr = [str without the first char]; 
     char c = str[0]; 
     Trienode newnode = root[c - '0']; 
     if(newnode == null){ 
      newnode = new Trienode(); 
      newnode.c = c; 
      newnode.parent = root; 
     } 
     return addString(newstr, newnode); 
    } 

あなたが同じライン上での検索などを作成することができます。

Answer 2

に感謝である私を助けてください。非常にシンプルなので、Javaにマッピングできると確信しています。

はここにある：

public class Trie<T> : Dictionary<T, Trie<T>> 
{ 
} 

を完了します。あなたはそれが簡単だと言った。しかしそれはトライであり、それは動作します。

Answer 3

このリンクは、コードを含むウォークスルーを提供します。ここで

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries

Answer 4

#!/usr/bin/env python 
import sys 

class Node: 
    def __init__(self): 
     self.next = {} #Initialize an empty hash (python dictionary) 
     self.word_marker = False 
     # There can be words, Hot and Hottest. When search is performed, usually state transition upto leaf node is peformed and characters are printed. 
     # Then in this case, only Hottest will be printed. Hot is intermediate state. Inorder to mark t as a state where word is to be print, a word_marker is used 


    def add_item(self, string): 
     ''' Method to add a string the Trie data structure''' 

     if len(string) == 0: 
      self.word_marker = True 
      return 

     key = string[0] #Extract first character 
     string = string[1:] #Create a string by removing first character 

     # If the key character exists in the hash, call next pointing node's add_item() with remaining string as argument 
     if self.next.has_key(key): 
      self.next[key].add_item(string) 
     # Else create an empty node. Insert the key character to hash and point it to newly created node. Call add_item() in new node with remaining string. 
     else: 
      node = Node() 
      self.next[key] = node 
      node.add_item(string) 


    def dfs(self, sofar=None): 
     '''Perform Depth First Search Traversal''' 

     # When hash of the current node is empty, that means it is a leaf node. 
     # Hence print sofar (sofar is a string containing the path as character sequences through which state transition occured) 
     if self.next.keys() == []: 
      print "Match:",sofar 
      return 

     if self.word_marker == True: 
      print "Match:",sofar 

     # Recursively call dfs for all the nodes pointed by keys in the hash 
     for key in self.next.keys(): 
      self.next[key].dfs(sofar+key) 

    def search(self, string, sofar=""): 
     '''Perform auto completion search and print the autocomplete results''' 
     # Make state transition based on the input characters. 
     # When the input characters becomes exhaused, perform dfs() so that the trie gets traversed upto leaves and print the state characters 
     if len(string) > 0: 
      key = string[0] 
      string = string[1:] 
      if self.next.has_key(key): 
       sofar = sofar + key 
       self.next[key].search(string,sofar) 

      else: 
       print "No match" 
     else: 
      if self.word_marker == True: 
       print "Match:",sofar 

      for key in self.next.keys(): 
       self.next[key].dfs(sofar+key) 


def fileparse(filename): 
    '''Parse the input dictionary file and build the trie data structure''' 
    fd = open(filename) 

    root = Node() 
    line = fd.readline().strip('\r\n') # Remove newline characters \r\n 

    while line !='': 
     root.add_item(line) 
     line = fd.readline().strip('\r\n') 

    return root 



if __name__ == '__main__': 

    if len(sys.argv) != 2: 
     print "Usage: ", sys.argv[0], "dictionary_file.txt" 
     sys.exit(2) 

    root = fileparse(sys.argv[1]) 

    print "Input:", 
    input=raw_input() 
    root.search(input) 

Answer 5

実装です： -

輸入java.util.HashMapを。

パブリッククラストライ{

class Node { 
    HashMap<Character, Node> children; 
    boolean end; 
    public Node(boolean b){ 
     children = new HashMap<Character, Tries.Node>(); 
     end = false; 
    } 
} 
private Node root; 
public Tries(){ 
    root = new Node(false); 
} 
public static void main(String args[]){ 
    Tries tr = new Tries(); 
    tr.add("dog"); 
    tr.add("doggy"); 

    System.out.println(tr.search("dogg"));; 
} 
private boolean search(String word) { 
    Node crawl = root; 
    int n = word.length(); 
    for(int i=0;i<n;i++){ 
     char ch = word.charAt(i); 
     if(crawl.children.get(ch) == null){ 
      return false; 
     } 
     else { 
      crawl = crawl.children.get(ch); 
      if(i==n-1 && crawl.end == true){ 
       return true; 
      } 

     } 
    } 
    return false; 
} 
private void add(String word) { 
    Node crawl = root; 
    int n = word.length(); 
    for(int i=0;i<n;i++){ 
     char ch = word.charAt(i); 
     if(crawl.children.containsKey(ch)){ 
      crawl = crawl.children.get(ch); 
     } 
     else { 
      crawl.children.put(ch, new Node(false)); 
      Node temp = crawl.children.get(ch); 
      if(i == n-1){ 
       temp.end = true; 
      } 
      crawl = temp; 
      System.out.println(ch + "  " + crawl.end); 

     } 
    } 
} 

}

ただ、ハッシュマップを使用して、単語の末尾を追跡します。