ヒッキープログラミングスレ 2 - 1371668281

1：（-＿-）さん：2013/06/20(木) 03:58:01 ID:???: プログラミングの話題のスレ

質問・相談
初心者からプロまで
プログラミングに関することなら何でもＯＫ

ヒッキーのプログラミングするスレ
http://ikura.2ch.net/test/read.cgi/hikky/1362050172/

プログラミングできる奴、一緒にアプリ作ろうぜ！！
http://ikura.2ch.net/test/read.cgi/hikky/1360671157/

ヒキ板情報技術部
http://ikura.2ch.net/test/read.cgi/hikky/1348106094/

前スレ
ヒッキープログラミングスレ
http://jbbs.livedoor.jp/bbs/read.cgi/internet/17286/1361821799/
802：（-＿-）さん：2015/10/14(水) 23:00:59 ID:???: まず
転送用バッファ（処理済みデータ)
保留バッファ(圧縮するかしないか、圧縮するなら固定ハフマンかカスタムハフマンかを考察中・解析中のデータ)
入力バッファ(まだ解析対象になってないデータ)

転送用バッファは処理済みデータの要求があったときにコピーするデータ
未処理データがまだ残っており転送用バッファが空になったとき保留バッファの解析・考察をして圧縮処理を施し転送用バッファにコピーする
保留バッファが一定サイズ未満になったとき入力バッファからデータをコピーしてくる

圧縮は最大258バイトの長さを縮められるから保留バッファはそれ以上のデータは保持しておいたほうがいい
非圧縮ブロックは64KiBまでの長さにできるから、保留バッファを64KiBにするって手もあるのかもしれんけど
非圧縮ブロックは長さ情報を頭に挿入しなきゃならんし
所謂アスキー文字の値127以下の文字ばかりなら固定ハフマンでも8bitで格納だから
バイト境界を意識しなきゃならん非圧縮ブロックを使うなら値128～255が多いデータのときでほどよく分布してる場合か
偏りがあるなら距離長さの対象になるかもしれんし
そうでなくても同じデータが頻出するならカスタムハフマンで頻出値を8bit未満に符号化できるかもしれんし
803：（-＿-）さん：2015/10/14(水) 23:11:29 ID:???: カスタムハフマンを使うときは符号表も圧縮して挿入しなきゃならんから
符号表分のバイト数を加えても超圧縮できるときじゃないとメリットないよなあ
たぶん数十バイトから百数十バイトくらい余分に使うのかな
頻出データが5biｔくらいになったとしても相当な頻度での量がないと圧縮効果は薄そう
804：（-＿-）さん：2015/10/14(水) 23:35:08 ID:???: 2chのスレとかだとあっという間に数百キロバイト超えるのな
１レスごとの書き込み量の多いスレだと100レス行く前に32Kに達するし
１レスごとの書き込み量の少ないスレだと200～300レスくらいで32Kに達する

32KiBで参照して圧縮するわけだけど
2chのスレみたいなテキストベースは32KiBも調べる必要なさそう
2KiBくらいでも十分かも

バイナリデータだと32KiBという短い距離だと早々同一のバイト列は出てこなさそう
ビットマップの単色が頻繁に続くってことならやはり32KiBも参照する必要はないし
TrueColorだと１マス4バイトくらいか？32KiBだと大雑把に8000マスくらいか？
横1024の画像データならたった8ラインにも満たない・・・
もっと遠いとこに似たような色の並びがあったとしても参照できないし
deflateが圧縮業界で雑魚な感じなのか
805：（-＿-）さん：2015/10/14(水) 23:41:29 ID:???: うん？テキストベースを2KiBだとちょっと少ないか
アスキー文字なら１バイト文字だけどunicodeとかマルチバイト文字は
1000文字で2000バイト超えたりするわけだから
2chの1レスは2000文字くらい書けたりするわけだ、大半は全角文字だから2バイト文字で4000バイトは超える
荒らしとかの　ああああああああああああああああああ　みたいな連続文字は簡単に圧縮対象だけど
例えば名無しデフォルトが多くメ欄はsageが多く、日付は同じ日のレスもそれなりあることを考えると
10KiBくらいは参照したほうがよさげか
806：（-＿-）さん：2015/10/14(水) 23:55:49 ID:???: RFCにある圧縮処理の実装の仕方の参考情報を元に
頭悪い俺がロジックを考える（ひとまず自力だけで考える）

まず32KiBの参照
RFCにあるのは3文字(バイト)分のキーで距離マップを作るといいとある

