5

Trie Data Structure に格納されているすべての単語を出力または取得したいと考えています。これは、スペルミスのある単語と Dictionary 内の単語の間の編集距離を計算したいためです。したがって、Trie から各単語を取得し、編集距離を計算することを考えていました。しかし、私は取得することができません。このためのコードスニペットが必要です。HashMapこれは、JavaでTrieを使用して実装した方法です

Trie に保存されているすべての単語を出力するコードの書き方を教えてください。どんな助けでも大歓迎です

TrieNode.java

package triehash;
import java.io.Serializable;
import java.util.HashMap;

public class TrieNode implements Serializable {

HashMap<Character, HashMap> root;

public TrieNode() {
   root = new HashMap<Character, HashMap>();   
   }
}

TrieDict.java

package triehash;

import java.io.FileOutputStream;
import java.io.ObjectOutputStream;;
import java.io.Serializable;
import java.util.HashMap;
import java.io.Serializable;

public class TrieDict {   
 public  TrieNode createTree()
 {
     TrieNode t = new TrieNode();
     return t;
 }

 public void add(String s, TrieNode root_node) {
    HashMap<Character, HashMap> curr_node = root_node.root;
    s = s.toLowerCase();
    for (int i = 0, n = s.length(); i < n; i++) {
        Character c = s.charAt(i);
        if (curr_node.containsKey(c))
            curr_node = curr_node.get(c);
        else {
            curr_node.put(c, new HashMap<Character, HashMap>());
            curr_node = curr_node.get(c);
        }
    }
    curr_node.put('\0', new HashMap<Character, HashMap>(0)); // term
  }

 public void serializeDict(TrieNode root_node)
 {    
   try{
        FileOutputStream fout = new FileOutputStream("/home/priya/NetBeansProjects/TrieHash/dict.ser");

    ObjectOutputStream oos = new ObjectOutputStream(fout);   
    oos.writeObject(root_node);
    oos.close();
    System.out.println("Done");

   }catch(Exception ex){
       ex.printStackTrace();
   }
}

 public void addAll(String[] sa,TrieNode root_node) {
    for (String s: sa)
        add(s,root_node);
 }

 public static void main(String[] args)
 {
    TrieDict td = new TrieDict();
    TrieNode tree = td.createTree();

    String[] words = {"an", "ant", "all", "allot", "alloy", "aloe", "are", "ate", "be"};
    for (int i = 0; i < words.length; i++)
      td.add( words[i],tree);       
    td.serializeDict(tree); /* seriliaze dict*/
 }   
}
4

1 に答える 1

0

まず、インスタンス変数の宣言された型がroot少し変わっていることに注意してください。(具体的には、 の値の型は、HashMap<Character,HashMap>使用したいジェネリックの一部を除外します。) 以下のコードは機能するはずですが、この結果としていくつかの警告が表示されます。HashMap<Character,TrieNode>代わりに型を使用するようにコードをリファクタリングしてみてください。それが衒学的であれば申し訳ありません。:)

にメソッドとして追加して、これを試してくださいTrieNode：

public Set<String> computeWords() {
    Set<String> result;

    if(root.size() == 0)
        result = new HashSet<String>();
    else
        result = computeWords(root, "");

    return result;
}

protected static Set<String> computeWords(HashMap tree, String prefix) {
    Set<String> result=new HashSet<String>();

    if(tree.size() == 0)
        result.add(prefix);
    else
        for(Object o : tree.keySet()) {
            Character c=(Character) o;
            prefix = prefix+c;
            result.addAll(computeWords((HashMap) tree.get(c), prefix));
            prefix = prefix.substring(0, prefix.length()-1);
        }

    return result;
}

指定されたTrieNodeオブジェクトに対してt、t.computeWords()は でエンコードされたすべての単語のセットを返しますt。

これは、あなたが尋ねようとしていた質問に答えていると思います。ただし、ヘッダーに記載されているように質問に答えるには、次のようにすべての単語を出力しますt。

for(String word : t.computeWords())
    System.out.println(word);

HashSetまた、特に で大量のオブジェクトを作成するため、これは間違いなく最も効率的な実装ではありませんが、computeWords(HashMap,String)動作するはずです!

EDIT : このコードは、単語を空の で終了することも前提としていますHashMap。代わりに で単語を終了する場合は、メソッドのチェックを でnull更新する必要があります。申し訳ありませんが、それを呼び出す必要がありました。if(tree.size() == 0)staticif(tree == null)

編集: 明確でない場合に備えて、すべての単語を印刷する方法を説明しました。

編集: 空のトライ ケースを修正しました。

于 2013-04-15T04:55:28.377 に答える