aplicación trie

Question

Estoy tratando de poner en práctica una forma muy sencilla Trie en Java que soporta 3 operaciones. Me gustaría que tuviera un método de inserción, un método tiene (es decir, es una palabra determinada en el trie), y un método toString para devolver el trie en forma de cadena. Creo que tengo la inserción de funcionar correctamente, pero tiene toString y están demostrando ser difícil. 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 la clase nodo

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 realizar una inserción, inserción se llama en ese nodo raíz, que forma recursiva crea un nuevo nodo en la posición correcta, y continúa hasta que la palabra esté completa. Creo que el método funciona correctamente.

Mi función se tiene muy roto, porque Tienes a que tienen instrucción de retorno fuera de los soportes 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 debe trabajar con algunos ajustes, pero no puedo averiguar por la vida de mí.

toString es una bestia que he tratado de abordar, pero nada que lanzar en él trabaja, así que va a dejar que sea hasta que resolver el problema tiene. Si me tiene trabajando que puede ser capaz de averiguar una manera de que lo hace en una función toString.

El propósito de la int val = word.charAt (0) - 64; es debido a que cada cadena introducida debe ser todo en mayúsculas (Voy a crear una cadena de formatear la función de asegurar esto después) de modo int valor de la primera letra - 64 será su posición en la matriz. es decir, índice de matriz 0 es A, por lo que 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

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

Answer 2

Tal vez sólo puede utilizar "Mapa C" en lugar de "c TrieNode []", que permitirá utilizar esto para todos los tipos de caracteres en mayúsculas / minúsculas e incluso caracteres especiales e incluso se ahorrará espacio (la asignación de 26 matriz de caracteres en cada nivel de caracteres)

Answer 3

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 4

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

Answer 5

Este mapa Trie implementos has (llamado get en esta aplicación) y toString

Answer 6

Aquí está la aplicación Java sencilla sin necesidad de utilizar 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());
    }


}