保留バッファ中のX番目のデータの評価を終えて次のバイトに行くときに
X-2、X-1、Xの３バイトをキーとして処理を終えたデータ分も含めた総バイト位置の配列を値としてマップしていく
この場合はX-2番目のデータの総バイト位置を値の配列の最後尾に加える
んで
次のX+1番目のデータの評価のときX+1、X+2、X+3をキーとしてマップから探し出して
一致するものがあれば距離の近い順（最後尾)のほうからデータ列の一致をチェックしていく
繰り返しデータが発生するのはその参照したデータを走査していく際にX+1番目の手前であるX番目に到達してしまったとき
そのときに参照距離の最初に戻って繰り返し一致していくか判定するわけだ
807：（-＿-）さん：2015/10/15(木) 00:02:10 ID:???: 距離マップにひたすらマッピングしてくと、とんでもないデータ量になりかねない(キーは最大2の24乗にもなるし)
つまり32KiB超えた分は適宜削除しなきゃならない
そこでキューを使う、キューにマップするキーと配列に追加する値のセットを挿入していき、
キューのサイズが32KiBを超えたら先頭のキューのものをマップから削除する

これは効率悪そう

問題は、評価対象は保留バッファであり、32KiBの参照は転送用バッファに入れられた処理済データの分も含むわけだ
しかも保留バッファを順に走査していくと32KiBの参照は保留バッファ内にも持つ必要が出てくる

つまり、処理済データ32KiB分を保持するマップとキュー、
そして保留バッファの情報を保持するマップとキューが必要となる

うん、効率悪そう
808：（-＿-）さん：2015/10/15(木) 00:07:04 ID:???: カスタムハフマンによるリテラル値の符号化による圧縮を考える場合は
評価対象である保留バッファの0～255の値のヒストグラムを作り、
頻出順に並び替えてハフマン符号表を生成し、ヒストグラムの個数と符号化後のビット数を掛けて和すると圧縮サイズになるって感じか
それとは別に符号表のサイズも考慮せにゃならんが
809：（-＿-）さん：2015/10/15(木) 00:13:59 ID:???: ブロック区切りは保留バッファごとじゃなく
直近の処理済データでブロックを終わらせなくていいのなら継続と言う感じかな
ブロックのサイズ制限があるのは非圧縮ブロックのみだが
非圧縮ブロックは先頭にブロックサイズを入れなきゃならんから
直近の処理済データが非圧縮ブロックならそこでブロックは終わってなければならない

保留バッファにあるデータを評価した結果
最後の処理済の継続ブロック（すなわち固定ハフマンかカスタムハフマン）と同じブロックでよいのなら
そのまま符号化データを転送用データにぶっこんでいけばいいし
違うブロックのほうがいいのならブロック終端の256の符号をぶっこんでから
新しいブロックを作る必要があると
810：（-＿-）さん：2015/10/15(木) 00:23:39 ID:???: ここで１つ問題がある
ブロックは最後のブロックにはそれを示すフラグを入れる必要があるわけだ
複数のブロックで構成することを事前に想定しているのならいいが
全体を１ブロックだけ（１つの処理方法だけ）で構成するとなると
ブロックの先頭にあるフラグビットに最終ブロックのフラグを立てなければならない

入力データの全てが保留バッファに完全に収まるというのなら、あるいは入力データの全サイズが一定サイズ以下なら
単一ブロックと決め付けて処理するのもアリかもしれんが

