【新約聖書】PowerShellスクリプトで実装する、マタイによる福音書のhtmlを85%のサイズに圧縮するアルゴリズム

やったこと

圧縮アルゴリズムどころか、自分でソートすら書けないパソコンの大先生が
PowerShellスクリプトで圧縮アルゴリズムを実装しました。

テストとして使用した文書はこちらです。htmlをutf-8で保存しました。
http://bible.salterrae.net/kougo/html/matthew.html

結果的に 190,720 バイト => 162,672 バイトと元のサイズの85%になりました。
ど素人が「減らせた」というだけでもすごくないですか？それができるPowerShellすごい。

エクスプローラで「送る」⇒「圧縮」したら 53,578 バイトになりました。28%です。
一瞬で28%に圧縮されるなんて……奇跡としか思えません。

圧縮アルゴリズムの詳細

• 4バイトずつ読み、頻出の値トップ128ランキングを作成
• 先頭に頻出値を128個書く
• トップ128に入る値は 0~0x7F の1バイトに置き換え
• トップ128に入らない値は 0x80, 4バイト値 という計5バイトに置き換え
• 4で割り切れないデータ余りの数だけ末尾に 0x81, 1バイト値 に置き換え

こちらがスクリプトです。

function ToMS {
    param ([string]$FullName)
    return [System.IO.MemoryStream]::new([System.IO.File]::ReadAllBytes($FullName))
}

function Zip {
    param ([System.IO.Stream]$Stream)

    $br = [System.IO.BinaryReader]::new($Stream)

    $yokuDeruInt32Top128 = 1..($Stream.Length / 4) | % { $br.ReadInt32() } | group | sort Count -Descending | select -First 128 | % { [int]$_.Name }
    
    $dic = @{}
    0..($yokuDeruInt32Top128.Count - 1) | % { $dic[$yokuDeruInt32Top128[$_]] = $_}

    $ms = [System.IO.MemoryStream]::new()
    $bw = [System.IO.BinaryWriter]::new($ms)

    $yokuDeruInt32Top128 | % { $bw.Write([int]$_) }
    $ms.Position = 128 * 4 #128個なくてもここまで進める

    $Stream.Position = 0
    while ($Stream.Length - $Stream.Position -ge 4) {
        $i = $br.ReadInt32()
        if ($dic.ContainsKey($i)) {
            $bw.Write([byte]$dic[$i])
        }
        else {
            $bw.Write([byte]0x80)
            $bw.Write([int]$i)
        }
    }

    while ($Stream.Length - $Stream.Position -ge 1) {
        $bw.Write([byte]0x81)
        $ms.WriteByte($Stream.ReadByte())
    }

    $ms.Position = 0
    return $ms
}

function UnZip {
    param([System.IO.Stream]$Stream)

    $br = [System.IO.BinaryReader]::new($Stream)

    $dic = @{}
    0..127 | % { $dic[$_] = $br.ReadInt32() }

    $ms = [System.IO.MemoryStream]::new()
    $bw = [System.IO.BinaryWriter]::new($ms)

    while ($Stream.Length - $Stream.Position -gt 0) {
        $b = [int]$br.ReadByte()
        if ($b -eq 0x80) {
            $bw.Write([int]$br.ReadInt32())
        }
        elseif ($b -eq 0x81) {
            $bw.Write([byte]$br.ReadByte())
        }
        else {
            $bw.Write([int]$dic[$b])
        }
    }

    $ms.Position = 0
    return $ms
}

コードを使うコマンドライン

# 圧縮してファイルに保存
> . .\zip.ps1; $ms = ToMS($pwd.Path+"\matthew.html"); $zipped = Zip($ms); [IO.File]::WriteAllBytes($pwd.Path+"\zipped", $zipped.ToArray())

# 伸長してファイルに保存
> . .\zip.ps1; $ms = ToMS($pwd.Path+"\zipped"); $unzipped = Unzip($ms); [IO.File]::WriteAllBytes($pwd.Path+"\unzipped", $unzipped.ToArray())

反省

頻出はE3 81 9F E3「た●」やE3 80 81 E3「、●」というような
3バイトの文字 + 何かの先頭1バイト　のようになっていました。

utf-8の日本語が含まれた文書を
4バイトで区切るのは効率がよくないかもしれません。

Zip が 10秒
UnZip が 40ミリ秒
でした。

> Get-WmiObject Win32_Processor


Caption           : Intel64 Family 6 Model 158 Stepping 9
DeviceID          : CPU0
Manufacturer      : GenuineIntel
MaxClockSpeed     : 2501
Name              : Intel(R) Core(TM) i5-7300HQ CPU @ 2.50GHz
SocketDesignation : U3E1

> $PSVersionTable

Name                           Value
----                           -----
PSVersion                      5.1.17763.316
PSEdition                      Desktop
PSCompatibleVersions           {1.0, 2.0, 3.0, 4.0...}
BuildVersion                   10.0.17763.316
CLRVersion                     4.0.30319.42000
WSManStackVersion              3.0
PSRemotingProtocolVersion      2.3
SerializationVersion           1.1.0.1

ほかにPowerShellで圧縮する方法

DeflateStream を使います。これはgzip圧縮できます。結果は16%です。

> $fs=[System.IO.File]::OpenRead($pwd.Path+"\matthew.html");$ms=[System.IO.MemoryStream]::new();$ds=[System.IO.Compression.DeflateStream]::new($ms,[System.IO.Compression.CompressionMode]::Compress);$fs.CopyTo($ds);$ms.Length/$fs.Length;$ds,$ms,$fs|%{$_.Close()}

---

Compress-Archive コマンドレット

圧縮する方法というか.zipファイルに圧縮する方法です。
出力ファイル名を.zipとしなければエラーになってしまいます。たとえば.appxはNGです。

Compress-Archive : .appx はサポートされるアーカイブ ファイル形式ではありません。サポートされるアーカイブ ファイル形式は
、.zip のみです。

---

アルゴリズムは圧縮率・圧縮伸長の速度・CPU使用率・メモリ使用量などのバランスで選ぶべきです。
PowerShellで圧縮するならDeflateStreamでよろしいかと思います。