4

ファイルからツリーを構築するにはどうすればよいですか? それらをファイルから読み込んで、適切なレベルに追加できるようにしたい

4

3 に答える 3

2

あなたはトライを実装しようとしているようです。

Java での優れた実装については、こちらをご覧ください: http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

于 2013-04-09T16:48:52.613 に答える
1

追加する

ルートから始めて、最初の (または現在の) 文字を検索します。その文字が見つかった場合は、そのノードに移動して次の文字を検索します。文字が見つからない場合は、現在の文字に一致する単語を検索します。類似する単語があれば、現在の文字を新しいノードとして追加し、両方の単語をその下に移動します。そうでない場合は、単語を追加します。

注:これにより、例に示されているツリーよりも検索用に最適化されたツリーが作成されます。(adamant と adapt は別の 'a' ノードの下にグループ化されます)

更新: Trieに関するウィキペディアの記事を参照してください。

于 2013-04-08T18:18:44.693 に答える
1

リーフ (実際の単語) の前にツリーに 2 つのレベルしかない場合は、単純に 28 要素の配列から始めて、文字をインデックスに変換できます (つまり、a==1、b==2 など)。配列の要素は、完全な単語を含むセット/リストにすることができます。配列とリストを遅延して作成できます (つまり、ルート配列を作成し、他の配列と単語のリストに null を使用し、必要に応じて配列/リストを作成します)。

正しく従うべきルールを読んでいますか?

PS私は、それぞれがフルサイズの配列を使用しても、スペースが無駄になることはなく、非常に高速に対処できるはずだと思います

更新: @ user1747976、まあ、各配列には約 28*4 または 28*8 ビット + 12 バイトのオーバーヘッドがかかります。配列ごとに 28*4+12=116 バイトになるように、圧縮された ops を使用してください。メモリを効率的に使用するか、処理を効率的に使用するかによって異なります。メモリ効率を高めるために、配列の代わりにある種のハッシュマップを使用できますが、追加のオーバーヘッドが配列で使用するものよりも少ないかどうかはわかりません。ただし、処理は確かに悪くなります。ツリー部門の要件に応じて、巧妙なループを何度も使用する必要があります。ツリーに挿入するための醜い疑似コード:

root=new Object[28];
word="something";
pos = root;
wordInd=1;
for (int i=1; i<=TREE_DEPTH ; i++) {
   targetpos = letterInd(letter(wordInd,word));
   if (i==TREE_DEPTH) {
      if (pos[targetpos] == null) pos[targetpos] = new HashSet<String>();
      (Set) pos[targetpos].add(word);
      break;
   } else {
      if (pos[targetpos] == null) pos[targetpos] = new Object[28];
      wordInd++;
      pos = pos[targetpos];
   }
}

単語の取得に使用できる同様のループ。

于 2013-04-08T18:23:31.970 に答える