そうでない場合は問題だな
入力データの終端まで来て、あ、やっぱ単一ブロックでよかったわってなっても今更ブロックのフラグの変更は無理だし
苦肉策を要するならデータの無い終了フラグのためだけのブロックを作るというのも一つの手か
非圧縮ブロックならLEN=0にして3bit+4byteで35bitか
固定ハフマンブロックなら、3bit+7bitで10bitでこれが一番妥当だな
カスタムハフマンは・・・3bit+色々byteあってこれはダメなパティーン
固定ハフマンの10bitの終了ブロック作りゃいいだけだから、まぁいいのか
811：（-＿-）さん：2015/10/16(金) 18:23:36 ID:???: 脱線してVirtualBoxに入れてたUbuntu14ちゃんをアプデしたらぶっ壊れた件ｗ
aptitude update　でパッケージリスト更新して、かなり久しぶりだからかすごい量のアプデがあったけど
気にせず aptitude upgrade ぽーん！とやったらぶっ壊れたｗ
途中でinitramfsが失敗してるようで一時領域が不足してポポポーン！
cpやmkdirが失敗しまくリングなメッセージ多発してショッキングだったは
同じく久方ぶりにアプデしたdebian6ちゃんは平然とやってのけたのに！（ヤバそうなメッセージはチラホラあったような感じではあったけど！）
どちらも常に上書き保存設定にしてたから前の状態に復元できないという！（せっかく仮想環境使っている意味がないことをしている俺！！）
そもそもこんな低スペックPCでVirtualBoxを動かすってのが無理があるんだ！
812：（-＿-）さん：2015/10/16(金) 18:28:52 ID:???: うーん、どうしようか
大昔にDLったUbuntu14ちゃんのインストールディスクイメージちゃんでUbuntuちゃんを再インストールするか
でもそれだと結局大量のアプデ地獄が
だからといってヘボ回線だから更新されてるかもしれないインストールディスクイメージのDLはしんどいしな
え？失敗を調査して手動で修復？無理無理、なんか6万件近いアプデが入ったみたいだしそんなん無理や！
813：（-＿-）さん：2015/10/16(金) 18:31:32 ID:???: そもそも何でubuntuちゃんをVirtualBoxに入れたのか記憶にすらない・・・
あ、思い出したわ、Mono VisualBasicを試すためだったな
814：（-＿-）さん：2015/10/17(土) 03:08:28 ID:???: 今日も今日とて脱線してCygwinの更新とyukicoderやってたは
ダメぽ
815：（-＿-）さん：2015/10/17(土) 03:09:30 ID:???: 昨日のyukicoderのコンテストの★2の問題が解けなかったわ…
やはり★1の問題を解くのがいいわ
816：（-＿-）さん：2015/10/18(日) 06:23:04 ID:???: 今日もyukicoderに没頭してしまった
とうとう通常問題の★1は全部解き終わってしまった
★2の問題に取り組むか、gzip処理を作る続きをするか（続きも何もガワしか作ってないがな)
817：（-＿-）さん：2015/10/19(月) 04:38:45 ID:???: 方針
ひとまず固定ハフマンを使って圧縮して一時バッファに突っ込む
ある一定サイズの入力データを読み終えた時点で
そこまでのデータを非圧縮ブロックとして扱ったときの８割（？）程度以下に圧縮できていれば一時バッファを確定出力データとして送る
そうで無いときはその部分のヒストグラムを調べ使用されてない値が一定数（５割くらい？）以上あればカスタムハフマンの符号表を作り
カスタムハフマンで符号表含めて８割程度以下になるならカスタムハフマン採用
そうで無い場合は３つのケースで最もデータサイズが小さくなるものを採用
818：（-＿-）さん：2015/10/19(月) 04:46:17 ID:???: うーむ、一時的な圧縮データである一時バッファを作らず
変換パターン（アルファベット値と距離長さの値）を保存しておけば
カスタムハフマンの符号表での圧縮サイズ測りやすいか？
カスタムハフマンを使う場合は２通りの圧縮手法が考えられる
単純にビット数の小さい連続リテラル値としての圧縮と
固定ハフマンと距離長さをメインにする同じ変換パターンでの圧縮と
後者の場合はデータ値(0-255)のヒストグラムじゃなく変換アルファベット値(0-287)のヒストグラムにする必要があるな
前者の場合は0-255のヒストグラムが必要になるな
819：（-＿-）さん：2015/10/19(月) 04:55:54 ID:???: カスタムハフマンはもう１つパターンがあったか
確定データの最後がカスタムハフマンブロックならそのカスタムハフマンの符号表を使えるというパターン

前からのカスタムハフマンの符号表を使うか、今回解析したデータ列から生成できるカスタムハフマン符号表を使うか

前の符号表使う問題点としてはヒストグラムが異なるデータ群のものになるってことか
ハフマン符号表の生成法の復習をまだしてないからよく分からんが
前のデータ群になかったデータ値・アルファベット値が出てきたらちょっとややこしそう
出現する値の種類は変わらなくても分布が変われば圧縮効率が極端に落ちるだろうし
確定済みのデータ群のカスタムハフマン符号表を使うメリットが出てくるケースはすごく限定されそう
820：（-＿-）さん：2015/10/19(月) 04:58:34 ID:???: 前のカスタムハフマンを使うメリットは符号表データを新たに埋め込む必要がないってところくらいか
あくまで前のデータ群とヒストグラムの類似性が高いときだけの限定的用途にしかならんか
821：（-＿-）さん：2015/10/19(月) 04:59:33 ID:???: ひとまずハフマン符号表の生成ロジックの復習をしないと
カスタムハフマンを適用する基準すら設けられない
822：（-＿-）さん：2015/10/19(月) 05:07:52 ID:???: まぁでも一応圧縮ロジックの概要は掴めた気がする

