Implementación de Trie

Question

Estoy intentando implementar un Trie muy simple en Java que admite 3 operaciones. Me gustaría tener un método insert, un método has (es decir, una palabra determinada en el trie) y un método toString para devolver el trie en forma de cadena. Creo que la inserción funciona correctamente, pero has y toString están resultando ser difíciles. Esto es lo que tengo hasta ahora.

La clase trie.

public class CaseInsensitiveTrie implements SimpleTrie { 

    //root node 
    private TrieNode r; 

    public CaseInsensitiveTrie() { 
     r = new TrieNode(); 
    } 

    public boolean has(String word) throws InvalidArgumentUosException { 
     return r.has(word); 
    } 

    public void insert(String word) throws InvalidArgumentUosException { 
     r.insert(word); 
    } 

    public String toString() { 
     return r.toString(); 
    } 

    public static void main(String[] args) { 

     CaseInsensitiveTrie t = new CaseInsensitiveTrie(); 

     System.out.println("Testing some strings"); 
     t.insert("TEST"); 
     t.insert("TATTER"); 
     System.out.println(t.has("TEST")); 
    } 
} 

Y el nodo de clase

public class TrieNode { 

    //make child nodes 
    private TrieNode[] c; 
    //flag for end of word 
    private boolean flag = false; 

    public TrieNode() { 
     c = new TrieNode[26]; //1 for each letter in alphabet 
    } 

    protected void insert(String word) { 
     int val = word.charAt(0) - 64; 

     //if the value of the child node at val is null, make a new node 
       //there to represent the letter 
     if (c[val] == null) { 
      c[val] = new TrieNode(); 
     } 

     //if word length > 1, then word is not finished being added. 
     //otherwise, set the flag to true so we know a word ends there. 
     if (word.length() > 1) { 
      c[val].insert(word.substring(1)); 
     } else { 
      c[val].flag = true; 
     } 
    } 

    public boolean has(String word) { 
     int val = word.charAt(0) - 64; 
     if (c[val]!=null && word.length()>1) { 
      c[val].has(word.substring(1)); 
     } else if (c[val].flag==true && word.length()==1) { 
      return true; 
     } 

     return false; 
    } 

    public String toString() { 
     return ""; 
    } 
} 

Así que, básicamente, al crear un trie, un TrieNode se crea como la raíz con 26 niños. Cuando se intenta insertar, se invoca a ese nodo raíz, que recursivamente crea un nuevo nodo en la posición correcta, y continúa hasta que la palabra se completa. Creo que ese método está funcionando correctamente.

Mi función tiene muy rota, porque I tiene para tener esa declaración de devolución fuera de los paréntesis por alguna razón. No puedo contenerlo dentro de una cláusula else o el compilador se queja. Aparte de eso, estoy pensando que el método debería funcionar con algunos ajustes, pero no puedo resolverlo por mi vida.

toString es una bestia que he intentado abordar, pero nada de lo que arroje funciona, así que lo dejo hasta que resuelva el problema. Si tengo funciona, puedo encontrar una manera de reformatearlo en una función toString.

El propósito de int val = word.charAt (0) - 64; es porque cada cadena ingresada debe ser mayúscula (crearé una función de formateo de cadena para asegurar esto luego) para que el valor int de la primera letra - 64 sea su posición en la matriz. es decir, el índice de matriz 0 es A, entonces A = 64, A - 64 = 0. B = 65, B - 64 = 1, y así sucesivamente.

Answer 1

Su función has probablemente debería tener este aspecto:

