辞書式圧縮補集合かるた

2020年 1月 8日 開催 のソノリテ数学デーにて発生した
「圧縮バイナリ補集合かるた」(正式名称は不明)というゲームとについての補足説明的ななにかである.

補集合かるたというのは「集合トランプ」というカードゲームを用いて,読み札の補集合を取り合うかるた遊びである.

補集合かるた - 集合トランプ

「圧縮バイナリ補集合かるた」のルール

・読み手
読み札に記載された数字をバイナリ変換し,0あるいは1が連続している個数の数列として読み上げる.

・取り手
読み上げられた数字列を,脳内でデコードして得られた集合の補集合を取る.

・例
{1,2,3,4,5} は バイナリ変換すると 11011100101 となる
11011100101 を 圧縮すると 2132111 となる

この圧縮方法はランレングス符号化というデータ圧縮アルゴリズムです.

連長圧縮 - Wikipedia

本日のやらかし

またエクストリームスポーツが生まれた...と思いながら見ていると,zip圧縮みを感じて「zip圧縮バイナリ補集合かるた」と口走ってしまった.
しかし,この圧縮方法は上記の通りzip圧縮ではないので,この呼名は訂正します.

zip圧縮の仕組み

せっかくだから,zip圧縮の仕組みも調べていくと解説記事が見つかった・

ZIP,LHAの圧縮の仕組み - Qiita

「ハフマン法と辞書式という2つのアルゴリズムで構成されている」

アルゴリズムがわかればzip圧縮を適応することも可能であるということになる訳だ

辞書式圧縮していくぅ

集合, バイナリ列, 辞書式圧縮後の数値列 として記載します
辞書式圧縮は,バイナリ列を文字列として扱います
辞書式圧縮の表記法は[一致位置, 一致長]として記載します.また,一致長の最小値は2とします.

・例
{1,2,3}, 11011, 110[3,2]
と書きます.ここでは[3,2] は3文字前から2文字(11)を表します.

{Φ}, , 
{1}, 1, 1
{2}, 10, 10
{3}, 11, 11
{4}, 100, 100
{5}, 101, 101
{1,2}, 110, 110
{1,3}, 111, 111
{1,4}, 1100, 1100
{1,5}, 1101, 1101
{2,3}, 1011, 1011
{2,4}, 10100, 10[2,2]0
{2,5}, 10101, 10[2,2]1
{3,4}, 11100, 11100
{3,5}, 11101, 11101
{4,5}, 100101, 100[3,2]1
{1,2,3}, 11011, 110[3,2]
{1,2,4}, 110100, 110[2,2]0
{1,2,5}, 110101, 110[2,2]1
{1,3,4}, 111100, 1[1,3]00
{1,3,5}, 111101, 1[1,3]01
{1,4,5}, 1100101, 1100[3,2]1
{2,3,4}, 1011100, 101[1,2]0
{2,3,5},  1011101, 101[1,2]1
{2,4,5}, 10100101, 10[2,2]0[4,2]1
{3,4,5}, 11100101, 1[1,2]001[2,2]
{1,2,3,4}, 11011100, 1101[4,3]0
{1,2,3,5}, 11011101, 1101[4,4]
{1,2,4,5}, 110100101, 110100[5,3]
{1,3,4,5}, 111100101, 1[1,3]001[2,2]
{2,3,4,5}, 1011100101, 101[1,2]00[6,3]
{1,2,3,4,5}, 11011100101, 1101[4,3]01[2,2]

このぐらいの文字列なら,ラングレンズ符号化で十分だなという結論
間違いあったらおしえてください

辞書式圧縮だと前提条件かっちりしないと読み札が一意に定まらないのも問題である