対象データの一定サイズ分を距離長さ圧縮のアルファベット値に変換したパターンを生成
（パターン生成時についでに固定ハフマンでの圧縮サイズ(ビット数)も計算していく）
非圧縮時、および前回確定データがカスタムハフマンならそれ使用時のサイズも算出
この時点で非圧縮の８割以下が生成できるならそれでいいんじゃね？的な判定
ダメぽそうなら
この解析中データ限定のカスタムハフマン符号表を生成を考える
ヒストグラムの分布的に具合が悪そうならカスタムハフマン符号表の生成はなしに現時点での最小サイズになるものを採用
分布の偏りに見込みを感じたらカスタムハフマン符号表を生成して圧縮後サイズを算出
ここまでの中で一番最小のサイズに収まるものを採用
823：（-＿-）さん：2015/10/19(月) 05:12:52 ID:???: 非圧縮ブロックのサイズ算出時に気をつけることは
前回確定データがハフマン符号による圧縮してる場合はブロック終了値を先頭に挿入する必要がある
そして非圧縮ブロックの開始ビットを入れ、バイト境界までのビット飛ばしに続きデータの長さ２バイトと確認用２バイトが加わると
バイト境界まで飛ばすのは多くて７ビットくらいだからブロック開始フラグに１バイト使ったとみなしてもいいかもしれない
前回のハフマンのブロック終了値が何ビットかもちょっと関係するか固定ハフマンだと大したビットサイズじゃないが
カスタムハフマンを使ってる場合は何ビットになるか検討もつかないな長大になるかもしれんし
824：（-＿-）さん：2015/10/19(月) 05:16:04 ID:???: 非圧縮ブロックが最小になるケースは
データ値がほぼ全てが存在していて、出現頻度もほとんど変わりなく、かつ長さ距離での参照可能な類似データがほとんど存在しない
そんなデータ

