ヒッキープログラミングスレ 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/
772：（-＿-）さん：2015/06/23(火) 05:15:31 ID:???: 発展

寿命と交配を設ける

残り寿命が閾値を超えたら交配行動を求め行動する
最寄の個体に接近し強制交配を行う、交配した両個体はそこで死亡（ただし餌とはならず消滅する）
交配により子個体が2個体発生する。親の両個体から経験を半分ずつ受け継ぐ。経験はランダムに選出される。
受け継ぐ経験はランダムに選出されるため子個体はそれぞれ異なる経験を持つ個体となる
773：（-＿-）さん：2015/06/23(火) 05:41:06 ID:???: メモ

「HTTP/2」がついに登場！開発者が知っておきたい通信の仕組み・新機能・導入方法
http://codezine.jp/article/detail/8663
774：（-＿-）さん：2015/06/23(火) 05:47:20 ID:???: SPDYにしろHTTP/2にしろ
そんな糞重いサイトなんか消えてなくなれってしか思わんわ
無駄に動的コンテンツとか動的読み込みとか要らんちゅうの
軽量ページの遷移だけでなんとかしてほしいわ
775：（-＿-）さん：2015/08/27(木) 04:29:03 ID:???: Java

Pattern.quote(String)

https://paiza.io/projects/1wPSZNGBSwZ8c1w2QfQnLw
776：（-＿-）さん：2015/09/01(火) 04:43:28 ID:???: メモ

注目高まる人工知能--押さえておきたい用語21選
http://japan.zdnet.com/article/35068871/
777：（-＿-）さん：2015/09/22(火) 06:07:41 ID:???: https://paiza.jp/poh/joshibato/matsue-ruby

コードゴルフ難しい
778：（-＿-）さん：2015/10/12(月) 04:31:59 ID:???: 覚悟決めたgzipのdeflate圧縮アルゴリズム実装をするぞ
779：（-＿-）さん：2015/10/12(月) 05:22:16 ID:???: うう、gzipのdeflat圧縮の解除の処理を実装したの2年前だし
そのコードを眺めてたが、昔の俺は出来る奴だったんだな・・・
コード何を書いてるのかよくわからんし・・・deflateの知識を完全にド忘れしてて理解不能に近いわ・・・
780：（-＿-）さん：2015/10/12(月) 05:38:20 ID:???: やべえわ、deflate圧縮の再勉強が必要なレベルだわ・・・それはダルすぎ・・・覚悟消滅
781：（-＿-）さん：2015/10/12(月) 05:52:52 ID:???: DEFLATE
https://tools.ietf.org/html/rfc1951

ZLIB
https://tools.ietf.org/html/rfc1950

GZIP
https://tools.ietf.org/html/rfc1952
782：（-＿-）さん：2015/10/12(月) 05:55:42 ID:???: 翻訳版

DEFLATE
http://www.futomi.com/lecture/japanese/rfc1951.html

ZLIB
http://www.futomi.com/lecture/japanese/rfc1950.html

GZIP
http://www.futomi.com/lecture/japanese/rfc1952.html
783：（-＿-）さん：2015/10/12(月) 05:56:54 ID:???: 色々な翻訳載せてるこの人は神だわ

英語技術文書日本語訳
http://www.futomi.com/lecture/japanese/index.html
784：（-＿-）さん：2015/10/12(月) 06:11:29 ID:???: うん、前回もこの日本語訳で学習したような気がする
原文のほうはちょろっと眺めてみたが見た覚えが全くない
2年前の俺は英語文章を読む気概は無かったようだ
785：（-＿-）さん：2015/10/12(月) 06:21:53 ID:???: カスタムハフマンで圧縮はしんどそう
ハフマン符号表を独自に生成（あるいは事前用意）でやるんだろうけど
ある程度のサイズ（ブロックというやつか）読み込んだデータのヒストグラム取って大きな偏りがある場合は
カスタムハフマンで超圧縮できたりしたらすごいんだろうけど
事前用意ならある程度データの偏りがあることが分かってるデータ形式を取り扱うときとかかな
どのみち面倒や
786：（-＿-）さん：2015/10/12(月) 06:25:39 ID:???: ただ固定ハフマンだとほとんど圧縮できなさそう
同じ連続データが頻出するようなデータ形式じゃないと固定ハフマンより非圧縮ブロック使うほうがいいし
本気で圧縮を考えるならカスタムハフマン使わざるをえないのか・・・
787：（-＿-）さん：2015/10/12(月) 06:28:14 ID:???: ハフマン符号の生成法自体は書いてあるけど
カスタムハフマンだと符号表の圧縮もしなきゃならんし、何よりブロックフォーマットが面倒
788：（-＿-）さん：2015/10/12(月) 06:31:24 ID:???: 前回は伸張処理だったから固定ハフマンの内容について深く考えなかったけど
やたらめったら同じ連続データが頻出しない限り固定ハフマンを使う価値ねえわ
普通のテキスト文書を圧縮なら単純に頻出文字のビット数抑える目的のカスタムハフマン作るほうが断然いいな
789：（-＿-）さん：2015/10/12(月) 06:39:36 ID:???: 固定ハフマンは3バイト(24bit)以上一致すると半分以下のに減らせる感じではあるが
html文書の圧縮とかなら2文字以上タグやパラメータ名が頻出したとしても
タグやパラメータ名なんて文書全体の大した割合じゃないし、固定ハフマンだとちょろっとしか圧縮できないな
俺がいまこのスレで連投してるレスだって連続データ多くないだろうし
ただヒストグラムで頻出検査しても微妙そうではあるが
790：（-＿-）さん：2015/10/12(月) 06:52:14 ID:???: だいたい半分に圧縮か
http://ideone.com/4kiJcR
791：（-＿-）さん：2015/10/12(月) 06:59:50 ID:???: Javaでもだいたい半分か・・・
http://ideone.com/PXzrny

