java - 使用 Trie 实现 T9 字典？

Question

我必须实现 T9 词典。

基本上，当我按下 9 个键中的任何一个时，它应该向我显示可以使用该组合键开头的前 5 个单词。

如果我输入“46”，它会根据我是否输入“酒店”或“好”当我按下 4 时，我的意思是“g”或“h”。

优先级是根据哪些词比较流行——你可以使用，比方说，从顶部开始的前 5000 个词 100 000话。

我正在做的代码是:

导入

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

此代码在添加到 Trie 时给出空指针异常我找不到解决方案请帮忙

Answer 1

1 - 您的文件不包含字符。它是二进制的，因此您应该使用 FileInputStream 对象来读取它。

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