if (c[val]!=null && word.length()>1) { 
    return c[val].has(word.substring(1)); //<-- Change is on this line 
} else if (c[val].flag==true && word.length()==1) { 
    ...etc 

de realizar la llamada recursiva, pero que realmente necesita para que ese valor se propagan de vuelta a la llamada original.

Answer 2

Tal vez solo puede usar "Mapa c" en lugar de "TrieNode [] c", que le permitiría usar esto para todos los tipos de caracteres mayúsculas/minúsculas e incluso caracteres especiales e incluso le ahorraría espacio (asignación serie 26 caracteres en cada nivel del personaje)

Answer 3

This Trie Map implementa has (called get in this implementation) y toString

Answer 4

Aquí está mi aplicación: -

public class Tries { 

class Node { 
    HashMap<Character, Node> children; 
    boolean end; 
    public Node(boolean b){ 
     children = new HashMap<Character, Tries.Node>(); 
     end = false; 
    } 
} 
private Node root; 
public Tries(){ 
    root = new Node(false); 
} 
public static void main(String args[]){ 
    Tries tr = new Tries(); 
    tr.add("dog"); 
    tr.add("doggy"); 

    System.out.println(tr.search("dogg")); 
    System.out.println(tr.search("doggy")); 
} 
private boolean search(String word) { 
    Node crawl = root; 
    int n = word.length(); 
    for(int i=0;i<n;i++){ 
     char ch = word.charAt(i); 
     if(crawl.children.get(ch) == null){ 
      return false; 
     } 
     else { 
      crawl = crawl.children.get(ch); 
      if(i==n-1 && crawl.end == true){ 
       return true; 
      } 

     } 
    } 
    return false; 
} 
private void add(String word) { 
    Node crawl = root; 
    int n = word.length(); 
    for(int i=0;i<n;i++){ 
     char ch = word.charAt(i); 
     if(crawl.children.containsKey(ch)){ 
      crawl = crawl.children.get(ch); 
     } 
     else { 
      crawl.children.put(ch, new Node(false)); 
      Node temp = crawl.children.get(ch); 
      if(i == n-1){ 
       temp.end = true; 
      } 
      crawl = temp; 
      System.out.println(ch + "  " + crawl.end); 

     } 
    } 
} 

} 

Answer 5

Aquí es sencilla aplicación java sin u cantar cualquier otra estructura de datos

import java.util.ArrayList; 
import java.util.List; 

class Trie { 

    private static Node root = new Node(' ', false); 

    static int getIndex(char x) { 
     return ((int) x) - ((int) 'a'); 
    } 

    static class Node { 
     char data; 
     boolean isLeaf; 
     Node[] children; 

     Node(char data, boolean leaf) { 
      this.data = data; 
      this.isLeaf = leaf; 
      this.children = new Node[26]; 
     } 

    } 

    static void insert(String data, Node root) { 
     if (data == null || data.length() == 0) { 
      return; 
     } 
     Node child = root.children[getIndex(data.charAt(0))]; 
     if (child == null) { 
      Node node = new Node(data.charAt(0), data.length() == 1); 
      root.children[getIndex(data.charAt(0))] = node; 
      if (data.length() > 1) { 
       insert(data.substring(1, data.length()), node); 
      } 
     } else { 
      if (data.length() == 1) { 
       child.isLeaf = true; 
      } else { 
       insert(data.substring(1, data.length()), child); 
      } 
     } 
    } 

    static boolean find(String data, Node root) { 
     if (data == null || data.length() == 0) { 
      return true; 
     } 
     char x = data.charAt(0); 
     //note that first node ie root is just dummy, it just holds important 
     Node node = root.children[getIndex(x)]; 
     if (node == null) { 
      return false; 
     } else { 
      if (data.length() == 1) { 
       return node.isLeaf; 
      } else { 
       return find(data.substring(1, data.length()), node); 
      } 
     } 
    } 

    static boolean delete(String data, Node root) { 
     if (data == null || data.length() == 0) { 
      return false; 
     } 
     char x = data.charAt(0); 
     //note that first node ie root is just dummy, it just holds important 
     Node node = root.children[getIndex(x)]; 
     if (node == null) { 
      return false; 
     } else { 
      if (data.length() == 1) { 
       node.isLeaf = false; 
       boolean allNull = true; 
       for (Node node1 : node.children) { 
        allNull = allNull && node1 == null; 
       } 
       return allNull; 
      } else { 
       boolean delete = delete(data.substring(1, data.length()), node); 
       if (delete) { 
        node.children[getIndex(x)] = null; 
        if(node.isLeaf){ 
         return false; 
        } 
        boolean allNull = true; 
        for (Node node1 : node.children) { 
         allNull = allNull && node1 == null; 
        } 
        return allNull;    } 
      } 
     } 
     return false; 
    } 


    private static List<String> strings = new ArrayList<>(); 

    private static List<String> getAll() { 
     strings = new ArrayList<String>(); 
     findAllDFS(root, ""); 
     return strings; 
    } 

    private static void findAllDFS(Node node, String old) { 
     if (node != null) { 
      if (node.data != ' ') { 
       old = old + node.data; 
      } 
      if (node.isLeaf) { 
       strings.add(old); 
      } 
      for (Node node1 : node.children) { 
       findAllDFS(node1, old); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     insert("abc", root); 
     insert("xyz", root); 
     insert("abcd", root); 
     insert("abcde", root); 


     delete("abcd", root); 

/*  System.out.println(find("abc", root)); 
     System.out.println(find("abcd", root)); 
     System.out.println(find("ab", root)); 
     System.out.println(find("xyz", root));*/ 


     System.out.println(getAll()); 
    } 


} 

Answer 6

Aquí mi aplicación:

public class Tries { 
private static class Leaf { 
    private Leaf(char c) { 
     this.c=c; 
    } 
    char c; 
    int counter = 1; 
    List<Leaf> leaves = new ArrayList<>(10); 
} 
private Leaf root = new Leaf('0'); 
public void add(String word) { 
    Leaf current = root; 
    Leaf newLeaf = null; 
    for (char c : word.toCharArray()) { 
     boolean found = false; 
     for (Leaf leaf : current.leaves) { 
      if (leaf.c == c) { 
       current = leaf; 
       current.counter++; 
       found=true; 
       break; 
      } 
     } 
     if (!found) { 
      newLeaf = new Leaf(c); 
      current.leaves.add(newLeaf); 
      current = newLeaf; 
     } 
    } 
} 
public int find(String partial) { 
    Leaf current = root; 
    for (char c : partial.toCharArray()) { 
     boolean found = false; 
     for (Leaf leaf : current.leaves) { 
      if (leaf.c == c) { 
       current=leaf; 
       found=true; 
       break; 
      } 
     } 
     if(!found) return 0; 
    } 
    return current.counter; 
} 

public boolean hasWord(String partial) { 
    return find(partial)>0; 
    } 
}