アッカーン
792：（-＿-）さん：2015/10/12(月) 07:02:17 ID:???: 半分というのは素晴らしい成績なのか微妙なのか判断つかんな・・・
793：（-＿-）さん：2015/10/12(月) 07:10:10 ID:???: PHPは他の圧縮形式もサポートしてるから
後で比較してみるかな
794：（-＿-）さん：2015/10/13(火) 07:32:04 ID:???: ふむ
https://paiza.io/projects/-D3AYAjkYK36g5yiYpEG_g
795：（-＿-）さん：2015/10/14(水) 06:24:15 ID:???: Deflateは固定ハフマンを使うのなら

最大で258バイトを13ビット（2バイト弱、距離1バイトの1バイトを258バイト分繰り返し）～26ビット(4バイト弱、距離32Kバイトから258バイト分のコピー)に圧縮できる

3バイト(24ビット)を参照で圧縮する場合は
最小12ビット(2バイト弱、距離1の1バイトを3バイト分繰り返し)～24ビット以上は圧縮の意味がないので23ビットまでで
23ビットは距離約8Kバイトまでの参照
796：（-＿-）さん：2015/10/14(水) 06:45:25 ID:???: ZLIBで使われるAdler32

下位バイト、s1 はバイトデータの総和に1を足したもの
上位バイト、s2 はバイトデータの先頭からの部分和に1を足した物の総和

RFCで紹介されてるコードはループ毎に素数65521で割って効率が悪いので（どんなCPUでも剰余算は効率が悪い）
ある程度足し合わせた状態を素数65521 で割って計算していくほうが効率がよい
ある程度足し合わせた状態がs1とs2のオーバーフローしないギリギリまで求めたい
既にあるadler32の値をupdateで更新するときに
s1とs2にが最も早くギリギリの値になるのはs1とs2の初期値が最大でバイトデータ全部が0xFF(255)のとき
s1とs2は最終的に素数65521 の余りとして算出されるため最大値は双方ともに65520
s1の最大値は簡単に 65520 + n * 255
s2は初項65520の交差255の等差数列の和の総和として表現できる

等差数列の和は
初項 a[0] 交差 d 、a[i+1] = a[i] + d
a[0]からa[n]までの和S[n] = (n+1)*a[0] + d*(n+1)*n/2

その総和なのでs2 = S[0] + S[1] + ... + S[n]
= (1+2+..+(n+1))*a[0] + d*(2*1 + 3*2 + 4*3 + ... + (n+1)*n)/2
=(n+1)*(n+2)*a[0]/2 + d*(2*1 + 3*2 + 4*3 + ... + (n+1)*n)/2

なんかs2はすさまじい桁になりそう
797：（-＿-）さん：2015/10/14(水) 06:51:13 ID:???: adler32の下位s1上位s2ともに2バイト
符号有int型(4バイト)で計算するとなると31ビットまで使える
32ビットが4Gだから31ビットはその半分の2G、20億？
6万ちょっとから20億までは随分と離れてる気がするけど
s2はすぐに到達してしまうようだ、(いくつかのAdler32の実装を見るとそんな感じ)
ライセンス回避のためかみんなちょろっとずつ実装の仕方や数値を変えているようではあった
Adler32の効率いいコードを実装しようとすると面倒そうだな
798：（-＿-）さん：2015/10/14(水) 22:43:49 ID:???: yukicoderなんかで無駄時間使ってしまった
799：（-＿-）さん：2015/10/14(水) 22:44:43 ID:???: yukicoderで★１の問題を解くのが適度に時間潰しに向いててついついハマってしまう
800：（-＿-）さん：2015/10/14(水) 22:45:17 ID:???: ★２以上だと難しくて解けないけど
★１くらいだと俺の脳みそだと適度に悩んで答えが出せるから楽しい
801：（-＿-）さん：2015/10/14(水) 22:46:29 ID:???: さっさとdeflateの圧縮アルゴリズムを実現するロジックを考えねば
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の説明の部分を書いた奴が感覚的に書いてるせいで非英語圏の人間が分からないんじゃあああああああ