writing trie implementation

This question h开发者_JAVA技巧as been asked many times and I googled many places but still couldn't find one place where I can get step-by-step instruction for writing trie implementation. Please help me out preferred language is Java or Python

Thank you

I have written a tries for string searching in java. Its pretty simple: here are the steps:

Node class is like this:

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);
  }

you can create search etc on the same line.

#!/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)

I'm not a Java or Python coder, but can give you a very simple c# trie implementation. It's very very simple so I'm sure you could map it to Java.

Here it is:

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

Done. Told you it was simple. But it is a trie and it works.

Here is implementation:-

import java.util.HashMap;

public class Tries {

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);

        }
    }
}

}

Just use hashmap and keep track of end of word.