Реализовать словарь T9 с помощью Trie?
Я должен реализовать словарь T9.
По сути, когда я нажимаю любую из 9 клавиш, она должна показать мне 5 лучших слов, которые можно начать с этой комбинации клавиш.
Если я наберу "46", он может дать "hotel" или "good" в зависимости от того, имел ли я в виду "g" или "h", когда нажимал 4.
Приоритет зависит от того, какие слова относительно популярны - вы можете использовать, скажем, первые 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;
Класс T9 Dict
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 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, я не могу найти решение, пожалуйста, помогите
2 ответа
Когда я запускаю это, я обнаруживаю, что исключение происходит в этой строке:
root = new Node(this.getVal(s.charAt(0)));
Давайте развернем это, вы передаете первый символ "слова" (то есть строка, s) к getVal(), и это, в свою очередь, вернет int, если и только если этот символ является строчной буквой, az.
Когда я запускаю файл, "слово" 6724 yahoo - это первая строка текстового файла словаря, на который вы ссылаетесь. В вашем коде нет ничего, чтобы очистить эту строку, чтобы перейти к самому слову, вместо этого вы сталкиваетесь с рядом пробелов, а затем с числом.
Так что причина этого не в том, что вы this.getVal(" "), Если вы позвоните map.get() и ключ не существует, он вернет ноль (как описано в документации к карте).
Один простой способ получить само слово, а не пробел или номер частоты, это сначала обработать строку:
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)));
1 - Ваш файл не содержит символов. Это двоичный файл, поэтому вы должны использовать FileInputStream возражать, чтобы прочитать это.
2 - При чтении файла и добавлении строки в ваш Trie вы должны убедиться, что эта строка не нулевая, иначе она может выдать NullPointerException, Вы можете запустить свой файл так: