la mise en œuvre Trie

Question

Je cherche à mettre en œuvre un très simple Trie Java qui prend en charge 3 opérations. Je voudrais qu'il ait une méthode d'insertion, une méthode a (c.-à-est un certain mot dans la structure arborescente), et une méthode toString pour retourner la structure arborescente sous forme de chaîne. Je crois que je l'insertion fonctionne correctement, mais a et toString se révèlent être difficile. Voici ce que j'ai à ce jour.

La classe 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"));
    }
}

Et la classe de noeud

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

Donc, fondamentalement, lors de la création d'un Trie, un TrieNode est créé comme la racine avec 26 enfants. Quand un insert est tentée, insérer est appelée sur ce nœud racine, ce qui crée récursive un nouveau noeud à la position correcte et continue jusqu'à ce que le mot est terminé. Je crois que la méthode fonctionne correctement.

Ma a fonction est très cassé, parce que je Vous pour avoir cette déclaration de retour à l'extérieur des supports pour une raison quelconque. Je ne peux pas le contenir dans une clause else ou le compilateur se plaint. A part cela, je pense que la méthode devrait fonctionner avec quelques modifications, mais je ne peux pas le comprendre pour la vie de moi.

toString est une bête que j'ai essayé d'aborder, mais rien que je jette à cela fonctionne, alors je vais laisser ce soit jusqu'à ce que je résoudre le problème a. Si je me fait travailler, je peux être en mesure de trouver un moyen de le reformater en fonction toString.

Le but de l'int val = word.charAt (0) - 64; est parce que chaque chaîne entrée doit être tout en majuscules (je vais créer une chaîne fonction de formatage pour en assurer par la suite) si la première valeur int de lettre - 64 sera sa position dans le tableau. ie index de tableau est 0 A, si A = 64, A - 64 = 0. B = 65, B -. 64 = 1, et ainsi de suite

Answer 1

Votre fonction has devrait probablement ressembler à ceci:

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

Vous effectuez l'appel récursif, mais vous avez vraiment besoin de laisser cette valeur se propage en arrière vers l'appelant d'origine.

Answer 2

Peut-être que vous pouvez utiliser « Carte c » au lieu de « TrieNode [] c », qui vous permettra de l'utiliser pour tous les types de caractères majuscules / minuscules et même des caractères spéciaux et même sauverait vous l'espace (allocation 26 tableau de caractères à chaque niveau de caractères)

Answer 3

Voici mon implémentation: -

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

Voici mon implémentation:

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

les outils de cette carte Trie has (appelé get dans cette mise en œuvre) et toString

Answer 6

est simple implémentation Java sans utiliser toute autre structure de données

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


}