trie

trie

关注
发信
关注(28)粉丝(399)

使用Trie实现T9词典？

本文介绍了使用Trie实现T9词典？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述



基本上，当我按下9个键中的任何一个时，它应该显示
前5个字如果我输入'46'，它可以给'酒店'或'好'，这取决于是否I
当我按下4时，打算用'g'或'h'。

优先级是基于哪些单词比较流行 - 您可以使用
从顶部的字开始，前5000个字。



我正在执行的代码是：

导入 

  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（创建字典）; 
文件f =新文件（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（+时间
 +msec中带有+ i +的加载字典）; 
 
 // runGC（）; 
 long heap2 = usedMemory（）; //取一个之后堆快照：
 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（在+ time +msec中找到word：+ word +）; 
 
 
 $ b private static void runGC（）throws Exception {
 //无论什么原因，它有助于调用Runtime.gc（）
 //使用几种方法调用：
 for（int r = 0; r  _runGC（）; 
 
 
 
 private static void _runGC（）throws Exception {
 long usedMem1 = usedMemory（）; 
 long usedMem2 = Long.MAX_VALUE; （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（）; 
 
 
 code $ t 
 
  Trie class   p> 
 
 
  class Trie {
 
 private static final String regex =[a-zA-Z] *; 
 private static Trie instance = null; 
节点root = null; 
地图<字符，整数> 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）; 
 
 $ b public static Trie getInstance（）{
 if（instance == null）{
 synchronized（Trie.class）{
 instance = new特里结构（）; 
} 
} 
返回实例; 
} 
 
 public String getWord（String pattern）{
 String s = null; 
节点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  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 = root; 
节点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; 
节点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; 
节点离开; 
节点中间; 
节点权利; 
列表< 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）; 
 
 
 $ / code> 
当添加到Trie $ b时，此代码给出nullpointerexception $ b我找不到解决方案，请帮忙解决方案

当我运行这个时，我发现这行发生了异常： p> 

  root = new Node（this.getVal（s.charAt（0）））;

让我们展开这个，你传递word的第一个字符（即String， s ）添加到 getVal（）中，并且当且仅当该字符是一个小写字母，az。



当我运行文件时，word是 6724 yahoo - 这是您链接到的字典文本文件的第一行。在你的代码中没有任何东西可以清理这一行来得到实际的单词本身，而是面对一系列空格，然后是一个数字。



它失败的原因是你实际上要去 this.getVal（）。如果您调用 map.get（）并且该键不存在，它将返回null（如）。



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

  s = s.trim（）; //删除所有前导和尾随空白
 String word = s.substring（s.indexOf（）+1）; //在空格之后提取单词

然后您可以传递<$ c的第一个字符
$ b $ $ $ $ $ $ $ c $ root $ new Node（this.getVal（word.charAt（0 ）））;


I have to implement the T9 Dictionary .

Essentially, when I am pressing any of the 9 keys, it should show methe 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 Iintended 'g' or 'h' when I pressed 4.

The priority is based on which words are relatively popular - you canuse, 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 TrieI cannot find the solution please help

解决方案

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

这篇关于使用Trie实现T9词典？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！

10-15 08:35
Powered by LMLPHP ©2024 trie 0.004790