Implement T9 Dictionary using Trie?

Question

I have to implement the T9 Dictionary .

Essentially, when I am pressing any of the 9 keys, it should show me the top 5 words that can be started with that combination of keys.

If I type '46', it can give 'hotel' or 'good' depending on whether I intended 'g' or 'h' when I pressed 4.

The priority is based on which words are relatively popular - you can use, say, the first 5000 words from the top 100 000 words.

The code I am doing is:

Import

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.Date;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

T9Dict class

public class T9Dict {

    private static final Runtime s_runtime = Runtime.getRuntime();

    public static void main(String[] args) throws Exception {

        runGC();
        long heap1 = usedMemory();

        long start = new Date().getTime();
        Trie trie = Trie.getInstance();
        System.out.println("Creating Dictionary");
        File f = new File("C:\\Users\\hp1\\Desktop\\100kfound.txt");
        BufferedReader br = new BufferedReader(new FileReader(f));
        String s = br.readLine();
        int i = 0;
        do {
            i++;
            trie.add(s);
            s = br.readLine();
        } while (s != null);
        br.close();
        long end = new Date().getTime();
        long time = (end - start);
        System.out.println("Loaded Dictionary with " + i + " words in " + time
                + " msec");

        // runGC();
        long heap2 = usedMemory(); // take an "after" heap snapshot:
        System.out.println("Memory used = " + (heap2 - heap1));

        String pattern = "4663";
        start = new Date().getTime();
        String word = trie.getWord(pattern);
        end = new Date().getTime();
        time = (end - start);
        System.out.println("Found word : " + word + " in " + time + " msec");

    }

    private static void runGC() throws Exception {
        // for whatever reason it helps to call Runtime.gc()
        // using several method calls:
        for (int r = 0; r < 4; ++r) {
            _runGC();
        }
    }

    private static void _runGC() throws Exception {
        long usedMem1 = usedMemory();
        long usedMem2 = Long.MAX_VALUE;

        for (int i = 0; (usedMem1 < usedMem2) && (i < 1000); ++i) {
            s_runtime.runFinalization();
            s_runtime.gc();
            Thread.currentThread().yield();

            usedMem2 = usedMem1;
            usedMem1 = usedMemory();
        }
    }

    private static long usedMemory() {
        return s_runtime.totalMemory() - s_runtime.freeMemory();
    }
}

Trie class

class Trie {

    private static final String regex = "[a-zA-Z]*";
    private static Trie instance = null;
    Node root = null;
    Map<Character, Integer> map = new HashMap<Character, Integer>();

    private Trie() {
        map.put('a', 2);
        map.put('b', 2);
        map.put('c', 2);
        map.put('d', 3);
        map.put('e', 3);
        map.put('f', 3);
        map.put('g', 4);
        map.put('h', 4);
        map.put('i', 4);
        map.put('j', 5);
        map.put('k', 5);
        map.put('l', 5);
        map.put('m', 6);
        map.put('n', 6);
        map.put('o', 6);
        map.put('p', 7);
        map.put('q', 7);
        map.put('r', 7);
        map.put('s', 7);
        map.put('t', 8);
        map.put('u', 8);
        map.put('v', 8);
        map.put('w', 9);
        map.put('x', 9);
        map.put('y', 9);
        map.put('z', 9);
    }

    private int getVal(char c) {
        return map.get(c);
    }

    public static Trie getInstance() {
        if (instance == null) {
            synchronized (Trie.class) {
                instance = new Trie();
            }
        }
        return instance;
    }

    public String getWord(String pattern) {
        String s = null;
        Node node = root;
        int i = 0;
        int num = 0;
        while (i < pattern.length()) {
            num = pattern.charAt(i) - '0';
            if (num == node.val) {
                i++;
                if (i == pattern.length()) {
                    s = node.list.get(0);
                }
                node = node.middle;
            } else if (num < node.val) {
                if (i == pattern.length()) {
                    s = node.list.get(0);
                }
                node = node.left;
            } else {
                if (i == pattern.length()) {
                    s = node.list.get(0);
                }
                node = node.right;
            }

        }
        return s;
    }

