使用Trie实现T9字典？
我必须实现T9字典。
基本上，当我按下9个按键中的任何一个时，它应该显示可以用该组合键启动的前5个单词。
如果我输入’46’，它可以给’酒店’或’好’，这取决于当我按下4时我是打算’g’还是’h’。
优先级取决于哪些单词相对受欢迎 – 例如，您可以使用前100,000个单词中的前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(); } }
特里class
class Trie { private static final String regex = "[a-zA-Z]*"; private static Trie instance = null; Node root = null; Map map = new HashMap(); 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 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 list = new LinkedList(); public Node(int val) { this.val = val; } public void set(String s) { list.add(s); } public String toString() { return String.valueOf(val); } }
这个代码在添加到Trie时给出nullpointerexception我无法找到解决方案请帮忙
1 – 您的文件不包含字符。 它是二进制的，因此您应该使用FileInputStream对象来读取它。
2 – 在读取文件并在Trie中添加字符串时，您应该validation此字符串不为null，否则它会抛出NullPointerException 。 您可以像这样运行文件：
当我运行它时，我发现此行发生exception：
root = new Node(this.getVal(s.charAt(0)));
让我们展开这个，你将“word”的第一个字符（即String， s ）传递给getVal() ，这反过来将返回一个int，当且仅当该字符是小写字母时， AZ。
当我运行文件时，“word”是6724 yahoo – 这是你链接到的字典文本文件的第一行。 您的代码中没有任何内容可以清理此行以获取实际的单词本身，而是面向一系列空格，然后是数字。
所以它失败的原因是因为你有效地去了这个this.getVal(" ") 。 如果你调用map.get()并且密钥不存在，它将返回null（如Map文档中所述 ）。
获取单词本身而不是空白或频率数字的一种简单方法是首先处理字符串：
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)));