4

私はJavaが初めてで、非常に単純な「単語補完」プログラムを作成したいと考えています。辞書ファイルを読み取り、その単語をノード配列 (サイズ 26) に再帰的に追加します。私はこれをうまくやったと信じていますが、一致をどのように処理して印刷するかはわかりません。テストのために、関数を呼び出して現時点で 2 つの単語を挿入しています。すべてが機能したら、ファイルを読み取り、単語からジャンクを削除するメソッドを追加します。

例: 「test」と「tester」という単語がツリー内にあり、ユーザーが「tes」と入力すると、「test」と「tester」が表示されます。

誰かが（もしあれば）マッチを調べて印刷する方法を教えていただければ、本当に感謝しています. 完全なコードは以下のとおりです。

ありがとうございました

4

2 に答える 2

3

あなたが実装したものは"trie"と呼ばれ ます。既存の実装を見たいと思うかもしれません。

子ノードを格納するために使用したものはハッシュ テーブルと呼ばれ、非常に具体的な理由がない限り、標準の実装を使用して自分で実装することは避けた方がよいでしょう。実装にはいくつかの制限があります (文字範囲など)。

あなたのコードには method にバグがあると思いますhas：

...
else if (letter[val].flag==true || word.length()==1) {
    return true;
}

で始まる文字列がある場合にそのメソッドが true を返すことを意図している場合、wordチェックすべきではありませんflag。完全一致のみが存在する場合に true を返す必要がある場合は、チェックしないでくださいword.length()。

そして最後に、あなたの質問に対処します。最適ではありませんが、最も簡単な解決策は、文字列を受け取り、その文字列に一致するノードを返すメソッドと、ノードからすべての単語を構成するメソッドを作成することです。このようなもの（テストされていません）：

class Tree {

    ...
    public List<String> matches(CharSequence prefix) {
        List<String> result = new ArrayList<>();
        if(r != null) {
            Node n = r._match(prefix, 0);
            if(n != null) {
                StringBuilder p = new StringBuilder();
                p.append(prefix);
                n._addWords(p, result);
            }
        }
        return result;
    }
}

class Node {

    ...
    protected Node _match(CharSequence prefix, int index) {
        assert index <= prefix.length();
        if(index == prefix.length()) {
            return this;
        }
        int val = prefix.charAt(index) - 'a';
        assert val >= 0 && val < letter.length;
        if (letter[val] != null) {
            return letter[val].match(prefix, index+1);
        }
        return null;
    }

    protected void _addWords(StringBuilder prefix, List<String> result) {
        if(this.flag) {
            result.add(prefix.toString());
        }    
        for(int i = 0; i<letter.length; i++) {
            if(letter[i] != null) {
                prefix.append((char)(i + 'a'));
                letter[i]._addWords(prefix, result);
                prefix.delete(prefix.length() - 1, prefix.length());
            }
        }
    }
}
于 2013-04-16T08:10:58.350 に答える