問題タブ [bitstring]

プロジェクト オイラー数219を実行しようとしていますが、それを把握できていません。プロジェクトオイラーによると、Pythonを使用しようとしていますが、1分以内に実行できるはずです! これは、Pythonでは遅すぎるため、個々のビット文字列を計算することをおそらく望んでいないと考えるようになります.sub O(n)アルゴリズムが必要です。

新しいビット文字列をすばやく選択し、それらをグループで考慮することさえできるように、ビット文字列の可能なプレフィックスを格納する再帰的なソリューションを見てきました。これは、10 を少し超える値までのブルート フォース値でのみ機能します。

これを過ぎると、問題を軽減する方法を理解するのに苦労しています。次のようなパターンを作成することは常に可能です。

ただし、ビット文字列が 7 つを超える場合は最適ではありません。私が考慮すべきことについて誰かが私を導くことができますか？

ビット フラグのシーケンスを表す 16 進文字の 256 文字の文字列があり、それらをビット文字列に変換して&、|、vecなどで操作できるようにしようとしています。16 進文字列は、整数幅のビッグ エンディアン グループに書き込まれます。たとえば、8 バイトのグループがビット文字列 に"76543210"変換されます。"\x10\x32\x54\x76"つまり、最下位の 8 ビットは00001000です。

問題は、pack" h" 形式が一度に 8 バイトではなく 1 バイトの入力に対して機能するため、直接使用しただけでは正しい順序で結果が得られないことです。現時点では、私はこれをやっています：

これは機能しますが、ハックな感じがします。もっときれいな方法があるはずですが、私のpack-fu はあまり強くありません。この翻訳を行うためのより良い方法はありますか?

ビット文字列として解釈される MATLAB uint32 が与えられた場合、文字列に含まれる非ゼロ ビットの数を効率的かつ簡潔にカウントする方法は何ですか?

ビットをループする実用的で単純なアプローチがありますが、それは私のニーズには遅すぎます。(std::bitset count() を使用した C++ 実装はほぼ瞬時に実行されます)。

さまざまなビット カウント手法をリストしている非常に優れたページを見つけましたが、簡単な MATLAB 風の方法があることを願っています。

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

更新 #1

Brian Kernighan アルゴリズムを次のように実装しました。

パフォーマンスは依然として悪く、4096^2 の重み計算を計算するのに 10 秒以上かかります。std::bitset の count() を使用する私の C++ コードは、これを 1 秒未満の時間で実行します。

アップデート #2

これまでに試した手法の実行時間の表を次に示します。追加のアイデアや提案があれば更新します。

コメント: MATLAB の dec2bin() 関数は、実装が非常に不十分なようです。実行速度が非常に遅いです。

コメント: 「Naive bitget loop」アルゴリズムは次のように実装されています。

コメント: シャイナーのアルゴリズムのループ展開バージョンは次のようになります。

