30歳からのプログラミング

30歳無職から独学でプログラミングを開始した人間の記録。

Web API で文字列を可逆圧縮する

文字コード JavaScript

この記事では、 Web API で文字列の可逆圧縮を行う方法について書いていく。
任意の文字列を圧縮し、そして圧縮された文字列のリテラル表現から元の文字列を復元できることを目指す。

以前書いたように、 Node.js なら文字列の可逆圧縮は簡単に行える。

numb86-tech.hatenablog.com

また、 JavaScript でデータの圧縮を行うためのライブラリも、探してみれば色々と見つかる。

だがこの記事では、ブラウザ環境でも動作するコードを、ライブラリに頼らずに実装していく。
完成したコードは成果物の節に載せてある。

この記事に出てくるコードの動作確認は以下の環境で行った。

  • Deno 1.29.1
  • TypeScript 4.9.4

Compression Streams API

Compression Streams API は、データの圧縮や展開を行うための API で、特定の実行環境に依存せずに使うことができる。
gzip 形式や deflate 形式に対応している。

この記事では、この API を使って文字列の可逆圧縮を実装する。

注意点として、記事執筆時点ではブラウザ対応はそれほど行われておらず、例えば Firefox は対応していない。
https://developer.mozilla.org/ja/docs/Web/API/CompressionStream/CompressionStream#%E3%83%96%E3%83%A9%E3%82%A6%E3%82%B6%E3%83%BC%E3%81%AE%E4%BA%92%E6%8F%9B%E6%80%A7

文字列を Stream に変換し圧縮する

Compression Streams API はその名の通り Stream を対象とした API である。
そのため、まずは対象のデータ（今回の場合は文字列）を Stream に変換する必要がある。

Blobのインスタンスメソッドであるstreamを使うことで Stream を取得できるので、まず最初に文字列をBlobに変換する。

const originalString = "a";
const blob = new Blob([originalString]);
const stream: ReadableStream<Uint8Array> = blob.stream();

そしてその Stream をCompressionStreamインスタンスに渡す（パイプでつなげる）ことで、圧縮が行われる。
CompressionStreamコンストラクタには圧縮形式を渡すのだが、この記事ではdeflate-rawを渡すことにする。

const originalString = "a";
const blob = new Blob([originalString]);
const stream: ReadableStream<Uint8Array> = blob.stream();

const compressedStream = stream.pipeThrough(
  new CompressionStream("deflate-raw")
);

圧縮そのものはこれで完了である。

圧縮した Stream を文字列やバイナリに変換する

データを圧縮してそれで終わり、というケースは考えづらく、基本的には圧縮したデータを保存するなり何らかの処理に使うなりしたいはずである。
その際に Stream のままではなく別のデータとして扱いたいことも多い。

様々な方法があると思うが、Responseを使えば簡単に文字列やバイナリとしてデータを取得できる。
具体的には、ResponseインスタンスのarrayBufferメソッドやtextメソッドを使う。

const originalString = "a";
const blob = new Blob([originalString]);
const stream: ReadableStream<Uint8Array> = blob.stream();

const compressedStream = stream.pipeThrough(
  new CompressionStream("deflate-raw")
);

const res = new Response(compressedStream);

console.log("arrayBuffer" in res); // true
console.log("text" in res); // true

DecompressionStream で展開する

圧縮された Stream を展開するにはDecompressionStreamを使う。
使い方はCompressionStreamと同じで、インスタンスを作成する際にデータ形式を選び、それに対象の Stream をパイプすればよい。この際、圧縮時と異なるデータ形式を選択すると当然エラーになるので注意する。

const decompressedStream = compressedStream.pipeThrough(
  new DecompressionStream("deflate-raw")
);

展開によって元のデータに戻っているのか確認するが、その前にまず、圧縮によってデータが変換されていることを確認する。

以下のコードでは圧縮を行った Stream と行っていない Stream のバイナリデータを調べているが、確かに変換が行われている。

const stringToStream = (target: string): ReadableStream<Uint8Array> => {
  const blob = new Blob([target]);
  return blob.stream();
};

const streamToUint8Array = async (
  stream: ReadableStream<Uint8Array>
): Promise<Uint8Array> => {
  return new Uint8Array(await new Response(stream).arrayBuffer());
};

const originalString = "a";

const originalStream = stringToStream(originalString);

// 圧縮を行わない場合: 97
console.log(`圧縮を行わない場合: ${await streamToUint8Array(originalStream)}`);

const compressedStream = stringToStream(originalString).pipeThrough(
  new CompressionStream("deflate-raw")
);

// 圧縮を行った場合: 74,4,0,0,0,255,255,3,0
console.log(`圧縮を行った場合: ${await streamToUint8Array(compressedStream)}`);

なお、圧縮後に却ってデータが長くなってしまっているが、これは元のデータが極端に短いからであり、後述するように元データの長さが一定以上であれば基本的には圧縮効果を得られる。

