こんにちは、計測システム部フロントエンドの@remsleep_zzzです。
個人の取り組みとして、QRコードのwasmライブラリを作っています。
今回はその中でも、データエンコーディングが面白いなと感じたので、どういう仕組なのかを簡単に書いてみました。
※QRコードは㈱デンソーウェーブの登録商標です
TL;DR
- データエンコーディングは、入力データの種類に応じて最適なモードを選択し、効率的にデータを圧縮する仕組み
- QRコードのデータエンコーディングには複数の仕様がある
- QRコードには40のバージョンがあり、データの種類に応じてモードを切り替える必要がある
- 数字モード：3桁ごとに10ビット
- 英数字モード：2文字ごとに11ビット
- バイトモード：1バイトごとに8ビット
- 漢字モード：1文字あたり13ビット
QRコードのデータエンコーディングは、入力データの種類に応じて最適なモードを選択し、効率的にデータを圧縮します。この仕組みにより、小さなスペースに大量の情報を格納することが可能になっています。エンコーディングの理解は、QRコードの生成や読み取りを行う上で重要な知識となります。
QRコードとは
QRコード（Quick Responseコード）は、1994年にデンソーウェーブ社が開発した2次元コードです。主な特徴は以下の通りです。
- 高速読み取りが可能
- 360°どの方向からでも読み取り可能
- 大容量のデータを格納可能（最大7,089文字）
- 汚れや破損に強い誤り訂正機能を搭載
データエンコーディングとは
QRコードのデータエンコーディングとは、入力されたデータを効率的にQRコード内に格納するためのプロセスです。主なエンコーディングモードは以下の4つです。
- 数字モード：0-9の数字のみを扱い、3桁ごとに10ビットでエンコード
- 英数字モード：数字、大文字アルファベット、一部の記号を扱い、2文字ごとに11ビットでエンコード
- バイトモード：任意の8ビットデータを扱い、1バイトごとに8ビットでエンコード
- 漢字モード：漢字を扱い、1文字あたり13ビットでエンコード
このエンコーディング作業をすることで、たくさんの文字列を2次元コードで表すことができます。
QRコード上で白い部分は0を表し、黒い部分が1を表しています。
なぞなぞ
文字列 "ZOZO2024" を英数字モードでエンコードしてみましょう。
モード指定：0010（英数字モード）
文字数：000001000（8文字を9ビットで表現）
補足として、まずモード指定ですが、これは変換されたデータの先頭につけるものです。
これでどのモードをエンコードしているのかを読み取り側に知らせます。
次に文字数です。今回は8文字を9ビットで示すということを指定しています。これはモード指定の次のブロックに記載します。
なのでこの時点でエンコード前の0と1の状態のデータでは
0010 000001000 ???????????? ???????????? ???????????? ???????????? ????????????となることが想像できます。(できましたか? 僕はコードを書いているうちに想像ができるようになりました。)
データ変換の前にヒントとなるJsonをおいておきます。
今回は英数字モードなので、45種類の文字（0-9, A-Z, 空白, $, %, *, +, -, ., /, :）を扱います。
このマッピングはQRコード規格で定義されています。
{
"0": 0,
"1": 1,
"2": 2,
"3": 3,
"4": 4,
"5": 5,
"6": 6,
"7": 7,
"8": 8,
"9": 9,
"A": 10,
"B": 11,
"C": 12,
"D": 13,
"E": 14,
"F": 15,
"G": 16,
"H": 17,
"I": 18,
"J": 19,
"K": 20,
"L": 21,
"M": 22,
"N": 23,
"O": 24,
"P": 25,
"Q": 26,
"R": 27,
"S": 28,
"T": 29,
"U": 30,
"V": 31,
"W": 32,
"X": 33,
"Y": 34,
"Z": 35,
" ": 36,
"$": 37,
"%": 38,
"*": 39,
"+": 40,
"-": 41,
".": 42,
"/": 43,
":": 44
}
文字のグループ化
まず、変換前の文字列を2文字ごとにグループ化します。
英数字モードで2文字でグループ化する理由は、データの圧縮効率を高めるためです。
この方法には以下のような利点があります。
- 効率的なビット使用
- 2文字を11ビットで表現することで、1文字あたり5.5ビットで情報を格納できます。これは、各文字を個別に6ビットで表現するよりも効率的です。
- データ圧縮
- 2文字を1つの数値に変換することで、データを圧縮し、QRコード全体のサイズを小さくすることができます。
- 読み取り速度の向上
- データ量が減少することで、QRコードの読み取り速度が向上します。これは「Quick Response（高速読み取り）」というQRコードの名前の由来にも合致します。
- エラー訂正の効率化
- データ量が少なくなることで、エラー訂正コードの割合を増やすことができ、QRコードの耐久性が向上します。
話しがそれてしまいました。
2文字のグループにすると "ZOZO2024"は "ZO", "ZO", "20". "24"となります。
文字のグループをビットに直す
1文字目の値に45を掛け、2文字目の値を加えます。
なぜ45をかけるのかというと、45×45−1=2024 が11ビットに収まるためです。
これで11ビットで2文字を表現できますね。
上記のJsonを参考にすると
ZO: Z(35) * 45 + O(24) = 1599
ZO: Z(35) * 45 + O(24) = 1599
20: 2(2) * 45 + 0(0) = 90
24: 2(2) * 45 + 4(4) = 94
という結果を得ることができました。
次にこの値を11ビットの2進数にします。
すると、
ZO:1599 → 11000111111
ZO:1599 → 11000111111
20:90 → 00001011010
24:94 → 00001011110
となりました。これで文字のビット変換は完了です。
ビットになった文字を並べて読み取り可能にする
ZO:1599 → 11000111111
ZO:1599 → 11000111111
20:90 → 00001011010
24:94 → 00001011110
結果：0010 000001000 11000111111 11000111111 00001011010 00001011110
これを8ビット単位で区切ると
00100000 01000001 11001101 01000101 00101001 11011100 00101110 10000000
これで、英数字モードで8文字を9ビットで表現することができました。
このような内部処理が実際にURLや文字列をQRコードにするときにも行われているのです。
実際のコードを書いてみる
では、先程の手作業で解いていたなぞなぞをコードで表現してみましょう。
今回はRustを使っています。
use std::collections::HashMap;
use bitvec::prelude::*;
fn main() {
let input = "ZOZO2024";
let encoded = encode_alphanumeric(input);
println!("Encoded: {:?}", encoded);
}
fn encode_alphanumeric(input: &str) -> BitVec<u8, Msb0> {
let char_values = create_char_value_map();
let mut result = BitVec::new();
for chunk in input.chars().collect::<Vec<char>>().chunks(2) {
let value = match chunk.len() {
2 => char_values[&chunk[0]] * 45 + char_values[&chunk[1]],
1 => char_values[&chunk[0]],
_ => unreachable!(),
};
let bits = match chunk.len() {
2 => 11,
1 => 6,
_ => unreachable!(),
};
result.extend_from_bitslice(&value.view_bits::<Msb0>()[(16 - bits)..]);
}
result
}
fn create_char_value_map() -> HashMap<char, u16> {
let mut map = HashMap::new();
for (i, c) in "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:".chars().enumerate() {
map.insert(c, i as u16);
}
map
}
コード解説
create_char_value_map 関数で、英数字モードの文字と値のマッピングを作成します。
encode_alphanumeric 関数が主要なエンコーディングロジックを実装しています
入力文字列を2文字ずつのチャンクに分割します。
各チャンクを対応する数値に変換します。
11ビット（2文字の場合）または6ビット（1文字の場合）のビット列に変換します。
すべてのビット列を結合して最終的な結果を生成します。
bitvec クレートを使用して、ビット操作を効率的に行っています。
メイン関数で "ZOZO2024" をエンコードし、結果を表示します。
このコードを実行すると、"ZOZO2024" の英数字モードエンコーディング結果が表示されます。
注意: このコードを実行するには、Cargo.toml に bitvec = "1.0" を依存関係として追加する必要があります。
まとめ
今回は、QRコードのデータエンコーディングをなぞなぞをしながら理解し、コードにしてみました。
QRコードのエンコードのロジックは少ない情報量で安全に文字列を扱うノウハウが詰まっていました。
ビット変換など、コンピュータサイエンスの基礎部分を再確認できたのもよかったポイントでした。
今後もRustでのwasmライブラリ実装を進めていきます。
経過なども共有できたらと考えていますので、次回作をお楽しみに。
参考資料
Discussion
2024/12/09 追記
サンプルコードですが、以下の形にしたほうがMapの作成コスト減ります。
これでメモリ使用量を最適化することができるので、こちらを参考にしてください。