"Prosta" implementacja narzędzia Trie

Question

Muszę zaimplementować Trie (w języku Java) dla projektu uczelnianego. Trie powinien móc dodawać i usuwać struny (dla fazy 1).

Spędziłem kilka godzin każdego dnia (przez kilka ostatnich dni) próbując dowiedzieć się, jak to zrobić i nieudane za każdym razem.

Potrzebuję pomocy, przykłady w internecie i moim podręczniku (Struktury danych i algorytmy w Javie autorstwa Adama Drozdka) nie pomagają.

Informacja

1. zajęcia węzłów Pracuję z:

   class Node { 
       public boolean isLeaf; 
   } 
   
   class internalNode extends Node { 
       public String letters; //letter[0] = '$' always. 
       //See image -> if letter[1] = 'A' then children[1] refers to child node "AMMO" 
       //See image -> if letter[2] = 'B' then children[2] refers to internal node "#EU" 
       public TrieNode[] children = new TrieNode[2]; 
   
       public TrieInternalNode(char ch) 
       { 
        letters = "#" + String.valueOf(ch);//letter[0] = '$' always. 
        isLeaf = false; 
       } 
   } 
   
   class leafNode extends Node 
   { 
       public String word; 
       public TrieLeafNode(String word) 
       { 
        this.word = new String(word); 
        isLeaf = true; 
       } 
   } 
   

2. A oto kod pseudo dla wstawki, że muszę podążać (Uwaga: to jest bardzo niejasne)

   trieInsert(String K) 
   { 
       i = 0; 
       p = the root; 
       while (not inserted) 
       { 
        if the end of word k is reached 
         set the end-of-word marker in p to true; 
        else if (p.ptrs[K[i]] == 0) 
         create a leaf containing K and put its address in p.ptrs[K[i]]; 
        else if reference p.ptrs[K[i]] refers to a leaf 
        { 
         K_L = key in leaf p.ptrs[K[i]] 
         do 
         { 
          create a nonleaf and put its address in p.ptrs[K[i]]; 
          p = the new nonleaf; 
         } while (K[i] == K_L[i++]); 
        } 
        create a leaf containing K and put its address in p.ptrs[K[--i]]; 
        if the end of word k is reached 
         set the end-of-word marker in p to true; 
        else 
         create a leaf containing K_L and put its address in p.ptrs[K_L[i]]; 
        else 
         p = p.ptrs[K[i++]]; 
       } 
   } 
   

3. Potrzebuję zastosować następujące metody.

   public boolean add(String word){...}//adds word to trie structure should return true if successful and false otherwise 
   
   public boolean remove(String word){...}//removes word from trie structure should return true if successful and false otherwise 
   

4. nie mogę znaleźć pseudo kod do usuwania, ale jeśli wkładka nie działa usuwać przyzwyczajenie mi pomóc.

5. Oto obraz, jak powinien wyglądać Trie, który powinienem wdrożyć.

1. Zdaję sobie sprawę, że Trie nadal będą nieefektywne jeśli realizowane w ten sposób, ale w tej chwili nie muszę się o to martwić.

2. Książka stanowi implementację, która jest podobna do tego, co trzeba zrobić, ale nie korzysta z końca char słowa („$”), a tylko przechowuje słowa bez ich przedrostków u dziecka węzłów http://mathcs.duq.edu/drozdek/DSinJava/SpellCheck.java

Ograniczenia

1. muszę wdrożyć Trie w Javie.
2. Nie mogę importować ani używać żadnej z wbudowanych struktur danych Java. (tzn. bez mapy, HashMap, ArrayList itp.)
3. Mogę używać tablic, typów pierwotnych Java i ciągów Java.
4. Trie musi użyć symbolu $ (dolar), aby wskazać koniec słowa. (Patrz rysunek poniżej)

5. mogę asume że teraz słowo zawierające $ symbol będzie włożony.
6. Muszę zaimplementować Trie w tym samym stylu co książka.
7. Sprawa słów nie ma znaczenia, np.wszystkie słowa będą uważane za małe litery:
8. Trie powinny przechowywać tylko znak końca słowa i znaki odnoszące się do słowa, a nie cały alfabet (jak niektóre implementacje).

Nie oczekuję, że ktokolwiek wykona dla mnie wdrożenie (chyba że ma kogoś w pobliżu: P) Po prostu potrzebuję pomocy.

Answer 1

Po pierwsze, nie sądzę, że należy rozdzielać poszczególne węzły liści i wewnętrzne węzły. Polecam tworzenie uniwersalnej klasy węzła za pomocą metody isLeaf(). Ta metoda zwróci wartość true, jeśli węzeł nie ma elementów podrzędnych.

Oto kilka pseudokodów wyższego poziomu dla funkcji, które należy wdrożyć. Dla uproszczenia przyjmuję istnienie metody o nazwie getIndex(), która zwraca indeks odpowiadający znakowi.

Insert(String str) 
    Node current = null 
    for each character in str 
     int index = getIndex(character) 
     if current.children[index] has not been initialized 
      initialize current.children[index] to be a new Node 
     current = current.children[index] 

Możesz łatwo zwiększyć ten pseudokod w zależności od potrzeb. Na przykład, jeśli chcesz return false gdy wstawiania nie powiedzie:

• return false, jeśli ciąg wejściowy jest null
• return false, jeśli ciąg wejściowy zawiera nieprawidłowe znaki

Teraz tutaj jest jakiś pseudokod na wyższym poziomie do usunięcia.

Remove(String str) 
    Node current = null 
    for each character in str 
     int index = getIndex(character) 
     current = current.children[index] 

    // At this point, we found the node we want to remove. However, we want to 
    // delete as many ancestor nodes as possible. We can delete an ancestor node 
    // if it is not need it any more. That is, we can delete an ancestor node 
    // if it has exactly one child. 

    Node ancestor = current 
    while ancestor is not null 
     if ancestor has 2 or more children 
      break out of loop 
     else if ancestor has less than 2 children 
      Node grandAncestor = ancestor.parent 
      if grandAncestor is not null 
       reinitialize grandAncestor.children // this has the effect of removing ancestor 

     ancestor = ancestor.parent 

Na bardzo wysokim poziomie śledzimy ciąg wejściowy do węzła, który chcemy usunąć. Następnie przechodzimy w górę drzewa po wskaźnikach rodzica i usuwamy każdy węzeł z 1 dzieckiem (ponieważ nie jest już potrzebny). Gdy dotrzemy do węzła z 2 dziećmi, zatrzymujemy się.

jak Insert, możemy łatwo rozszerzyć ten Pseudokod do return false gdy usunięcie nie jest udany:

• return false, jeśli ciąg wejściowy jest null
• return false, jeśli ciąg wejściowy zawiera nieprawidłowe znaki
• return false, jeśli ciąg wejściowy prowadzi do węzła, który nie istnieje

najłatwiej jest wdrożenie usunąć, jeśli klasa ma pole węzła nadrzędnego. Jednak możliwe jest zastosowanie metody bez punktów rodzicielskich, ale jest trudniejsze. Możesz zobaczyć przykład trudniejszej implementacji here.