[Перевод] 10 > 64: как хранить больше данных в QR-кодах
Для кодирования данных в десятичном формате требуется гораздо больше символов, чем для тех же данных, но закодированных в base64 — 06513249 против YWJj. Однако это правило не работает, когда речь идёт о QR-кодах. В них гораздо лучше работает использование десятичных чисел. Никакой магии, просто все дополнительные цифры сохраняются настолько эффективно, как если бы кодирования вообще не было. Десятичная кодировка позволяет QR-кодам хранить больше данных, а ещё их легче сканировать.
В статье расскажу:
как на практике использование десятичной кодировки снижает (незначительно) плотность QR-кода, содержащего URL-адрес;
почему это так работает: все десятичные данные безопасны для URL-адресов и эффективно сохраняются в числовом режиме QR-кода, в то время как base64 даёт 75% потерь, поскольку данные приходится хранить в двоичном формате;
как запихнуть максимум данных в URL в QR-код.
Два QR-кода, которые кодируют одни и те же данные: левый, использующий base64, немного плотнее, чем правый, использующий десятичную систему (сравните участки в вверху по центру). Большие модули (маленькие квадраты) десятичного QR-кода облегчают сканирование.
В статье «Механическая симпатия к QR-кодам: улучшение регистрации в Новом Южном Уэльсе» я исследовал QR-коды, используемые для отслеживания контактов COVID. Оказывается, несколько штатов включили кучу информации в URL-адреса своих QR-кодов в виде JSON-объекта в кодировке Base64, предположительно потому, что это удобно.
Они использовали URL-адреса с 228-символами, типа такого: https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app? data=eyJ0IjoiY292aWQxOV9idXNpbmVzcyIsImJpZCI6IjEyMTMyMSIsImJuYW1lIjoiVGVzdCBOU1cgR292ZXJubWVudCBRUiBjb2RlIiwiYmFkZHJlc3MiOiJCdXNpbmVzcyBhZGRyZXNzIGdvZXMgaGVyZSAifQ==, причём это eyJ..
.был большим двоичным объектом. На уровне исправления ошибок H
это можно закодировать в QR-код 81×81 (версия 16).
Если всё же нужно хранить данные в формате JSON (в статье описано, почему мы этого не делаем), есть способы эффективнее base64: переписав данные в десятичный формат, мы получим 353-символьный урл https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app? data=072685680885510189821994892577900638215789419258463239488533499278955911240512279111633336286737089008384293066931974311305533337894591404330656702603998035920596585517131555967430155259257402711671699276432408209151397638174974409842883898456527289026013404155725275860173673194594939.
Любой здравомыслящий человек скажет, что это на 50% длиннее. К счастью, для QR-кодов всё немного иначе, и там потребуется на 20% меньше модулей (квадратиков). Вышеуказанный урл умещается в QR-код 73×73 (версия 14).
QR-коды с меньшим количеством модулей легче сканировать.
Сложные данные в URL-адресах
QR-коды могут хранить произвольные данные, но обычно они используются для хранения URL-адреса, чтобы при сканировании можно было перейти на сайт и получить оттуда всю полезную информацию. С другой стороны, QR-код может быть размещён где-то, где нет доступа к интернету, и он тоже должен содержать достаточное количество полезной информации. Это приводит к появлению URL-адресов с большим количеством данных.
Однако URL-адрес — это ограниченный контейнер: попытка вставить в него произвольные данные может привести к проблемам, связанным с неправильной интерпретацией или искажением спецсимволов. К счастью, URL-адреса в основном представляют собой просто текст, а способов преобразования произвольных данных в текст существует множество: на странице Википедии о кодировании двоичных данных в текст описано аж 28 штук.
Один из самых распространённых, пожалуй, Base64: он встроен в каждый браузер. Например тот, с которого вы сейчас читаете эту статью. Base64 кодирует 3 байта в 4, выбранные из сокращённого 64-символьного алфавита. Это разумный выбор по умолчанию. Его можно включать в атрибуты JSON, HTML/XML, CSS и, конечно же, URL-адреса.
Всё это означает, что данные base64 могут оказаться в QR-кодах, где закодирован URL-адрес, содержащий большой объем данных. К сожалению, base64 — плохой метод кодирования двоичных данных в QR-коде: выбор алфавита вынуждает QR-код хранить данные неоправданно неэффективным способом.
Схемы кодирования
Существует огромное множество способов закодировать набор произвольных байтов в сокращённый набор символов. Мы подробно рассмотрим base64, base10 и base45 из RFC 9285, который разработан для QR-кодов (другие, такие как base16 (шестнадцатеричный), base32 или base36, явно хуже).
кодирование | персонажи | соотношение ввод: вывод | пример | URL-адрес безопасен? |
отсутствует | символы | 1 | abc | нет |
база64 | 0–9, A–Z, a–z, +, / | 1.33 | YWJj | частично |
base64url | 0–9, A–Z, a–z, -, _ | 1.33 | YWJj | да |
base45 | 0–9, A–Z, $%*±.:/, пробел | 1,5 | 0EC92 | нет |
base10 | 0–9 | 2.41 | 06513249 | да |
Некоторые из них являются безопасными URL: закодированные данные могут быть внесены непосредственно в URL-адрес, не требуя какого-либо специального экранирования или обработки, в то время как другие таковыми не являются или могут потребовать специальной обработки со стороны сервера. Мы собираемся размещать данные в URL-адресах, поэтому безопасность URL-адресов является обязательным требованием. Так что нам нужно рассматривать следующие варианты:
Я придумал «base10» благодаря тому, что рассматривал байты как огромное целое число (с прямым порядком байтов) по основанию 256, а затем напечатал целое число в другой системе счисления. Это не скейлится до больших данных, но отлично работает для пары килобайт, которые можно сохранить в QR-коде. Версия Python может быть такой:
import math
_DIGITS_PER_BYTE = math.log(2**8, 10)
def b10encode(data: bytes) -> str:
raw = str(int.from_bytes(data, byteorder="little"))
# Handle leading zeros so that, for instance, b"", b"\x00"
# and b"\x00\x00" each have their own unique encoding, not
# just "0".
encoded_length = math.ceil(len(data) * _DIGITS_PER_BYTE)
prefix = "0" * (encoded_length - len(raw))
return prefix + raw
def b10decode(s: str) -> bytes:
# Deduce the length of the result from the input, matching
# b64encode's zero-padding (NB. a real implementation
# should validate the length is valid)
decoded_length = math.floor(len(s) / _DIGITS_PER_BYTE)
return int(s).to_bytes(
length=decoded_length,
byteorder="little",
)
В таблице в столбце «Соотношение ввода: вывода» показано, какое количество выходных символов потребуется (в среднем) свыше количества входных символов.
Например, при кодировании в base10 длинные входные данные практически соответствуют среднему значению, тогда как короткие входные данные могут различаться сильнее:
ввод (шестнадцатеричный) | вывод | соотношение |
01 | 001 | 3/1 = 3 |
12 34 56 | 05649426 | 8/3 = 2,67 |
FF FE… 01 00 | 00000496…7615 (617 цифр) | 617/256 = 2,41 |
Режимы QR кодов
QR-код хранит данные в битовом потоке, а входные данные закодированы в сегментах. Каждый сегмент данных может быть закодирован в одном из четырёх различных режимов. Каждый режим поддерживает разные входные данные. Например, «буквенно-цифровой» режим, который поддерживает сохранение только цифр, заглавных букв и некоторых знаков препинания, определяя способ сопоставления этих символов с битами для хранения.
режим | символы | бит на символ | издержки |
Цифровой | 10:0–9 | 3.33 | 0,34% |
Буквенно-цифровой | 45: 0–9, A–Z, $%*±.:/ пробел | 5,5 | 0,15% |
Двоичный | 256: произвольные байты | 8 | 0% |
Кандзи | 8189 1 | 13 | 0,0041% |
Для цифрового и буквенно-цифрового режимов несколько входных символов сохраняются вместе, что приводит к дробным битам для одного символа. Например, цифровой режим сохраняет группы из 3 цифр в 10 бит, например, 123456 кодируется двумя фрагментами, 123, а затем 456 — в 20 бит.
«Издержки», пусть и небольшие, будут, в любой кодировке. Удобно, что 103 лишь немногим меньше 210, а 452 меньше 211.
Когда QR-код содержит несколько фрагментов данных, он все равно представляет собой один длинный поток символов, поэтому продуманный выбор фрагментов позволяет подобрать оптимальный режим для каждой значимой подстроки входных данных.
А-ля десятичный режим
Режим, необходимый для хранения закодированных данных, зависит от набора выходных символов. Для кодировок, которые мы рассмотрели выше:
кодирование | символы | QR-режим |
base64url | A–Z, a–z, 0–9, -, _ | Двоичный |
base10 | 0–9 | Цифровой |
Base64url содержит строчные буквы и поэтому при сохранении в QR-коде требует двоичного режима. 3 входных байта (24 входных бита) превращаются в 4 выходных символа, и эти 4 символа должны быть сохранены в 4×8 = 32 битах QR-кода. В итоге средние издержки составляют 33%: 1 входной байт сохраняется как 1,33 байта в QR-коде. Каждый байт может хранить до 256 различных значений, но кодировка base64 использует только 64 из них. Это приводит к потере 75% значений, или по 2 бита в каждом сохранённом байте.
Для base10 расчёт не так прост, но мы можем его выполнить
Входными данными будет некоторое количество 8-битных байтов, каждый из которых имеет 28 = 256 возможных значений.
Каждый входной байт
log(256, 10)
в среднем превращается в ≈ 2,408 выходных цифр.3 цифры хранятся в 10 битах.
В сумме
10 / 3 * log(256, 10)
для хранения каждого входного байта требуется ≈ 8,027 бит.
В результате 1 входной байт сохраняется в среднем как 1,0034 байта: издержки составляют 0,34%.
Это именно издержки самого цифрового режима. На этапе кодирования двоичного текста в кодировке Base10 издержки отсутствуют! Для кодирования тех же данных в Base10 требуется на 242% больше символов, но эти символы можно эффективно сохранить в QR-коде. При хранении не остаётся излишков.
Резюмируем
Давайте вернёмся к нашему URL-адресу, который был раньше: https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app? data=eyJ0IjoiY292aWQxOV9idXNpbmVzcyIsImJpZCI6IjEyMTMyMSIsImJuYW1lIjoiVGVzdCBOU1cgR292ZXJubWVudCBRUiBjb2RlIiwiYmFkZHJlc3MiOiJCdXNpbmVzcyBhZGRyZXNzIGdvZXMgaGVyZSAifQ==
Параметр "data=”
содержит некоторый JSON в кодировке Base64. Это можно закодировать и получше, без JSON или base64, но давайте предположим, что нужно сделать именно JSON. Мы можем взять большой двоичный объект eyJ0I…
и декодировать его в базовый JSON: {"t":"covid19_business","bid":"121321","bname":"Test NSW Government QR code","baddress":"Business address goes here "}.
Пропуск этих байтов через функцию b10encode даёт очень длинное число: 072685680885510189821994892577900638215789419258463239488533499278955911240512279111633336286737089008384293066931974311305533337894591404330656702603998035920596585517131555967430155259257402711671699276432408209151397638174974409842883898456527289026013404155725275860173673194594939.
Десятичная кодировка кажется человеку длинной, но для кодирования QR-кода она проще и занимает лишь немногим больше места, чем требуется необработанному JSON [^base16-base32-base36]:
строка | длина |
необработанный JSON | 118 байт |
кодировка base64 | 160 символов |
хранилище base64 QR | 160 байт |
кодировка base10 | 285 цифр |
хранилище base10 QR | 119 байт |
Вы можете спросить о других кодировках, таких как base16 (шестнадцатеричная), base32 и base36 (которые подходят для буквенно-цифрового режима) или base 8 (подходят для цифрового режима, но с ними легче работать, чем с base10). Они менее эффективны для цифрового режима, чем base10, но в некоторых случаях потенциально более удобны.
В URL-адресе остальная часть не является чисто числовой, поэтому для того, чтобы увидеть преимущества этого кодирования, необходимо использовать два сегмента:
один со «скучными» фрагментами URL-адреса в начале, вероятно, с использованием двоичного режима
один с большим блоком данных в формате Base10, используя числовой режим
С использованием Segno 1.6.1 можно увидеть что-то типа такого:
url_prefix = "https://www.service.nsw.gov.au/campaign/service-nsw-mobile-app?data="
encoded_data = b10encode(data)
# Two segments, so that they're encoded with separate modes
qr = segno.make([url_prefix, encoded_data])
В QR-кодах регистрации COVID Нового Южного Уэльса использовался уровень исправления ошибок H. Если взять это за основу и просто поменять кодировку параметра data, мы увидим результат из начала поста:
Два QR-кода, которые кодируют одни и те же данные: левый использует base64, что даёт QR-код 81×81 (версия 16), а правый использует base10, что даёт QR-код 73×73 (версия 14).
Крайние значения
Умение выбирать режимы, кодировки и сегменты позволяет удовлетворить ограничения формата QR-кода. QR-коды могут хранить до 23,6 килобит ≈ 3,0 КБ при использовании версии 40 с уровнем исправления ошибок L. Это соответствует примерно 7 тысячам десятичных цифр в числовом режиме или 3 тысячам байтов в двоичном режиме.
Мы можем попробовать это на нескольких тестовых URL-адресах типа http://example.com/{encoded_data}. Максимум, который мы можем уместить в QR-код, выглядит так:
Кодирование | Входные данные | Длина URL-адреса |
base64url | 2,2 КБ | 2,9 тыс. |
base10 | 2,9 КБ | 7.0 тыс. |
Теоретически, гораздо более длинный URL base10 не имеет значения: благодаря QR-режиму он сжимается очень эффективно.
Однако после публикации этой статьи было отмечено, что iOS неправильно сканирует огромный URL-адрес base10, читая http://example.com вместо http://example.com/310…
Значит, длина URL имеет значение! Похоже, что это ограничение длины отличается от обычных ограничений URL, поскольку 8 КБ — это разумный нижний предел для «нормальных» браузеров в наши дни, так что 7 тыс. символов должны быть безопасными. Вставка той же ссылки в Safari напрямую работает отлично!
Так что лучше проведите собственное тестирование.
Два максимальных QR-кода, которые для большинства людей почти не отличаются друг от друга. Но мы с вами знаем, что второй содержит на 33% больше данных.
Спасибо за внимание!