Saturday, November 19, 2016

Dictionary Implementation with Trie. Pattern Search will work for 355k words

import java.util.HashMap;

public class TrieNode
{
    private char character;
   
    private HashMap<Character, TrieNode> children;
   
    private boolean isEnd;
   
    TrieNode(char character)
    {
        this.character = character;
        children = new HashMap<>();
        isEnd = false;
       
    }
   
    public char getCharacter()
    {
        return character;
    }
   
    public void setCharacter(char character)
    {
        this.character = character;
    }
   
    public HashMap<Character, TrieNode> getChildren()
    {
        return children;
    }
   
    public void setChildren(HashMap<Character, TrieNode> children)
    {
        this.children = children;
    }
   
    public boolean isEnd()
    {
        return isEnd;
    }
   
    public void setEnd(boolean isEnd)
    {
        this.isEnd = isEnd;
    }
}





import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map.Entry;

public class TrieOperations
{
    private TrieNode root;
   
    private static int totalFoundWords;
   
    public TrieOperations()
    {
        root = new TrieNode((char)0);
        totalFoundWords =0;
    }
   
    public void insert(String word)
    {
        int length = word.length();
        TrieNode temp = root;
        for (int i = 0; i < length; i++)
        {
            char ch = word.charAt(i);
            HashMap<Character, TrieNode> child = temp.getChildren();
           
            if (child.containsKey(ch))
            {
                temp = child.get(ch);
            }
            else
            {
                TrieNode next = new TrieNode(ch);
                child.put(ch, next);
                temp = next;
            }
           
        }
        temp.setEnd(true);
    }
   
    public void patterMatching(String word)
    {
        int length = word.length();
        TrieNode temp = root;
        String value = "";
        boolean cont = false;
        for (int i = 0; i < length; i++)
        {
            char ch = word.charAt(i);
            HashMap<Character, TrieNode> child = temp.getChildren();
            if (child.containsKey(ch))
            {
                temp = child.get(ch);
                cont = true;
                value += ch;
            }
            else
            {
                cont = false;
                break;
            }
        }
        if (cont)
        {
            findPossibleStrings(value, temp);
        }
        System.out.println(totalFoundWords +" words are found");
       
    }
   
    private void findPossibleStrings(String value, TrieNode temp)
    {
        if (temp.isEnd())
        {
            System.out.println(value);
            totalFoundWords++;
        }
        HashMap<Character, TrieNode> child = temp.getChildren();
        for (Entry<Character, TrieNode> entry : child.entrySet())
        {
            value += entry.getKey();
            findPossibleStrings(value, entry.getValue());
            value = value.substring(0, value.length() - 1);
        }
    }
   
    public static void main(String[] args)
    {
        TrieOperations opr = new TrieOperations();
        //you can get the list of words from https://raw.githubusercontent.com/dwyl/english-words/master/words.txt
        File file = new File(Your list of words file);
        BufferedReader br = null;
        try
        {
            br = new BufferedReader(new FileReader(file));
            String line;
            while ((line = br.readLine()) != null)
            {
                opr.insert(line.trim());
            }
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        finally
        {
            if (null != br)
            {
                try
                {
                    br.close();
                }
                catch (IOException e)
                {
                    e.printStackTrace();
                }
            }
        }
        String input = "prabhu";
        opr.patterMatching(input);
    }
}