97から74,4,0,0,0,255,255,3,0に変換されたデータがDecompressionStreamで元に戻るのか確認する。

const stringToStream = (target: string): ReadableStream<Uint8Array> => {
  const blob = new Blob([target]);
  return blob.stream();
};

const streamToUint8Array = async (
  stream: ReadableStream<Uint8Array>
): Promise<Uint8Array> => {
  return new Uint8Array(await new Response(stream).arrayBuffer());
};

const originalString = "a";

const originalStream = stringToStream(originalString);

// 元データ: 97
console.log(`元データ: ${await streamToUint8Array(originalStream)}`);

const compressedStream = stringToStream(originalString).pipeThrough(
  new CompressionStream("deflate-raw")
);

const decompressedStream = compressedStream.pipeThrough(
  new DecompressionStream("deflate-raw")
);

// 圧縮後に展開したデータ: 97
console.log(
  `圧縮後に展開したデータ: ${await streamToUint8Array(decompressedStream)}`
);

確かに元に戻っている。

圧縮後の文字列を展開して元の文字列を手に入れる

Compression Streams API を使えば Stream を可逆圧縮できることが分かった。
しかしこの記事でそもそもやりたかったことは、任意の文字列を圧縮し、圧縮された文字列のリテラル表現から元の文字列を復元できるようにすることである。

そのためには、圧縮後の Stream を文字列に変換しなければならない。

既述の通りResponseインスタンスにはtextメソッドがあるので、それを使えば簡単に文字列が手に入る。
だがこの方法では上手くいかない。

試しにaを圧縮し、圧縮結果をtextメソッドで取得してみる。

const stringToStream = (target: string): ReadableStream<Uint8Array> => {
  const blob = new Blob([target]);
  return blob.stream();
};

const compressedStream = stringToStream("a").pipeThrough(
  new CompressionStream("deflate-raw")
);

console.log({ a: await(new Response(compressedStream).text()) }); // { a: "J\x04\x00\x00\x00��\x03\x00" }

J\x04\x00\x00\x00��\x03\x00という文字列が手に入る。
だがこの文字列をaに戻すことはできない。置換文字である�が含まれてしまっているからだ。

他のデータと同様に文字列もまた、プログラムの内部では0と1の羅列として扱われる。その羅列を規定のルールに基づいて文字列に変換することで、文字列としての表現を得る。ルールに則っていないデータの場合、上手く文字列に変換することができない。
そして Unicode において表示不可能な文字を表現するのが、置換文字である。

numb86-tech.hatenablog.com

どんなデータであっても、文字列として有効でない場合は全て�と表示されてしまうため、もともとどのようなデータであったかという情報は失われてしまう。

CompressionStream はただデータの圧縮を行うだけであり、圧縮後のデータが文字列として有効かどうかは何も考慮しないため、このようなことが発生してしまう。
そのため、圧縮されたデータをそのまま文字列に変換するのではなく、まずは文字列として有効な形式に変換する必要がある。

今回は、圧縮後のバイト列の要素を一つずつ文字列に変換することで、文字列として有効なデータに変換する。

const stringToStream = (target: string): ReadableStream<Uint8Array> => {
  const blob = new Blob([target]);
  return blob.stream();
};

const compressedStream = stringToStream("a").pipeThrough(
  new CompressionStream("deflate-raw")
);

const arrayBuffer = await(new Response(compressedStream).arrayBuffer());

// 圧縮後のデータの Uint8Array による表現を手に入れる
const bytes = new Uint8Array(arrayBuffer);

let binaryString = "";
for (let i = 0; i < bytes.byteLength; i++) {
  // Uint8Array の各要素は 0..255 の範囲内になるので、それを Code Unit として利用すれば必ず有効な文字列を得られる
  binaryString += String.fromCharCode(bytes[i]);
}

console.log({ binaryString }); // { binaryString: "J\x04\x00\x00\x00ÿÿ\x03\x00" }

置換文字を消すことができた。これで、元の文字列に復元することが可能になる。

ここまでに行った処理を整理すると、以下のようになる。

  1. 圧縮したい文字列を Stream に変換する
  2. CompressionStreamで Stream を圧縮する
  3. 圧縮された Stream のUint8Arrayによる表現を手に入れる
  4. Uint8Arrayの各要素を Code Unit として使って文字列を作る

なので、それと逆の処理を行えば元の文字列が手に入る。

  1. 展開したい文字列の Code Unit を取得して、それを使ったUint8Arrayを作る
  2. Uint8Arrayを Stream に変換する
  3. DecompressionStreamで Stream を展開する
  4. 展開された Stream を文字列に変換する
const str = "J\x04\x00\x00\x00ÿÿ\x03\x00";

const bytes = new Uint8Array(str.length);
for (let i = 0; i < str.length; i++) {
  bytes[i] = str.charCodeAt(i);
}

