【PHP】同じ文字列が多数含まれるレスポンスの辞書的な圧縮方法

　Web 上でなにかをやり取りする時には通信が発生し、時折通信量がネックになります。そういった時に使える圧縮方式の一つを紹介します。

　本題に入る前に Apche や nginx の様な web サーバーが対応している gzip 形式の圧縮レスポンスを知っておくべきです。これは単に web サーバーの設定のみでできるレスポンスの圧縮です。レスポンスを送る前に web サーバーが gzip にしてレスポンスを送ってくれるため通信量が少なく済みます。デメリットとして Content-Length がヘッダーから消える（もしかしたら対策があるのやもしれませんが）という点がありますが、それが問題になるのはダウンロードの様な % 表示が欲しい時にぐらいで、その時はあらかじめ静的コンテンツを gzip 圧縮しておくという方法があります。この方法を用いると独自の圧縮アルゴリズムやデコードを作るのに特に時間を割くことなくレスポンスを圧縮できます。レスポンスサイズ問題はこの方法で大体解決します。後述の方法の出番はやんごとなき事情でレスポンス形式に関する設定を触れずとも圧縮する必要がある時か更なる圧縮を望む時ぐらいです。

　圧縮のために行うことはざっくばらんな代わりに計算量が少なく済むハフマン符号化です。これを完成させると辞書的なレスポンスになります。ハフマン符号化は簡単に言うと多く現れるデータ量の大きい対象に短い符号を割り当てて、短い符号で構成される圧縮データをつくり、短い符号を対応する大きいデータに置き換えて復元する方法です。
ハフマン符号 – Wikipedia
　これの考えを文字の代わりに 1 項目にして、頻度も計算しない雑な形で用います。
　具体例は次です。

// 圧縮前
//単に"株式会社シーポイントラボ"が 10000 個並んだレスポンス
['株式会社シーポイントラボ','株式会社シーポイントラボ','株式会社シーポイントラボ',...]

// 圧縮後
// "株式会社シーポイントラボ" に 0 を割り当てて 0 を 10000 個並べたレスポンス
[
  ["株式会社シーポイントラボ"],
  [0,0,0,...]
]

　元々あったデータ末端からそれぞれの値を単純な連番 int で置き換える感じです、例の状況では0のデータ量 / "株式会社シーポイントラボ"のデータ量の圧縮率になります。例ほど極端な状況はそうそうありませんが、1ページ中の件数が多く、情報がぎっしり詰まった検索 API などでは同様に役に立つ時があります。データ自体の重複が期待できず時でもキー名の重複による圧縮効果が期待できます。
　変換を行う PHP コードの実装例が次です。

<?php
/**
 * 雑ハフマン符号化による圧縮を行う
 */
class DictCompressor {
    /** @var int 辞書のインデックスを管理するための値 */
    private int $latestIndex = 0;
    /** @var string[] 辞書。string の一次元配列  */
    private array $dict = [];
    /** @var array 元々のデータを辞書インデックスに置き換えたもの */
    private array $body;

    /**
     * @return array 圧縮結果
     */
    public function getCompressed(): array
    {
        return [
            $this->dict,
            $this->body,
        ];
    }

    /**
     * 圧縮を実行
     * @param  array  $array
     * @return array
     */
    public function run(array $array): array
    {
        $results = [];
        foreach ($array as $key => $value) {
            if (is_array($value)) {
                // 配列がネストしているならば再帰
                $childArr = $this->run($value);
                $keyIndex = $this->registerOrReadDict($key);
                $results[$keyIndex] = $childArr;
            } else {
                // $key と $value ついて辞書に登録 or 既存読み込み
                $valueIndex = $this->registerOrReadDict($value);
                $keyIndex = $this->registerOrReadDict($key);
                $results[$keyIndex] = $valueIndex;
            }
        }
        // 圧縮結果を代入。一番外側で実行されている run でのみこの代入が効く
        $this->body = $results;

        // 再帰用に現在の結果を返す
        return $results;
    }

    /**
     * 辞書に新規登録 or 読み取り
     * @param $v
     * @return false|int|string
     */
    private function registerOrReadDict($v)
    {
        if(in_array($v, $this->dict, true)) {
            // 既に辞書に登録されているならば、その登録済みのキーを取得
            $valueIndex = array_search($v, $this->dict, true);
        } else {
            // 未だ辞書に登録されていないのであれば、最新のキーを割り当てて辞書に登録
            $valueIndex                       = $this->latestIndex;
            $this->dict[$this->latestIndex++] = $v;
        }
        return $valueIndex;
    }
}


$raw = [
    [
        'memberId' => 1,
        'name'  => '浜松太郎',
        'group' => [
            '株式会社シーポイントラボ',
            '浜松商店',
            '支店'
        ],
    ],
    [
        'memberId' => 2,
        'name'  => '浜松次郎',
        'group' => [
            '株式会社シーポイントラボ',
            '浜松商店',
        ],
        'someRelMemberId' => 1
    ],
    [
        'memberId' => 3,
        'name'  => '浜松三郎',
        'group' => [],
        'someRelMemberId' => 1
    ],
];
$compressor = new DictCompressor();
$compressor->run($raw);
echo json_encode($compressor->getCompressed());
/*
 * レスポンス結果。三件だけでもぎりぎり圧縮効果があります。
 * もちろん本体が長いほど、キー名が長いほど、よく効きます。
[
  [
    1,
    "memberId",
    "浜松太郎",
    "name",
    "株式会社シーポイントラボ",
    0,
    "浜松商店",
    "支店",
    2,
    "group",
    "浜松次郎",
    "someRelMemberId",
    3,
    "浜松三郎"
  ],
  {
    "0": {
      "1": 8,
      "3": 10,
      "9": {
        "0": 6,
        "5": 4
      },
      "11": 0
    },
    "5": {
      "1": 0,
      "3": 2,
      "9": {
        "0": 6,
        "5": 4,
        "8": 7
      }
    },
    "8": {
      "1": 12,
      "3": 13,
      "9": [
        
      ],
      "11": 0
    }
  }
]
 */