Кодирование строк в небольшие размеры для генерации QRCode - PullRequest
Новая
       29

Кодирование строк в небольшие размеры для генерации QRCode

1 голос
/ 21 апреля 2011

Я генерирую QR-коды, используя строки, которые очень легко могут быть длиннее, чем QRCode. Я ищу предложения по алгоритмам для кодирования этих строк как можно меньшего размера или доказательство того, что строка не может быть уменьшена в дальнейшем.

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

    function encodeLookUp(character){
        switch(character){
            case '0': return '0000';
            case '1': return '0001';
            case '2': return '0010';
            case '3': return '0011';
            case '4': return '0100';
            case '5': return '0101';
            case '6': return '0110';
            case '7': return '0111';
            case '8': return '1000';
            case '9': return '1001';
            case '|': return '1010';
            case ':': return '1011';
        }
        return false;
    }

Используя эту таблицу, я уже делаю кодировку 16, поэтому каждый из 32 символов ascii из исходной строки становится половиной символа в новой строке (фактически вдвое меньше длины). 

Starting String:  01251548|4654654:4465464 // ID1 | ID2 : ID3   demonstrates both pipes.
Bit String:  000000010010010100010101010010001010010001100101010001100101010010110100010001100101010001100100
Result String:  %H¤eFT´FTd // Half the length of the starting string.

Затем этот новый код ascii переводится в соответствии со спецификацией QRCode.

РЕДАКТИРОВАТЬ: наибольшее количество символов в настоящее время кодируется: 384

УТОЧНЕНИЕ: цифровая длина идентификатора и количество идентификаторов или каналов являются переменными с тенденцией к единице. Я пытаюсь сократить этот алгоритм, чтобы он содержал в среднем наименьшее количество символов к моменту, когда он является «строкой результата».

ПРИМЕЧАНИЕ. Результирующая строка является только представлением ascii двоичной строки, которую я закодировал с данными для соответствия стандартным спецификациям QRCode и считывателям.

Ответы [ 5 ]

0 голосов
/ 22 апреля 2011

QR-коды поддерживают двоичный режим, и это будет наиболее эффективный способ хранения ваших идентификаторов. Или:

  1. Выберите длину (в байтах), достаточную для хранения всех ваших идентификаторов, и закодируйте QR-код в виде последовательности целых чисел фиксированной длины. 4 байта (32 бита) - это стандартный выбор, который должен охватывать вероятный диапазон, или
  2. Если вы хотите иметь возможность кодировать широкий диапазон идентификаторов, но ожидаете, что большинство значений будут маленькими, используйте схему кодирования переменной длины. Одним из примеров является использование младших 7 битов каждого байта для хранения целого числа и самого старшего бита для указания наличия дополнительных байтов.

Также обратите внимание, что QR-коды могут быть намного длиннее 384 символов!

Редактировать: Исходя из вашего первоначального вопроса, похоже, вы кодируете больше, чем просто последовательность целых чисел - у вас есть по крайней мере два разных типа разделителей. Где они могут появиться и при каких обстоятельствах? Формат кодирования будет зависеть от этих параметров.

0 голосов
/ 22 апреля 2011

В качестве начала ответа на мой собственный вопрос:

Если я начну со строки чисел

, я могу разобрать эту строку для шаблонов и удерживать эти шаблоны в специальных символах, которыеможет занять другие 4 пробела, доступные в моем дереве Хаффмана.

РЕДАКТИРОВАТЬ: Пример: начальная строка 12222345, конечная строка 12x345.Где x - символ, который означает «повторить последний символ еще 3 раза»

0 голосов
/ 21 апреля 2011

Если у вас есть относительно неслучайные данные, хорошим решением может быть кодировка Хаффмана .

0 голосов
/ 21 апреля 2011

QR-коды уже имеют специальные режимы кодирования, которые оптимизированы для цифр или только буквенно-цифровых данных.Вероятно, было бы легче воспользоваться этими преимуществами, чем придумывать схему.

Если вы собираетесь делать что-то нестандартное, я думаю, вам будет трудно победить что-то вроде сжатия gzip.Просто распакуйте байты, закодируйте их в байтовом режиме и распакуйте на другом конце.

0 голосов
/ 21 апреля 2011

Используя эту функцию, вы потеряете много места (поскольку 4 бита - это слишком много для 12 комбинаций).

Я бы начал с просмотра максимально возможной длины ваших идентификаторов и нашел бы подходящий блок хранения.

Если вы храните эти предметы последовательно в фиксированном количестве (скажем, 4 идентификатора). Вам потребуется максимум id_length * id_count, и вам не нужно будет использовать какие-либо разделители.

Редактировать: Опять-таки, в зависимости от количества идентификаторов, которые вы хотите записать, и их ожидаемой максимальной длины, могут быть различные типы кодировок для сжатия. RLE (кодирование длин серий) пришло мне в голову.

...