圧縮済みデータとかが入力データとして来たらそういう分布になってるだろうな
825：（-＿-）さん：2015/10/19(月) 05:19:56 ID:???: 圧縮済みデータをわざわざ圧縮処理かけるなんて無駄すぎるから普通しないだろうけど
圧縮済みデータを何らかのフィルタリング加工したら追加圧縮可能な分布にはなりえるかもしれんな
deflateは32kb単位の参照窓しか持たないから32kbを超えるような形で類似データが発生するようなデータ郡だと
データを並び替えて類似データを32kb以内に連続させるというフィルタリングをすれば更なる圧縮がかけられそうだな
826：（-＿-）さん：2015/10/19(月) 05:42:45 ID:???: うっうー
RFCのDEFLATEの文書にあるのはカスタムハフマンの符号長リストから符号表を復元する方法だった件
ヒストグラムから符号表作るのはハフマンさんの著書を読めとか書いてあるうう
827：（-＿-）さん：2015/10/19(月) 05:43:41 ID:???: いちおーう
Wikipediaのハフマン符号のページにもアルゴリズムは書いてあるけども！
828：（-＿-）さん：2015/10/19(月) 06:09:14 ID:???: 符号表を圧縮する符号表は
アルファベット値が0～18の符号表で
アルファベット値の符号長は最大7bit、
この符号表(0-18)でカスタムハフマンの符号表(0-257/285)の符号長リストを圧縮している
最初に来るのがリテラル値(0-286)の符号長リスト、これを元にリテラル符号表を復元
続くのが距離(の符号長（距離の拡張ビット数に相当するものと思われる）
その後に続くのが長さの符号長（長さの拡張ビット数に相当するものと思われる）

う・・・ん？距離符号と長さ符号の符号長の解釈これで正しいのか？
昔実装したInflate処理でそこをどのようにしたか全く記憶に残ってないな・・・まぁコードを見直せばいいだけだが
拡張ビット数ってことじゃないと距離と長さを表せないわけだし
うーん、確信が持てない

自前実装したInflateで一応カスタムハフマンで符号化されたデータの復号には成功したが
そのカスタムハフマンの符号化で距離・長さが使われてなかったら分からんな

うーん、分からんくなってきた
もしかすると昔実装したInflateのカスタムハフマンの距離と長さの復号は間違ってる可能性があるかもしれん

面倒くせえな、面倒くせえ
829：（-＿-）さん：2015/10/19(月) 06:15:26 ID:???: ハフマン符号化はwikipediaので何となく分かった
出現頻度で頻度０を除いた配列作ってソートして
小さい順から２つ取り出して木にして和した値をさっきの配列に挿入してソート
同様に小さい順から２つ取り出して木にして和した値を配列に挿入してソート

まぁソートはコスト高いから配列全要素1走査O(n)で最小値と２番目を取り出すのは可能だからそれで取り出せばいいかもだけど
830：（-＿-）さん：2015/10/19(月) 06:23:42 ID:???: 拡張ビット数ではないぽげだな
リテラル・長さのアルファベットの符号長リストが続いて
距離符号の符号長リストが続く

固定ハフマンだと距離符号の符号長は全部5bit固定って話なのか
831：（-＿-）さん：2015/10/19(月) 06:25:14 ID:???: おーけーおーけー
昔書いたInflate実装のコードは読みにくさ抜群だったけど
それのおかげでカスタムハフマンのことが分かった
832：（-＿-）さん：2015/10/19(月) 06:27:48 ID:???: 気になるのはRFCのDEFLATEでハフマン符号表を作るのは複雑だからハフマンの著書を読めとあるが
Wikipediaで説明されてるロジックは別に複雑でもなんでもないんだよなあ
Wikipediaのはあまり圧縮効率が良くない生成法なのかな？
833：（-＿-）さん：2015/10/19(月) 06:30:34 ID:???: あー英語版のWikipediaのほうみたらやっぱりそうだった
日本語版のWikipediaは圧縮効率は二の次なロジックがシンプルな生成法のほうだわ
834：（-＿-）さん：2015/10/19(月) 06:43:20 ID:???: うーむ、どうも違うな
英語版wikipediaで紹介されてる一方のほうは日本語版wikipediaと同じだけど
もう一方はソートされてると2つのキューを使ってO(n)で終わる処理が作れるみたいな感じぽい？

まず第1のキューに全葉をつっこんで
第1のキューか第2のキューかあるいは両方から小さい値の節を２つ取り出す、和して第2のキューに突っ込む、これを繰り返す
という感じか
835：（-＿-）さん：2015/10/19(月) 06:46:39 ID:???: あー！これらはベーシックテクニックの項目に紹介してあるシンプルな方法ってだけのようだ！
英語版を下にスクロールすると他の手法について簡単に紹介が書いてあったわ
紹介だけでロジック書いてるわけでは無さそうだから
場合によっては特許アルゴリズムの可能性もあるってことだな
836：（-＿-）さん：2015/10/19(月) 06:48:45 ID:???: いや、待てよ、アルゴリズム書いてあるぽいか・・・？
ベーシックテクニックの項と違って分かりやすく整形された文章になってないだけで詳しく書いてある感じか・・・？
ちょっと読むのはしんどそうだな
なんで日本語wikipediaではそれ書いてないんだ！
837：（-＿-）さん：2015/10/19(月) 06:50:38 ID:???: 読むのしんどそうだが何よりも特許の有無も判別せにゃならんのか
アルゴリズム開発者の名前も書いてあるのあるけど特許調べるの面倒そうだなあ
838：（-＿-）さん：2015/10/19(月) 18:53:24 ID:???: さて、wikipediaに書いてあるいくつかのアルゴリズムについてさっそく読むぞ！

https://en.wikipedia.org/wiki/Huffman_coding
839：（-＿-）さん：2015/10/19(月) 19:05:27 ID:???: n-ary Huffman codingはハフマンさん自身が提唱したアルゴリズムらしいが
840：（-＿-）さん：2015/10/19(月) 19:08:30 ID:???: 情報圧縮と特許　
http://www.entis.jp/eridev/doc/cnp_ace/

特許とか面倒くせえなあ・・・
841：（-＿-）さん：2015/10/19(月) 19:14:53 ID:???: 日本語版wikipediaには特許の問題はないとか書いてあるが
>>840を読む限りではハフマン符号のフォーマットに関して特許が無いとあるだけで
ハフマン符号を生成する方法そのものは特許に関わる可能性があるとかどうとか
英語版wikipediaには特許については一切触れてないし
面倒くせえ
842：（-＿-）さん：2015/10/19(月) 19:26:25 ID:???: 特許庁のＨＰで「ハフマン Huffman」で検索したら1000件以上ヒットした・・・うげえ
843：（-＿-）さん：2015/10/19(月) 19:28:44 ID:???: もしかすると俺が実装したDeflateの圧縮解除処理も何らかの特許に触れる可能性が微レ存？
競技プログラミングなんか全然な頭の悪い俺の非効率極まりないだろうコードでも引っかかったりするのだろうか
844：（-＿-）さん：2015/10/19(月) 19:33:55 ID:???: 特許庁のＨＰクソうぜええ
別窓で個々の特許見れねえ
845：（-＿-）さん：2015/10/19(月) 19:36:17 ID:???: 特許のフォーマット糞すぎい！
全部言葉で説明するとか分かりにくすぎい！
擬似コードで示せるように法改正しろよ糞が
846：（-＿-）さん：2015/10/19(月) 23:17:33 ID:???: ダミだ・・・日本語サイトからじゃwikipediaにあるハフマン符号化のロジックが特許フリーなのかどうかの根拠が出てこない
特許庁の膨大な特許データ漁る以外方法はなさげ
847：（-＿-）さん：2015/10/19(月) 23:19:44 ID:???: ハフマン符号化は特許大丈夫とか言ってるサイトはどこも根拠なく言ってやがる、どいつもこいつも又聞きレベルで大丈夫と言ってるだけ
848：（-＿-）さん：2015/10/19(月) 23:21:57 ID:???: まぁ正確にハフマン符号というフォーマットには特許が無いとだけ言明してるサイトもあるにはあるが
符号化テーブルの生成法については実装がうんぬんとぼやかし気味
849：（-＿-）さん：2015/10/19(月) 23:24:13 ID:???: 大事なのは実装だろうが！特許に引っかからない実装方法こそ、特許フリーな実装方法にこそ意味があるってのに
850：（-＿-）さん：2015/10/19(月) 23:25:45 ID:???: いや、まぁ俺も無駄に拘ってるのは意味も無いといえば意味ないがな
851：（-＿-）さん：2015/10/19(月) 23:30:59 ID:???: 特許になっているってことは実装方法が公開されてるわけだから
権利者に無断でその方法を使って商売しちゃならんぞってことなんだろ、特許ってたぶん
特許になって公開されてるアルゴリズムやらロジックはそれを紹介するだけでは罪にはならない感じなのか知らんが
wikipediaや個人サイトでその手法を紹介するのは可能なわけだ、その気になれば誰だって特許庁のＨＰから見れるわけだしな

問題は紹介されてるからってそれを実装してみたら特許に抵触したってことがありうるって話だ
852：（-＿-）さん：2015/10/19(月) 23:31:39 ID:???: そんなこと個人レベルで気にするやつなんて普通いないし、俺が頭おかしいだけなのは分かる
853：（-＿-）さん：2015/10/19(月) 23:36:49 ID:???: ただ単にちょっと気なっているだけなのではあるが
そこんとこに素人にも分かりやすく説明してるサイトを見つけられない俺が無能すぎるわけだ
854：（-＿-）さん：2015/10/20(火) 00:01:21 ID:???: 面倒になってきた
特許について調べんのやめやめ
855：（-＿-）さん：2015/10/20(火) 00:09:57 ID:???: https://en.wikipedia.org/wiki/Huffman_coding#n-ary_Huffman_coding

n-aryハフマンアルゴリズムは{0,1,..,n-1}のアルファベットを
メッセージをエンコードするため、そしてn-aryツリーを組み立てるために使う。
このアプローチはハフマン氏の論文の中で彼によって考えられた。
856：（-＿-）さん：2015/10/20(火) 00:28:32 ID:???: 同じアルゴリズムが適用される
as for n=2のときのバイナリコード
そのn以上の可能性のシンボルがまとめてとられる場合を除いて
ちょうど2以上の可能性のかわりに

俺の英語力！？？
857：（-＿-）さん：2015/10/20(火) 00:29:40 ID:???: たぶんベーシックテクニックで書かれてるロジックに対して言及されてるんだろうけど
858：（-＿-）さん：2015/10/20(火) 00:32:23 ID:???: たぶん、probableは「可能性」じゃなく「確率」「確率分布」あたりを意味してるのかな
859：（-＿-）さん：2015/10/20(火) 00:38:27 ID:???: おそらく
ベーシックテクニックの２分木のような感じでＮ分木が処理される
的なことを言っているセンテンス
２分木が小さいほうから２個取り除いて処理するのを
Ｎ分木では小さいほうからＮ個取り除いて処理する
ということをたぶん言っている
860：（-＿-）さん：2015/10/20(火) 00:46:08 ID:???: 注意
2より大きいnから
全てでないソース単語のセット
ハフマン符号からn-aryツリーを適切に形成できる
861：（-＿-）さん：2015/10/20(火) 00:54:18 ID:???: nが2より大きい場合、ソース単語の一部からなる集合は
ハフマン符号のためのn-aryツリーを適切に形成できる
ということです
862：（-＿-）さん：2015/10/20(火) 00:54:55 ID:???: しっくりこない
863：（-＿-）さん：2015/10/20(火) 00:56:40 ID:???: この場合、追加の0確率の場所ホルダーが必ず追加される
864：（-＿-）さん：2015/10/20(火) 00:57:36 ID:???: 場所ホルダーじゃなくプレースホルダー?
865：（-＿-）さん：2015/10/20(火) 01:00:08 ID:???: 機械翻訳だと
追加しなければなりません
だな、受動形で本来の主語が抜けてるから主語はyouってことでyou must addが must be added になったって感じか
866：（-＿-）さん：2015/10/20(火) 01:02:43 ID:???: さらなるプレースホルダを追加しなければならない
どんなプレースホルダかというと、0確率、すなわちヒストグラム取って個数0になった文字(値)のためのってことあたりか
867：（-＿-）さん：2015/10/20(火) 01:10:02 ID:???: その理由は
ツリーは1短縮のために１つのnを形成しなければならない
バイナリコードの場合はこれは１短縮するための１つの２である
そして
どんなサイズのセットでもそんな短縮を形成できる
868：（-＿-）さん：2015/10/20(火) 01:14:27 ID:???: もし、ソース単語の数がn-1で割った余り1と一致する場合、
ソース単語のセットは適切なハフマンツリーを形成するだろう
869：（-＿-）さん：2015/10/20(火) 01:20:02 ID:???: 英語圏の人が読めば分かる英文であっても
英語圏じゃない人間が読むと解釈に困る英文は存在する
どんな外国語も教科書どおりな真面目でお堅い文法どおりで使われているわけでない
俺の書く日本語だって、日本語を少し齧ったくらいの外国人では読むことは辛いだろう

日本の受験英語の英文は何と文法どおりで読み易い英文なんだ！クソ教育万歳だぜ
870：（-＿-）さん：2015/10/20(火) 01:20:36 ID:???: 生きた英語を教えろや
英語のサイトが全然読めんだろーが！！
871：（-＿-）さん：2015/10/20(火) 01:22:29 ID:???: n-aryの説明の部分を書いた奴が感覚的に書いてるせいで非英語圏の人間が分からないんじゃあああああああ
872：（-＿-）さん：2015/10/20(火) 01:24:29 ID:???: まぁもともと言語別にwikipediaのページは存在するし、他言語を使う人間が読むことを想定してないってのはあるだろうな
だいたい一般有志が編集しまくるwikipedia、よみやすい文章を書くエキスパートでもスペシャリストでもないしな
俺が期待しすぎたんや
873：（-＿-）さん：2015/10/20(火) 01:26:30 ID:???: 俺に競技プログラマみたいなセンスがあれば、かけらレベルでもあれば
この微妙な説明文からでもアルゴリズムやロジックを予想できたかもしれんが
センス皆無だからな
無理ゲー
874：（-＿-）さん：2015/10/20(火) 01:28:44 ID:???: もう面倒だしベーシックテクニックにあるキューを２つ使う方法で実装するわ
俺の勘違いかもしれんが、雰囲気からしてn-aryってのはdeflateには使えなさそうな気がするし
875：（-＿-）さん：2015/10/20(火) 01:37:26 ID:???: ということで
ハフマン符号の形成からして
>>817で考えてた未使用５割以上とかいう考え方はあまり効果的な発想じゃなさそう
出現頻度の偏りが極端であればカスタムハフマンの効果があるって感じかな
0-255のほぼ全てが分布していても特定の値だけ極端に頻出してたらそれを1bitあたりに符号化すれば超縮む、みたいな？
876：（-＿-）さん：2015/10/20(火) 01:39:38 ID:???: 逆に0-255のほとんどに分布してて偏りがあまり無ければカスタムハフマンはほぼ意味なし
偏り無くても未使用が５割以上あれば8bit表現から7bit表現に圧縮できるかもしれないし検討する価値は出てくるかもだが
877：（-＿-）さん：2015/10/20(火) 05:29:26 ID:???: ひとまず性能度外視でdeflate実装してみっか
878：（-＿-）さん：2015/10/20(火) 05:55:20 ID:???: ひとまずもう寝る時間で時間足りないから
今夜やるわ
879：（-＿-）さん：2015/10/25(日) 05:52:17 ID:???: うう、脱線しまくりんぐで全然進んでないよぉ
880：（-＿-）さん：2015/10/25(日) 05:53:05 ID:???: 昨日はAtCoderのABCに参加しちゃったし
今日はCodeforcesに参加しようかとか脳裏によぎっちゃったり
881：（-＿-）さん：2015/10/25(日) 05:53:41 ID:???: 最近は録画するアニメも増えたからそれで時間を費やすようになったし
もうダメダメだよぉ～
882：（-＿-）さん：2015/11/03(火) 00:54:28 ID:???: 今日まで１ミリも進んでない！？
883：（-＿-）さん：2015/11/03(火) 00:55:06 ID:???: 2週間近くもサボりサボってるは！
884：（-＿-）さん：2015/11/04(水) 17:36:04 ID:???: brainf*ck
メモリ上のどこに何のための値をセットするか決めることが大事
つまり通常はコンパイラさんがやってくれる変数をメモリのどこに配置するかを自分で配置するイメージ

http://ideone.com/cDQlG9
885：（-＿-）さん：2015/11/04(水) 17:42:11 ID:???: 3*4の計算して表示
1つ目のメモリに3*4の答えを入れる
3を4回足す、を行えばよい
今回は2つ目のメモリにカウンタを入れる

>++++[<+++>-]

これで１つ目のメモリに12が入ったはず
886：（-＿-）さん：2015/11/04(水) 17:43:51 ID:???: brainf*ckの文字出力は文字コードなので
12を表示するのは大変そう
12という値から'1'の文字コードと'2'の文字コードを順に生成して出力せにゃならん
887：（-＿-）さん：2015/11/04(水) 17:47:38 ID:???: 12から'1'を生成するには
12を10で割って商を求める必要がある

う・・・む・・・
888：（-＿-）さん：2015/11/04(水) 17:51:54 ID:???: brainf*ckによる値のコピー
1つ目のメモリの値を2つ目のメモリにコピーする
コピーの際に一時的に3つ目のメモリを使う

[>+>+<<-]>>[<<+>>-]

最初の [>+>+<<-] は1つ目のメモリの値の数だけ2つ目と3つ目の値を増加させる、1つ目のメモリはカウンタの役割になる
次の >>[<<+>>-] は3つ目のメモリの値をカウンタにして1つ目のメモリの値を復元してる
889：（-＿-）さん：2015/11/04(水) 18:03:28 ID:???: brainf*ck
２つのメモリの値を足し算

1つ目のメモリの値と2つ目のメモリの値の和を3つ目のメモリに入れる
4つ目のメモリを一時的に使う（1つ目と2つ目のメモリ復元のため)

[>>+>+<<<-]>>>[<<<+>>>-] これは一つ目のメモリを3つ目4つ目にコピーし1つ目を復元するまで

<<[>+>+<<-]>>[<<+>>-] これは2つ目のメモリに移動して、2つ目のメモリを3つ目に足しこむのと4つ目にコピーして、2つ目のメモリを復元するまで

合わせるとこうなる
[>>+>+<<<-]>>>[<<<+>>>-]<<[>+>+<<-]>>[<<+>>-]
890：（-＿-）さん：2015/11/04(水) 18:05:12 ID:???: brainf*ck
２つのメモリの値を足し算

1つ目のメモリの値と2つ目のメモリの値の和を1つ目のメモリに入れる
足し合わせる２つの値を保持する必要ない場合はもっと簡潔に書ける

>[<+>-]

これだけ、2つ目のメモリをカウンタとし1つ目のメモリを増やせばいいだけ
891：（-＿-）さん：2015/11/04(水) 18:07:44 ID:???: brainf*ckは常にポインタの位置＝メモリの位置＝どの変数を見てるかを意識すればよい
892：（-＿-）さん：2015/11/04(水) 18:24:38 ID:???: 引き算は・・・どうなんだろうな
仕様をちゃんと調べてないから0から引くとアンダーフローエラーでも起こすのか？それとも255になるだけか？
C言語の整数型だと後者のように循環するから、たぶんbrainf*ckもそんな感じかなあ

