Эффективное сжатие и представление пар ключ-значение для считывания с одномерных штрих-кодов.

В настоящее время я пишу приложение для Windows Mobile, которое должно иметь возможность выбирать пары значений ключа из штрих-кодов 1D (настройки конфигурации). Чем меньше штрих-кодов нужно сканировать, тем лучше. Пример ввода:

------------------------------
| Key | Value                |    
------------------------------
| 12  | Söme UTF-8 Strîng    |
|  9  | & another string     |
------------------------------

Я придумал следующий алгоритм:

<сильный>1. Объедините пары ключ-значение и закодируйте значения с помощью Base64

Таким образом, мы получим что-то вроде 12=U8O2bWUgVVRGLTggU3Ryw65uZw==&9=JiBhbm90aGVyIHN0cmluZw==

<сильный>2. Используйте кодировку Хаффмана для сжатия данных

Я бы использовал для этого фиксированное дерево Хаффмана со следующей информацией, которая помогает мне сжимать данные:

-------------------------------------------
| Enties                       | Priority |    
-------------------------------------------
| =, &                         | High     |
| 0-9                          | Medium   |
| 5-bit Base64 Words (w/o 0-9) | Low      |
-------------------------------------------

<сильный>3. Создание штрих-кодов Code 128B из закодированных данных

Примените кодировку Base96 к битовому потоку, сгенерированному алгоритмом Хаффмана, чтобы получить символы ASCII, которые можно использовать в штрих-коде Code 128B. При необходимости разделите полученную строку на несколько штрих-кодов.

Кодирование этих шагов не будет для меня проблемой, но я хотел бы получить отзывы об эффективности и дизайне алгоритма.

Вопросы

  • Я где-то теряю потенциал для лучшего сжатия/укорочения строк?
  • Есть ли лучший способ сжать случайные данные в кодировке UTF8?
  • Должен ли я встраивать динамическую таблицу Хаффмана в закодированные данные?
  • Как я могу учесть сжатие Code 128B (0 требует меньше места, чем &)?

compression barcode huffman-code code128
person Gene    schedule 07.03.2013    source источник

Ответы (3)


arrow_upward
2
arrow_downward

Одним из простых способов было бы определить все 64 символа, напрямую сопоставленные с кодом 128. это оставит 30-40 доступных слотов с кодом 128. В остальных слотах определите несколько двойных символов. == =& 0= 1= 2= 3= 4= 5= 6= 7= 8= 9= &0 &1 &2 &2 &5 &5 &6 &7 &8 &9 (повторить последний символ)= =(двойной следующий символ) &(двойной следующий символ персонаж)

person Fred F    schedule 09.03.2013

arrow_upward
1
arrow_downward

После долгих игр и возни, мы, наконец, выбрали этот подход:

<сильный>1. Кодировать настройки в поток байтов

Значения полей сериализуются в поток байтов с заголовком для каждого поля. Заголовок занимает один байт и содержит идентификатор поля и некоторые флаги, помогающие уменьшить объем передаваемых данных. В зависимости от типа поля (например, строка, число или IP-адрес) значение эффективно кодируется в поток байтов. Например, IP-адрес кодируется 4 байтами, тогда как логический флаг кодируется непосредственно в заголовке поля. Таким образом, мы можем кодировать в поток даже SSL-сертификаты, если это необходимо. Поскольку типичные форматы штрих-кода не могут передавать произвольные значения байтов, на следующем шаге нам необходимо закодировать поток байтов.

<сильный>2. Преобразование в формат штрих-кода

Результирующий массив байтов теперь обрабатывается как большое целое число и преобразуется в целевой формат штрих-кода с использованием базовой кодировки и набора символов (см. into-7-bit-words-with-96-states-max">этот вопрос). Таким образом, мы эффективно используем формат штрих-кода для передачи наших данных (в отличие от Base64 или других кодировок). Из полученной строки мы можем выделить отдельные штрих-коды и добавить к ним некоторую дополнительную информацию заголовка (например, сколько штрих-кодов нужно отсканировать? зашифрованы ли данные?...).

Когда штрих-коды сканируются на мобильном устройстве, закодированная строка может быть восстановлена ​​и преобразована в такое же большое целое число. Затем это целое можно рассматривать как массив байтов, который можно проанализировать, если известен формат сериализации поля.

Этот подход оказался очень эффективным и быстрым (у нас были некоторые опасения по поводу реализация BigInteger на CF).

person Gene    schedule 13.09.2013
comment
Базовый пример реализации см. в разделе stackoverflow.com/questions/50343973/ - person Gene; 15.05.2018

arrow_upward
0
arrow_downward

В то время как некоторые форматы штрих-кода имеют фиксированный набор символов, которые они могут представлять, и используют одинаковое количество места для хранения каждого символа, другие либо используют несколько наборов символов, либо используют переменное количество места для хранения каждого символа. Например, «классический» код 39 определяет 43 символа, каждый из которых представлен одним из 43 символов, и просто не может представлять какие-либо другие символы, но есть еще один вариант кода 39, который представляет 39 общих символов с помощью одного символа, а другие символы с помощью двухсимвольная последовательность. Предположим, например, что кто-то хочет сохранить набор двоичных данных в штрих-коде code-39. Если преобразовать данные в формат base-64, четыре символа, связанные с тремя октетами необработанных данных, вероятно, займут в среднем около 5,69 символов для хранения [около 27 из 64 символов, используемых в base64, занимают два символа для хранения в коде 39]. Если вместо этого выбрать 32 символа, каждый из которых может быть представлен одним символом, можно было бы хранить 24 (или 25) битов, используя пять октетов для хранения пяти битов в каждом [стабильные 1,67 символа на октет по сравнению со средним значением 1,89 и худшим случаем 2,67]. ]. Если бы кто-то использовал «классический» код 39 (который может представлять 43 символа с использованием одного символа каждый), можно было бы даже хранить четыре октета в шести символах [в среднем 1,5 символа на октет].

Различные форматы штрих-кодов «оптимизированы» для разных наборов символов; некоторые, такие как Code 128, имеют несколько наборов символов и могут эффективно использоваться с данными, которые используют полный диапазон одного набора символов, избегая при этом использования символов за его пределами. Я не знаю каких-либо конкретных рекомендуемых подходов к переформатированию данных, чтобы оптимизировать использование наборов символов определенной символики, но изучение кодировки, используемой символикой, и ваших конкретных требований должно помочь вам выяснить, какая кодировка будет лучше всего работать для ваших целей. применение.

person supercat    schedule 05.12.2013