暗号テキストを検索し、暗号内の文字の頻度カウントを返す Java プログラムを作成したいと考えています。
2文字出現:
pk = 2、ke = 2、ld = 2
3 文字出現:
pke = 2。
これを可能な限り効率的に実行できるアルゴリズムはありますか?
4938 次
8 に答える
4
HashMap<String, Integer>マップ戦略は良いものですが、カウントされる文字のタプルであるため、私は.
暗号文の文字を反復処理すると、最後の X 文字を保存できます。これにより、長さ X+1 の部分文字列のすべての出現に対するマップが得られます。
于 2009-11-27T10:27:01.980 に答える
2
n-gramをtrieに格納し、通常の順序を逆にして、n-gram の最後の文字が trie の一番上に来るようにすることができます。トライの各ノードには、文字数が格納されます。文字列をループして、最後の N 文字を追跡します ( Buhb が示唆するように)。外側のループを通過するたびに、最後の N 文字を使用してパスを選択し、最後の文字から始まり、最後から N番目の文字で終わるトライをトラバースします。アクセスするノードごとに、そのカウンターをインクリメントします。
n-gram 頻度を出力するには、トライの幅優先トラバーサルを実行します。
全体的なパフォーマンスは演習として残しました。
于 2009-11-27T12:05:28.240 に答える
2
通常のアプローチは、ある種のマップを使用してキャラクターをカウントにマップすることです。HashMap<Character, Integer>たとえば、を使用できます。次に、暗号文を文字単位で反復処理し、その文字をカウント 1 でマップに入れる (まだ存在しない場合) か、そのカウントをインクリメントします。
于 2009-11-27T10:14:51.787 に答える
1
ハッシュまたはグラフを使用できます (outis のおかげで、特別な名前になっていることがわかりました。そのような種類のグラフは "trie" と呼ばれます)。ハッシュは遅くなり、グラフは速くなります。ハッシュはより少ないメモリを取得し、グラフは不適切な実装でより多くを消費します。
文字シーケンスの最大長がテキストの長さと等しく、テキストが十分に長い場合、大量のメモリを取得するため、配列を使用して実行することはできません。制限すると、4つの小文字/大文字シーケンスのメモリ([number of letters]^[max sequence length])*4となるバイトのようなsmthが得られます。(52^4)*4 ~= 24Mbシーケンスの長さが制限されていても問題がなく、このメモリ量がアルゴリズムよりも正常である場合、シーケンス内の文字が 4 文字以下の場合、アルゴリズムは非常に簡単になります。
于 2009-11-27T10:45:32.387 に答える
1
可能な値ごとにセルを含む配列を用意するか (暗号テキストがすべて小文字の場合は簡単 - 26 - そうでない場合は難しい)、文字を渡して値をインクリメントする Map を選択します。配列は高速ですが、柔軟性が低くなります。
于 2009-11-27T10:16:25.780 に答える
1
必要なシーケンスの長さのセットが固定されている場合、明らかなアルゴリズムは線形数のカウント操作を行います (たとえば、ハッシュテーブルでカウンターを検索してインクリメントします)。
「可能な限り効率的に」と言うとき、わずかな定数係数の改善に多大な労力を費やすことを提案しますか、サブリニアアルゴリズムを絶望的に検索しますか、それともアルゴリズムの複雑さのクラスをまったく理解していませんか?
于 2009-11-27T12:15:49.033 に答える
0
これに関しては、答えを考えていませんが、
しかし、このアルゴリズムは、辞書アプローチで圧縮ファイルを作成するために圧縮アルゴリズムで使用されるアルゴリズムとまったく同じだと思います。
私が間違っていなければ、このアプローチでは、辞書は次のように使用されます。
データ：
abccccabaccabcaaaaabcaaabbbbbccccaaabcbbbbabbabab
解析 1 : キー: * 値: abc
新しいデータ:
*cccabacc*aaaa*aaabbbbbccccaa*bbbbabbabab
経験に基づいた推測ですが、標準の「zip」ファイルはこのアプローチを使用していると思います（ここではわかりません）ので、これらのアルゴリズムを確認することをお勧めします
于 2009-11-27T12:39:25.030 に答える
0
最初に可能な限り最大の反復可能なシーケンスを探すことから始めて、そこから下に向かって作業することができます。たとえば、文字列が 10 文字の場合、発生する可能性のある最大の反復可能なシーケンスは 5 文字の長さになるため、最初に 5 文字のシーケンスを探し、次に 4 文字というように、2 に達するまで繰り返します。これにより、プログラムの反復回数が減るはずです。
于 2009-11-27T11:18:42.250 に答える