Scott さん、BitString プログラムに感謝します。私は中性子検出器からのデータの解釈に取り組んでいますが、このモジュールがまさに必要なツールであることがわかりました。残念ながら、モジュールが test-bitstring.py に合格するまでにはまだ時間がかかります。Windows XP と Python 3.1 を実行しています。ファイル bitstring-0.4.1.zip を Web サイトからダウンロードし、bitstring.py と test-bitstring.py の両方を Python ディレクトリの \lib フォルダーに抽出しました。test-bitstring.py を実行すると、11 個のエラーが発生します。:(

正しいバージョンをダウンロードしたこと、および両方の .py ファイルが \lib フォルダーに正常に作成されたことを 3 回確認しました。BitString で Windows を使用すると、既知の問題はありますか? それはおそらく私がやっていることですが、ここからどこへ行くべきか途方に暮れています。ドキュメントでは、バージョンが正しく、エラーが続く場合は連絡するように明示的に述べています。明らかな何かが欠けていることは確かですが、これがある種の互換性の問題ではないことを確認したかったのですか?

これを読んでいただきありがとうございます。お手数をおかけして申し訳ありません。もしあなたが私に返事をくれる機会があれば、なぜそれがテストに失敗するかもしれないとあなたが考えているのか、私はとても興味があります. 再度、感謝します！

ビット文字列にビット文字列サイズ n の 2 つの連続するビット文字列が n 回未満であるかどうかを確認する方法を見つけようとしています。

たとえば、ビット文字列のサイズが 5 (インデックス 0 ～ 4) であるとします。インデックス 1 と 3 が両方とも 0 の場合、false を返すことができます。しかし、それらが両方とも1つである場合、答えを見つけるために5つのピークを実行する必要がある場合があります.

ビット文字列の長さは 5 である必要はありません。簡単にするために、3 から 8 の間でよいとしましょう。

私たちは、 DES アルゴリズム(暗号化と復号化に使用される)の Java 実装を作成するように依頼されました。いくつか質問がありました：

1. DES では、64 ビットのプレーン テキストまたは暗号テキストと、正確に 56 ビットの共有キーが必要であると指定されています。バイト数を与えるメソッドは何ですか?

2. このアルゴリズムでは、64 ビットを 2 つの 32 ビット セクションに分割するなど、多くのビット レベル操作が使用されます。これはどのように行うことができますか？

動機

P2P ソフトウェアのように、部分的にダウンロードされるハフマン圧縮ファイルを想像してみてください。最初にファイル全体にディスク領域を割り当ててから、ランダムなファイル チャンクのダウンロードを開始します。ハフマン コードの 1 つ (ただしどれかはわかりません) は終了コードであるため、このコードがデコードされた場合は停止します。ファイルがいくつかの huffman 圧縮ストリームで構成されていると仮定すると、ダウンロードが完了する前にそれらのいくつかを解凍することを試みることができます。

ここで、ディスク スペースを事前に割り当てる方法が重要です。ハフマン ストリームが開始されたとしますが、まだ完了していないため、事前に割り当てられたディスク スペースが不足しているとします。通常、このスペースはすべて 0 なので、ハフマン コードでシンボルをデコードし続けます00..。これが最終コードでない場合、「無効な」データに気付かず、事前に割り当てられたスペースが 2 GB ある場合は、無駄なデコードを行っていることになります。

そのため、できるだけ早くデコードを停止する方法でスペースを事前に割り当てたいと考えています。

質問

「ハフマン ターミネータ」として機能する最短のビット文字列を探しています。つまり、この文字列をデコードすると、すべてのハフマン コードが少なくとも 1 回デコードされるため、確実に終了コードを受け取ることができます。これは、長さ1..nビットのハフマン コードのすべての組み合わせで機能するはずです。

00..注: 上記の仮想シナリオ (エンド コードとして使用、まだダウンロードされていないチャンクを検出するために P2P セグメント データを使用)に対する簡単な解決策があることは知っていますが、これは「ハフマン ターミネータ」の理論的な使用法を示すシナリオの例にすぎません。ビット文字列、私はこのシナリオを解決することに興味はありませんが、「ハフマンターミネーター」として機能するビット文字列を生成/見つけるためのアルゴリズム/方法/アイデアを探しています。

例

n = 2、[0, 1]、[00, 01, 1]、[0, 10, 11]の可能なハフマン コードの組み合わせを見てみましょう[00, 01, 10, 11]。1..n次に、可能なすべての長さのビット シーケンス( 0、1、00、01、10)を含むビット文字列から始めましょう11。

001011

さまざまなハフマン コードの組み合わせでデコードすると、次のようになります (ハフマン コードはシンボルに割り当てられますA..D)。

これは良いスタートであり、最初の 3 つのハフマン コードはすべて既にデコードされていますが、 でデコードすると[00, 01, 10, 11]、シンボルB(ハフマン コード01) が失われます。それでは、これをビット文字列に追加しましょう。

00101101

n=2これは、長さが 8 ビットの有効な「ハフマン ターミネータ」です。このバイトを使用してディスク領域を事前に割り当てておけば、2 ビットを超えないすべてのハフマン コードを確実に終了させることができます。各シンボルを 1 回デコードするn=2ための組み合わせの最小の長さであるため、より短いターミネータ文字列が存在しないこともわかっています。[00, 01, 10, 11]

n=3、 （43ビット）の「ハフマンターミネータ」も見つけました0001011001110100111010011100010101111101110が、それが正しいかどうか100％確信が持てず、最短のものかどうかもわかりません。

私が探しているもの

• 特定の のハフマン ターミネータを検索または生成するアルゴリズム/アイデアn。私の試みは例に似ています: 開始文字列を生成し、必要に応じてビットを追加して、すべての異なるハフマン コードの組み合わせを満たします。しかし、もっと良い方法があると確信しています。

• 特定のハフマンターミネータn=8およびn=16

• この問題 (または類似の問題) に関する論文/リンクがある場合。

ボーナス

「ハフマン ターミネータ」を見つけるためのボーナス ポイントは、ビット位置 から開始しても機能する1..nため、データが以前にデコードされた場合でも終了し、最初のビットで新しいハフマン コードに到達して開始することはありません。

更新: python-bitstring 3.0.0 のステップには従来の意味があります

私は python bitstringを使用しています。ファイルからロードされた ConstBitArray があり、1 とは異なるステップでスライスを取得したいと考えています。

通常のリストでは、次のようにします。

ただし、ビット文字列にはステッピングの奇妙な定義があります。以下を参照してください。

http://packages.python.org/bitstring/slicing.html#stepping-in-slices

誰かがそれを行う方法を知っていますか?

ありがとう

バイナリ プロトコルからメッセージをデコードするコードを書いています。各メッセージ タイプには 1 バイトのタイプ ID が割り当てられ、各メッセージにはこのタイプ ID が含まれます。メッセージはすべて、5 つのフィールドで構成される共通のヘッダーで始まります。私の API は単純です。

私の最初の本能は、メッセージ タイプごとに 1 つのデコード関数を記述してパターン マッチングに大きく依存し、fun 引数でそのメッセージ タイプを完全にデコードすることです。

メッセージの最初の 5 つのフィールドは構造的に同じですが、その後のフィールドはメッセージ タイプごとに異なることに注意してください。

およそ 20 のメッセージ タイプがあるため、上記のような 20 の関数があります。この構造で完全なメッセージを複数回デコードしていますか? 慣用句ですか？関数ヘッダーのメッセージ タイプ フィールドをデコードしてから、メッセージ本文のメッセージ全体をデコードしたほうがよいでしょうか?

次の関数をよりエレガントなものに置き換えようとしています:

(私は今、これは末尾再帰ではありません -- シンプルに保ちたかったのですが、Erlang の新しいバージョンではパフォーマンスが問題にならないことに加えて)

出力例:

リスト内包表記を使用したエレガントなソリューションが望ましいでしょう。これは、この結果がリスト内包表記でさらに処理され、1 つの内包表記にラップできるためです。

私は試した

ただし、Size が の倍数でない場合、これは最後のチャンクを除外しますbyte_site(P)。