クワイン・マクラスキー法とペトリック法による論理圧縮
「クワイン・マクラスキー法とペトリック法による論理圧縮アルゴリズムをCで実装」
http://qiita.com/jun6231jp/items/41b492ce31a109e4cec6
のソースを改造しました。
改造点は
- オンメモリで動作するように。
- ロジックを整理して高速化
- 複数出力に対応
などです。
make
qmc filename
入力ファイルは 0個以上のスペース又はタブのあと 1こ以上の '0' か '1' そのあと1こ以上のスペース又はタブのあと 1こ以上の '0' か '1 それ以外の文字が出てきたら無視。 入力の無い行は無視します。
sample/7seg.tblを参考にしてください。
入力は12ビットまで対応していますが、チェックはしていません。
-r 必要最小限のビットを求める処理をします。
-s 計算に先立って、入力をソートし重複行を削除します。
必要最小限のビットを求める時、nビット立った数をnの小さい順、数の小さい順に並べたテーブルを使います。 12ビットまで対応なので、テーブルサイズは4Kになります。
先に計算しておいたほうがよさそうなので、テーブルを作るツールを用意しました。
mask12.c
メッセージ出力やオリジナルの結果出力を省略したので、別プロジェクトとしています。 以前は元のソースを字面で追いかけて書き直していましたが、Githubに登録するにあたって、処理内容を追いかけて書き直しました。
また、windowsコンソールに対応するためにソースはBOM付きUTF-8にしてあります。
VS2015の開発者コマンドプロンプトでのコンパイル、実行を確認しています。
オリジナルを作成したjun6231jpさん。 そのほかコメント欄に改造案など出してくれた方々に感謝します。