XBM vs. Брайль
Мне в комментариях к предыдущей заметке задали в вопрос — а насколько графика, представленная шрифтом Брайля, проигрывает по размеру формату XBM? Я прикинул, что должна даже выигрывать — всё-таки XBM весьма многословный формат, предназначенный, прежде всего, для встраивания картинок в программы на языке Си.
Давайте посмотрим на какую-нибудь небольшую картинку:
#define bullet_width 7
#define bullet_height 7
static char bullet_bits[] = {
0x1c, 0x3e, 0x5f, 0x3f, 0x5d, 0x2a, 0x14};Что мы тут видим? Почти восемьдесят байт служебной информации, форматирование, от которого, впрочем, можно избавиться и информация о пикселях. Причём пиксели задаются группами по восемь числом в шестнадцатеричном виде и каждое такое число занимает пять байт вместе с запятой.
В итоге размер файла можно примерно оценить на как 77 + 7×7/(8/5) ≈ 107 байт. В реальности чуть больше из-за форматирования.
Если же перевести эту картинку в шрифт Брайля, то всё получится куда компактнее. Каждый символ шрифта занимает три байта и кодирует сразу восемь точек (2×4), плюс надо учесть в расчётах переводы строк: ceil(7/4) × (ceil(7/2) × 3 + 1) = 26 байт.
А есть ли условия, при которых XBM был бы компактнее его представления в Брайле?
Логика подсказывает, что это должны быть какие-то граничные случаи, вроде картинки в один пиксель по какому-то из измерений — в Брайле всё равно придётся завать восемь точек, как ни крути.
Я наугад выбрал разрешение 1×100 и угадал: 77 + 1×100/(8/5) ≈ 140 байт против ceil(1/4) × (ceil(100/2) × 3 + 1) = 151 байт.
Добавлено позднее: я не знаю как решить задачу нахождения этого порога аналитически, поэтому решил перебором, написав программу на языке R:
lhs <- \(w, h) ceiling(w/4) * (3 * ceiling(h/2) + 1)
rhs <- \(w, h) 77 + (5 * w * h) / 8
holds <- \(w, h) lhs(w, h) > rhs(w, h)
W <- 500
H <- 500
min_h <- \(w) { i <- which(holds(w, 1:H))[1]; if (is.na(i)) NULL else i }
min_w <- \(h) { i <- which(holds(1:W, h))[1]; if (is.na(i)) NULL else i }
for (w in 1:W) {
if (is.null(h <- min_h(w))) break
cat(sprintf("w = %d, h min = %d\n", w, h))
}
for (h in 1:H) {
if (is.null(w <- min_w(h))) break
cat(sprintf("h = %d, w min = %d\n", h, w))
}Получились следующие значения:
w = 1, h min = 87
w = 2, h min = 299
h = 1, w min = 201
То есть картинки 1×87, 2×299 и 201×1 (бо́льшую сторону можно увеличивать, это увеличит разрыв) занимают в Брайле больше, чем в XBM. В реальности это не точные границы, так как внутри XBM указывается название картинки, которое может быть разного размера.