const stream = new Blob([bytes]).stream();

const decompressedStream = stream.pipeThrough(
  new DecompressionStream("deflate-raw")
);

console.log(await new Response(decompressedStream).text()); //a

Base64 を使う

これで圧縮と展開を行えるようになったので、この時点で当初の目的は達成できている。
だが、aの圧縮結果であるJ\x04\x00\x00\x00ÿÿ\x03\x00を見れば分かるように、U+0004やU+0000のような制御文字も含まれてしまっている。

圧縮後の文字列の用途によっては、制御文字が含まれていると都合が悪かったり扱いづらかったりすることがある。
そのような場合、圧縮後の文字列を Base64 でエンコードすることで、制御文字を取り除くことができる。
その場合はもちろん、展開する際にまずデコードする必要がある。

上記で説明した圧縮方法では、各文字は全て Latin1 の範囲内に収まるので、btoaでエンコードできる。

Base64 や Latin1 、btoaについては以下の記事を参照。

numb86-tech.hatenablog.com

成果物

ここまでの内容を関数としてまとめたのが以下。Base64 によるエンコードも行うようにしている。

const compress = async (target: string): Promise<string> => {
  const arrayBufferToBinaryString = (arrayBuffer: ArrayBuffer): string => {
    const bytes = new Uint8Array(arrayBuffer);

    let binaryString = "";
    for (let i = 0; i < bytes.byteLength; i++) {
      binaryString += String.fromCharCode(bytes[i]);
    }

    return binaryString;
  };

  const blob = new Blob([target]);
  const stream = blob.stream();
  const compressedStream = stream.pipeThrough(
    new CompressionStream("deflate-raw")
  );

  const buf = await new Response(compressedStream).arrayBuffer();

  const binaryString = arrayBufferToBinaryString(buf);
  const encodedByBase64 = btoa(binaryString);
  return encodedByBase64;
};

const decompress = async (target: string): Promise<string> => {
  const binaryStringToBytes = (str: string): Uint8Array => {
    const bytes = new Uint8Array(str.length);
    for (let i = 0; i < str.length; i++) {
      bytes[i] = str.charCodeAt(i);
    }
    return bytes;
  };

  const decodedByBase64 = atob(target);
  const bytes = binaryStringToBytes(decodedByBase64);

  const stream = new Blob([bytes]).stream();

  const decompressedStream = stream.pipeThrough(
    new DecompressionStream("deflate-raw")
  );

  return await new Response(decompressedStream).text();
};

動作確認してみると、圧縮も展開も上手くいっている。
元の文字列の内容にもよるのだが、基本的には、文字列が長くなればなるほど圧縮効果は大きくなる。

const originalString = `<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Document</title>
</head>
<body>
  <p>abc</p>
  <p>abc</p>
  <p>abc</p>
  <p>123</p>
  <p>123</p>
  <p>123</p>
</body>
</html>
`;

const compressed = await compress(originalString);
// hI69EoIwDMf3PkXs7vXUxSF0EV11wMExlJxw1xYOwsDbA+0DMOV+Sf4feCrfj+r3eUIrwVuF+wBP8V9ojnpfMDVWAWBgIXAtjRNLob/V63zX6SCdeLZl7+bAUdBkVmiyFOu+WdLjYKl2aIZDuFxvB4Amu24hqfcKAAD//wMA
console.log(compressed);

const decompressed = await decompress(
  "hI69EoIwDMf3PkXs7vXUxSF0EV11wMExlJxw1xYOwsDbA+0DMOV+Sf4feCrfj+r3eUIrwVuF+wBP8V9ojnpfMDVWAWBgIXAtjRNLob/V63zX6SCdeLZl7+bAUdBkVmiyFOu+WdLjYKl2aIZDuFxvB4Amu24hqfcKAAD//wMA"
);

console.log(decompressed === originalString); // true

console.log(`${originalString.length} -> ${compressed.length}`); // 200 -> 168

ブラウザ環境での動作確認

compressとdecompressから型注釈を取り除いて Google Chrome (108.0.5359.124) で実行すると、問題なく動く。
ただ、 Deno とは Compression Streams API の実装が異なるらしく、圧縮した結果が異なる。

// Deno
await compress("a"); // SgQAAAD//wMA

// Google Chrome
await compress("a"); // 'SwQA'

その一方で、どちらの環境で圧縮した文字列であっても、どちらの環境でも復元できる。

// `SwQA`も`SgQAAAD//wMA`も decompress に渡すと`a`になる
// Deno でも Chrome でもどちらでもそうなる
await decompress("SwQA"); // a
await decompress("SgQAAAD//wMA"); // a

Firefox (108.0.1) でcompressを実行しようとすると、CompressionStreamが存在しないためエラーになる。

ReferenceError: CompressionStream is not defined

参考資料