使用Trie实现T9字典？

Question

我必须实现T9字典。

本质上，当我按下这9个键中的任何一个时，它应该给我显示前5个单词，它们可以以键的组合开始。

如果我键入'46'，它可以给‘酒店’或‘好’取决于我是否打算'g‘或'h’时，我按4。

优先级是基于哪个单词比较受欢迎--比如说，您可以使用来自顶级100000单词的前5000个单词。

我正在做的代码是：

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类

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

节点类

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

这段代码给出了nullpointerexception，当添加到Trie时，我找不到解决方案，请帮助

Answer 1

当我运行这个程序时，我发现异常发生在这一行上：

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

让我们展开它，将"word“(即字符串，s)的第一个字符传递给getVal()，这反过来将返回一个int当且仅当该字符是小写字母a。

当我运行该文件时，"word“是6724 yahoo --这是您链接到的字典文本文件的第一行。您的代码中没有任何东西可以清除这一行以获取实际的单词本身，相反，您将面临一系列空格，然后是一个数字。

因此，它失败的原因是因为您正在有效地使用this.getVal(" ")。如果调用map.get()而密钥不存在，它将返回null (如地图文件中所述)。

获取单词本身而不是空格或频率号的一种简单方法是首先处理字符串：

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

然后您可以传递word的第一个字符

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

Answer 2

你的文件不包含字符。它是二进制的，所以应该使用FileInputStream对象来读取它。

2-在读取文件和在Trie中添加字符串时，您应该验证该字符串不是空的，否则它会抛出一个NullPointerException。您可以这样运行您的文件：