Was kann eine schnellere Implementierung von Trie für den folgenden Anwendungsfall sein?

Question

Ich versuche, die problem zu lösen, im Wesentlichen müssen wir alle Wörter aus dem Wörterbuch finden, die das gegebene Präfix in lexikographischer Reihenfolge haben.

Ich benutze Trie Datenstruktur für die Aufgabe, aber meine Lösung einfach mal auf den Richter, was kann ein effizienter/schneller Weg, um dieses Problem zu lösen?

Meine aktuelle Implementierung ist

class trie{ 
    node root=new node(); 
    class node{ 
     node child[]=new node[26]; 
     boolean is_leaf=false; 
    } 

    public void add(char c[]) 
    { 
     node root=this.root; 
     int pos=0,c1=0; 
     while(pos<c.length) 
     { 
      c1=c[pos]-'a'; 
      if(root.child[c1]==null) 
      { 
       root.child[c1]=new node(); 
      } 
      root=root.child[c1]; 
      pos++; 
     } 
     root.is_leaf=true; 
    } 
    public ArrayList<String> search(String s) 
    { 
     char c[]=s.toCharArray(); 
     node root=this.root; 
     int pos=0,c1=0; 
     while(pos<c.length) 
     { 
      c1=c[pos]-'a'; 
      if(root.child[c1]==null) 
      { 
       root.child[c1]=new node(); 
      } 
      root=root.child[c1]; 
      pos++; 
     } 
     ArrayList<String> ans=new ArrayList<>(); 
     build_recursive(root,s,new StringBuilder(),ans); 
     return ans; 

    } 
    public void build_recursive(node root,String prefix,StringBuilder cur, ArrayList<String> ans) 
    { 
     if(root.is_leaf&&cur.length()!=0) 
     { 
      String s=prefix+cur.toString(); 
      ans.add(s); 
     } 

     for(int i=0;i<26;i++) 
     { 
      if(root.child[i]!=null) 
      { 
       char c=(char) (i+'a'); 
       cur.append(c); 
       build_recursive(root.child[i], prefix, cur, ans); 
       cur.deleteCharAt(cur.length()-1); 

      } 
     } 
    } 

} 

Die Funktion Suchen die sortierte Liste aller Wörter gibt, die dem angegebenen Präfix teilen.

Gibt es auch eine bessere Datenstruktur, die ich dafür verwenden könnte?

Answer 1

Versuche, einen Teilstring eines anderen Strings zu finden. Sie suchen jedoch nach Wörtern in einem Wörterbuch - ein Teilstring-Matching ist nicht wirklich notwendig. Sobald Sie das erste Wort mit dem Präfix gefunden haben, wird das nächste Wort, wenn es existiert, direkt daneben stehen. Keine komplexe Suche erforderlich!

Versuche verursachen auch viel Aufwand, da sie aus Knoten aufgebaut werden, die dann mit Zeigern (= zusätzlichen Platzanforderungen) referenziert werden müssen. Zeiger sind langsam. In C++ Iteration verknüpfter Listen can be 20x slower als Iterieren von Arrays, sofern die Knoten nicht alle schön geordnet sind. Sortierung

mit n = Worte O (n), die Arraylist:

Dieses Problem kann, sehr wahrscheinlich über

• Lesen aller Wörter in einem Arraylist mit String gelöst werden O (n log n)
• und für jedes Präfix Abfrage,
  • binary search das erste Spiel für das Präfix zu finden Verwendung: O (log n), und es wird bereits umgesetzt in der Standardbibliothek
  • aufeinanderfolgende Elemente der Rückkehr, die passen bis Spiele erschöpft sind: O (m), m = Anzahl der Spiele

Dies ist schneller als Tries auf theoretische Komplexität und und viel aufgrund schneller Speicherlayout - Messing mit Zeigern, wenn Sie dies nicht tun müssen, ist teuer.