Wie drucke ich alle Wörter, die in einem Tree gespeichert sind, wo Trie mit Hashmap in Java implementiert wurde?

Question

Ich möchte alle in Trie Data Structure gespeicherten Wörter drucken oder abrufen. Das ist, weil ich Edit-Abstand zwischen einem falsch geschriebenen Wort und einem Wort in Dictionary berechnen möchte. Daher dachte ich daran, jedes Wort von Trie abzurufen und Entfernung zu berechnen. Aber ich kann nicht abrufen. Ich möchte ein Code-Snippet dafür. Dies ist, wie ich die Trie mit HashMap in Java implementiert

Jetzt sagen Sie mir, wie Sie Code zum Drucken aller Wörter in Trie gespeichert schreiben. Jede Hilfe wird sehr geschätzt

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*/ 
} 
} 

Answer 1

Erstens ist es erwähnenswert, dass der deklarierte Typ des root Instanz-Variable ist eine etwas merkwürdig. (Speziell der Werttyp HashMap<Character,HashMap> schließt einige Generika aus, die Sie lieber verwenden würden.) Der folgende Code sollte funktionieren, Sie erhalten jedoch einige Warnungen. Sie könnten versuchen, Ihren Code zu refaktorieren, um stattdessen den Typ HashMap<Character,TrieNode> zu verwenden. Entschuldigung, wenn das pedantisch ist. :)

die Sie interessieren, hinzugefügt, wie Methoden 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; 
} 

Für ein gegebenes TrieNode Objekt t, t.computeWords() die Menge aller Wörter Wörter in t codiert zurückkehren würde.

Ich glaube, das beantwortet die Frage, die Sie stellen wollten. Um jedoch die Frage zu beantworten, wie im Header angegeben, dann würden Sie alle Wörter für die gleiche t wie folgt drucken:

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

Auch dies ist definitiv nicht die effizienteste Implementierung, zumal wir ein erstellen Bündel von HashSet Objekte in computeWords(HashMap,String), aber es sollte funktionieren!

BEARBEITEN: Dieser Code setzt auch voraus, dass Sie Wörter mit einem leeren HashMap beenden. Wenn Sie stattdessen Wörter mit null beenden, müssen Sie die if(tree.size() == 0) Überprüfung in der static Methode mit if(tree == null) aktualisieren. Tut mir leid, hätte das heraus rufen sollen.

BEARBEITEN: Erklärt, wie alle Wörter gedruckt werden, nur für den Fall, dass es nicht klar war.

BEARBEITEN: Leeren Gehäuse repariert.