引き算の法則をちゃんと把握しないと条件分岐ができないからなあ

条件分岐はゼロか否かだけだから難しいなあ
893：（-＿-）さん：2015/11/04(水) 18:27:16 ID:???: brainf*ck
メモリの値をリセット

1つ目のメモリの値を０にする

[-]

簡単
894：（-＿-）さん：2015/11/04(水) 18:27:56 ID:???: まぁ値が循環するのなら [+] でも０にはなるか
895：（-＿-）さん：2015/11/04(水) 19:44:52 ID:???: brainf*ck
値が０かどうか

1つ目の値が０かどうかを調べる
例のごとく2つ目に値をコピー
3つ目にフラグとして1回インクリメント
2つ目の値がゼロでないなら3つ目のデクリメント
3つ目の値がリセットされてないなら1つ目の値は０ではない
面倒な

[>+>+<<-]>>[<<+>>-] 　　2つ目にコピー (この時点で3つ目は０、ポインタは3つ目）
+　　　　　　　　　　　　　　　3つ目をインクリメントでフラグ
<[>-<[-]]　　　　　　　　　　　2つ目が０でないなら3つ目をデクリメントで2つ目リセットしてループ抜ける（ポインタは2つ目に）
>[- ～ ]　　　　　　　　　　　　3つ目が０でない＝1つ目が０　なので　～　の処理をする

なんという面倒な処理
896：（-＿-）さん：2015/11/04(水) 19:46:03 ID:???: ～の中は値を変化させたいメモリに移動して値変化させてまた3つ目にポインタを戻すしょりになる
897：（-＿-）さん：2015/11/04(水) 19:49:25 ID:???: brainf*ck
値が非０かどうか

まぁこれは簡単、フラグいらない
1つ目の値が非０か調べる
1つ目の値を2つ目にコピーして2つ目の値を判定すればいいだけ

[>+>+<<-]>>[<<+>>-]　　1つ目の値を2つ目にコピー
<[[-]　～　]　　　　　　　　2つ目に移動して　2つ目の値がある＝1つ目は非０　で　～　の処理を行う

当然ながら　～　は他のメモリにポインタ移動して値いじって2つ目にポインタを戻す処理
898：（-＿-）さん：2015/11/04(水) 19:55:33 ID:???: フラグを駆使すれば大小比較も可能か？
899：（-＿-）さん：2015/11/04(水) 20:04:24 ID:???: brainf*ck
2つの値を比較

うーん、複雑すぎてちょっと思考無理
900：（-＿-）さん：2015/11/24(火) 05:06:03 ID:???: うーん、しばらく放置してたせいでDeflateのことまた忘れかかってる・・・うおおおおおおおおおおおお
901：（-＿-）さん：2015/11/24(火) 05:06:43 ID:???: しばらくっていうか１ヶ月以上放置じゃねえかｗｗｗｗｗｗ