Trie implementation

Question

Я пытаюсь реализовать очень простую Trie в Java, которая поддерживает 3 операции. Я бы хотел, чтобы у него был метод insert, есть метод (т. Е. Это определенное слово в trie) и метод toString для возврата trie в строковой форме. Я считаю, что у меня правильно работает вставка, но есть и toString, которые оказались трудными. Вот что я до сих пор.

Три класса.

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

И узел класса

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

Так в основном, при создании TRIE, TrieNode создается как корень с 26 детьми. Когда попытка вставки выполняется, вставка вызывается в этом корневом узле, который рекурсивно создает новый узел в правильном положении и продолжается до тех пор, пока слово не будет завершено. Я считаю, что этот метод работает правильно.

У меня есть функция очень сломанная, потому что у меня есть, чтобы иметь эту инструкцию возврата за пределами скобок по какой-то причине. Я не могу содержать его в предложении else или компилятор жалуется. Помимо этого, я думаю, что метод должен работать с некоторыми настройками, но я не могу понять это для жизни меня.

toString - это зверь, с которым я пытался справиться, но ничто не бросает на него, поэтому я оставлю это до тех пор, пока не решит проблему. Если у меня есть работа, я могу составить способ переформатировать ее в функцию toString.

Цель int val = word.charAt (0) - 64; потому что каждая введенная строка должна быть все шапки (я буду создавать функцию форматирования строк, чтобы гарантировать это впоследствии), поэтому значение int первой буквы - 64 будет ее позицией в массиве. т.е. индекс массива 0 равен A, поэтому A = 64, A - 64 = 0. B = 65, B - 64 = 1 и т. д.

Answer 1

Ваша has функция должна, вероятно, выглядеть следующим образом:

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 

Вы выполняете рекурсивный вызов, но вам действительно нужно, чтобы это значение распространяется обратно к первоначальному абоненту.

Answer 2

Возможно, вы можете использовать «Map c» вместо «TrieNode [] c», что позволит вам использовать это для всех типов символов в верхнем и нижнем регистре и даже специальных символах и даже позволит вам сэкономить место (выделение массив 26 символов на каждом уровне персонажа)

Answer 3

This Trie Map реализует has (called get in this implementation) и toString

Answer 4

Вот моя реализация: -

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

Вот простая реализация Java без тебя петь любую другую структуру данных

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

Вот моя реализация:

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