編寫特爾執行

Question

這個問題已經被問了很多次，我GOOGLE了很多地方，但仍然找不到一個地方，我可以得到編寫特里執行的分步指令。請幫我出 首選語言Java或Python
謝謝

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或Python編碼器，但可以給你一個很簡單的C＃實現特里。這非常非常簡單，所以我相信你可以將它映射到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); 

     } 
    } 
} 

}

只需使用HashMap和跟蹤字的結束。