0

Java Trie の独自のバージョンを作成して作成するために必要な知識を得ようとしていますが、このプロジェクトには困惑しています。ここには非常に基本的な壊れたトライがあります。

Trie に 3 つの単語を追加しています (単語の最初の文字をキーとして使用し、値を追加の TrieNodes として使用します)。お気付きかもしれませんが、プログラムの実行中に isWord の値をチェックするために、TrieNode クラス内に print ステートメントがあります。単語の最後の文字の isWord 変数を True に設定します。したがって、単語の終わりを識別します (後で単語全体を取得するために使用します)。

最初に 3 つの単語を入力すると、出力はすべての単語のすべての文字を出力し、それらが Trie に入り、どの文字が単語の末尾であるかを正しく識別します。

ただし、単語を入力した直後にトライをトラバースし、トライのすべての文字とその isWord ステータスを再印刷すると、「Hello」の「e」が単語の末尾として突然識別されますか?

私はこれに何時間も注いでいますが、なぜこれが起こっているのかわかりません. 以下は作業コードです：

package testcode;


import java.util.*;

public class TestCode {

    public static Trie t;
    public static void main (String[] args){
        t = new Trie();
        t.addWord("hello");
        t.addWord("hi");
        t.addWord("soup");
        //at this point the output correctly identifies word endings.
        t.findWords();
        /* but when iterating through the hash map it becomes evident that
        * when entering the word 'hi' the 'e' in 'hello' had its isWord variable
        * changed to true. I followed the logic and I do not see how or why this
        * is happening.
        */
    }
}

//This Trie class handles the root trie, and Trie commands.
class Trie{
    private TrieNode root;

    public Trie(){
        root = new TrieNode();
    }

    public void addWord(String word){
        root.addWord(word.toLowerCase());
    }

    public void findWords(){
        root.findWords();
    }
}

//Trie Node handles the nodes and words within the trie
class TrieNode{

    private TrieNode parent;
    private boolean isWord;
    private boolean hasChildren;
    private char character;
    private Map<Character, TrieNode> children = new HashMap<>();

    public TrieNode(){

        hasChildren = false;
        isWord = false;
    }

    public TrieNode(String word){

        this();
        addWord(word);

    }
    public void addWord(String word){

       char firstChar = word.charAt(0);


       if (children.get(firstChar) == null){

           if(word.length() > 1){

               hasChildren = true;
               children.put(firstChar, new TrieNode(word.substring(1)));
               children.get(firstChar).parent = this;
               System.out.print(firstChar + "--");
               System.out.println(isWord);
           }

           else{
               children.put(firstChar, new TrieNode());
               if(character == 'e'){
                   System.out.println("shits about to go down");
               }
               isWord = true;
               System.out.print(firstChar + "--");
               System.out.println(isWord);
           }
           children.get(firstChar).character = firstChar;
       }

       else {
           children.get(firstChar).addWord(word.substring(1));
       }
   }

    public void findWords(){
        for(Character key : children.keySet()){
            children.get(key).findWords();
            System.out.println(children.get(key).character + " -- " + isWord);     
      }
    }
}

このコードは、次の出力を生成します。

o--true
l--false
l--false
e--false
h--false
i--true
p--true
u--false
o--false
s--false
p -- true
u -- false
o -- false
s -- false
o -- true
l -- false
l -- false
e -- true    //notice the e here is now suddenly a word ending with isWord = true
i -- true
h -- false
4

1 に答える 1

1

考えられる問題の範囲がありました..親子の混乱、親ノードでのリーフケースの処理、ビルドと印刷の両方など。

古い「findWords」コードでは、子文字を印刷していましたが、親は「isWord」フラグであることに注意してください。トライを構築すると、「子ノードが存在する」と「子ノードのパスを作成する」の間に望ましくない分岐がありました。そのため、「isWord」は既存のパスではなく、新しいパスでのみフラグを立てることができました。トライを構築すると、リーフ ノードではなく親に「isWord」が設定されるようにも見えました。

一般に、ネストされた IF ケースのスパゲッティであるコードは、信頼性が低い可能性が非常に高くなります。コードは可能な限り共通にする必要があります。実際に IF 内に属さない限り、コードはメソッドのメイン フローに保持します。

きれいで正しいコードは次のとおりです。

class TrieNode{
    private TrieNode parent;
    private boolean isWord;
    private boolean hasChildren;
    private char character;
    private Map<Character, TrieNode> children = new HashMap<>();

    public TrieNode(){
        this.hasChildren = false;
        this.isWord = false;
    }
    public TrieNode (char ch) {
        this.character = ch;
        this.hasChildren = false;
        this.isWord = false;
    }

    public void addWord (String word){
        if (word.length() == 0) {
            this.isWord = true;
            System.out.println( character + " -- " + isWord);
            return;
        }

        // represent the Child Node;
        //       --
        char firstChar = word.charAt(0);
        TrieNode child = children.get( firstChar);
        if (child == null){
            child = new TrieNode( firstChar);
            children.put( firstChar, child);
            child.parent = this;
            hasChildren = true;
        }

        // add Remaining Word;
        //      -- call for 1-length words, as 0-length at Child sets 'IsWord'!
        child.addWord( word.substring(1));

        // print building here.
        System.out.println( character + " -- " + isWord);
    }



    public void findWords(){
        for(Character key : children.keySet()){
            children.get(key).findWords();
        }
        System.out.println( character + " -- " + isWord);     
    }
}
于 2013-05-16T10:09:24.040 に答える