    public void add(String s) {

        if (s.length() > 0) {
            s = s.toLowerCase();
            System.out.println("Adding : " + s);
            if (root == null) {
                root = new Node(this.getVal(s.charAt(0)));
                Node node = root;
                Node temp = null;
                for (int i = 1; i < s.length(); i++) {
                    temp = new Node(getVal(s.charAt(i)));
                    node.middle = temp;
                    node = temp;
                    if (i == s.length() - 1) {
                        temp.set(s);
                    }
                }
            } else {
                Node node = root;
                int i = 0;
                Node temp = null;
                int val = 0;
                while (i < s.length()) {
                    val = getVal(s.charAt(i));
                    if (node.val == val) {
                        if (i == s.length() - 1) {
                            node.set(s);
                            i++;
                        } else {
                            i++;
                            if (node.middle == null) {
                                while (i < s.length()) {
                                    val = getVal(s.charAt(i));
                                    temp = new Node(val);
                                    node.middle = temp;
                                    node = temp;
                                    if (i == s.length() - 1) {
                                        temp.set(s);
                                    }
                                    i++;
                                }
                            } else {
                                node = node.middle;
                            }
                        }
                    } else if (val < node.val) {
                        if (node.left == null) {
                            temp = new Node(val);
                            node.left = temp;
                            node = temp;
                            if (i == s.length() - 1) {
                                temp.set(s);
                            } else {
                                i++;
                                while (i < s.length()) {
                                    val = getVal(s.charAt(i));
                                    temp = new Node(val);
                                    node.middle = temp;
                                    node = temp;
                                    if (i == s.length() - 1) {
                                        temp.set(s);
                                    }
                                    i++;
                                }
                            }

                        } else {
                            node = node.left;
                        }
                    } else {
                        if (node.right == null) {
                            temp = new Node(val);
                            node.right = temp;
                            node = temp;
                            if (i == s.length() - 1) {
                                temp.set(s);
                            } else {
                                i++;
                                while (i < s.length()) {
                                    val = getVal(s.charAt(i));
                                    temp = new Node(val);
                                    node.middle = temp;
                                    node = temp;
                                    if (i == s.length() - 1) {
                                        temp.set(s);
                                    }
                                    i++;
                                }
                            }
                        } else {
                            node = node.right;
                        }
                    }
                }
            }
        }
    }
}

Node class

class Node {

    int val;
    Node left;
    Node middle;
    Node right;
    List<String> list = new LinkedList<String>();

    public Node(int val) {
        this.val = val;
    }

    public void set(String s) {
        list.add(s);
    }

    public String toString() {
        return String.valueOf(val);
    }
}

This code is giving nullpointerexception when adding to Trie I cannot find the solution please help

Answer 1

When I run this I find that the exception occurs on this line:

root = new Node(this.getVal(s.charAt(0)));

Let's unroll this, you're passing the first character of the "word" (ie the String, s) to the getVal(), and this in turn will return an int if, and only if, that character is a lowercase letter, a-z.

When I run the file the "word" is 6724 yahoo - this is the first line of the dictionary text file you linked to. There is nothing in your code to clean up this line to get to the actual word itself, instead you are facing a series of spaces and then a number.

So the reason it fails is because you're effectively going this.getVal(" "). If you call map.get() and the key doesn't exist it'll return null (as described in the Map documentation).

One simple way of getting to the word itself and not the whitespace or frequency number is to first process the string:

s = s.trim(); // removes all leading and trailing whitespace
String word = s.substring(s.indexOf(" ")+1); // extract just the word after the space

And then you can pass the first character of word:

root = new Node(this.getVal(word.charAt(0)));

Answer 2

1 - You File doesn't contains characters. It is binary so you should use FileInputStream object to read it.

2 - In reading file and adding string in your Trie you should verify that this string is not null, otherwise it can throws a NullPointerException. You can run your file like this: