さらに処理するために格納する必要がある n ビットのバイナリ文字列を生成する C++ でアプリケーション用のプログラムを作成する必要があります。
質問 1) ただし、新しい文字列が生成されるたびに、データベースに既に存在するかどうかを確認する必要があります。ある場合は、追加しないでください。
考えられる方法の 1 つは、キーがバイナリ文字列の 10 進数値であるルックアップ用のハッシュ テーブル (STL マップなど) を維持することです。しかし、問題は n が非常に大きくなる可能性があるため、10 進数値を格納することが現実的ではないことです。つまり、 n が 200+ まで大きくなる場合があります。
また、n ビット文字列のビットが指定されていない場合もあります。例:- n = 4 の場合、文字列は 01xx の形式になります。下位 2 ビットは指定されていません。この場合、 01xx は実際には、完全に指定された 4 つの 4 ビット文字列 ( 0100,0101,0110,0111 ) を表します。したがって、01xx がデータベースにあり、0110 が生成された場合、0110 はデータベースに格納されません。
これを確認する効率的な方法を教えてください。
どういうわけか私が思いつくことができるのは:-
1) 文字列のデータベース全体を検索し、新しく生成された文字列を 1 つずつデータベース内の文字列と比較します。これは素朴な方法であり、複雑さは O(mn) です。ここで、m は現在データベースにある文字列の数です。
2) 文字列を二分決定木型構造に格納します。このタイプの方法では、ルックアップは対数になりますか?
3) 文字列内の各ビット位置について - 値が指定されている文字列を保存します。例:- n = 4 の場合、データベースに :- 01xx と 1xx1 が含まれている場合、この情報は次のように保存できます:-
0 - 1xx1
1 -
2 - 01xx
3 - 01xx、1xx1
0 は LSB が設定されていることを示します。3 は、MSB が設定されていることを示します。したがって、 0101 などの新しい文字列が生成された場合、 2 または 3 で検索できます。この方法は、メモリ使用量が高いようです。
この文字列検索を行うための効率的な方法をいくつか提案できますか?
質問 2) C++ の実装に関しても、これらの n ビット文字列を格納する効率的な方法は何ですか? ほとんどの場合、n ビット列のビットの大部分は指定されていないことに注意してください。したがって、n に比例するメモリ内のスペースを確保する代わりに、指定されたビットのみを格納する方が理にかなっています。
つまり、n は 10 かもしれません。しかし、生成される文字列は :- 1x1xxxxxxx のようなものかもしれません。この場合、 {(9,1),(7,1)} のようなものを保存する方が理にかなっています。では、文字列を 2 タプルのベクトルとして保存する必要がありますか? その場合、これらの文字列のデータベースを保存する良い方法は何でしょうか?