Как преобразовать число в более короткое

[PAV]

___Олег___ писал(а):

PAV писал(а):

Прочитал описание кода и не до конца понял, сколько значений может принимать каждый информационный знак (без учета заголовка и окончания, которые все равно есть всегда). Также нужно знать, какой длины шестнадцатиричные строки нужно кодировать. Всегда 32 символа или произвольной длины? Есть ли какие-то закономерности в числах или они могут быть совершенно произвольными?

Шестнадцатитричные строки всегда длиною 32 символа. Закономерности в числах есть - они все уникальные, короче GUID

Это не то, я имел в виду закономерности между цифрами внутри одного числа.

Самое важное - сколько различных значений может принимать знак кода, в который осуществляется перевод. По-хорошему, в систему с таким основанием и нужно осуществить перевод.

[незваный гость]

___Олег___ писал(а):

какое-нибудь красивое решение

Боюсь, что дело здесь в объеме информации, требующей передачи. И красивых решений нет. Есть лишь способы представления. Charset C - представление по основанию 100, и мы имеем 20 пар десятичных цифр (минимум) для передачи 128 бит. Charset B суть по основанию 95, и мы имеем 20 символов. Вы можете посчитать Charset A сами. Итого, все зависит от средней длины символа в Charset B и C. Теоретически, B может быть чуть короче. Практически - я бы на месте разработчиков Code-128 возиться бы не стал, и кодировал бы каждый символ из Charset B как пару цифр из Charset C, т.е. выигрыша не будет (20 : 20).

[незваный гость]

___Олег___ писал(а):

GUID

Тогда вопрос, а все ли 128 бит значимы? Разбиваются ли они на значимые группы (например, биты 16-31 представляют код страны - отведено 16 бит, но всего 157 стран - можно сжимать)?

И вообще, стоит ли игра свеч? Ну выцарапаете Вы 5% длины штрих-кода путем неимоверного усложнения программ, переменной длины штрих-кода и т.п. А Вам это надо? Неужели каждый погонный милиметр так важен Вашему нанимателю? Ведь ему платить за разработку и сопровождение программ, дополнительное место в ПЗУ, проблемы с ошибками чтения/распознования...

[___Олег___]

PAV писал(а):

___Олег___ писал(а):

PAV писал(а):

Прочитал описание кода и не до конца понял, сколько значений может принимать каждый информационный знак (без учета заголовка и окончания, которые все равно есть всегда). Также нужно знать, какой длины шестнадцатиричные строки нужно кодировать. Всегда 32 символа или произвольной длины? Есть ли какие-то закономерности в числах или они могут быть совершенно произвольными?

Шестнадцатитричные строки всегда длиною 32 символа. Закономерности в числах есть - они все уникальные, короче GUID

Это не то, я имел в виду закономерности между цифрами внутри одного числа.

Самое важное - сколько различных значений может принимать знак кода, в который осуществляется перевод. По-хорошему, в систему с таким основанием и нужно осуществить перевод.

Закономерностей между цифрами, внутри одного числа нет. GUID генерируется на основание mac адреса сетевой карты + значение системного таймера + куча всякой лабуды..... И числа в нем значимости не представляют (хотя по идее можно из них извлечь информацию, например о том на каком компе он был сгенерирован, но этот алгоритм мне неизвестен).

"Самое важное - сколько различных значений может принимать знак кода, в который осуществляется перевод. По-хорошему, в систему с таким основанием и нужно осуществить перевод. " - если переводить шестнадцатиричные цифры, то используя Code 128, позволяющий кодировать буквенно-цифровую информацию в кодировке ASCII (Charset B) - 95 значений. Если же переводить числа в десятичной системе счисления, опять же используя Code 128 но позволяющий кодировать только числа (Charset C) - знак кода может принимать 100 различных значений.

[___Олег___]

незванный гость писал(а):

:evil:

___Олег___ писал(а):

GUID

Тогда вопрос, а все ли 128 бит значимы? Разбиваются ли они на значимые группы (например, биты 16-31 представляют код страны - отведено 16 бит, но всего 157 стран - можно сжимать)?

И вообще, стоит ли игра свеч? Ну выцарапаете Вы 5% длины штрих-кода путем неимоверного усложнения программ, переменной длины штрих-кода и т.п. А Вам это надо? Неужели каждый погонный милиметр так важен Вашему нанимателю? Ведь ему платить за разработку и сопровождение программ, дополнительное место в ПЗУ, проблемы с ошибками чтения/распознования...

Если выйгрыш составит всего порядка 5% то вы правы, с этим не стоит заморачиваться, и скорее всего никак не удастся такой объем информации значительно уменьшить, в конце концов люди уже давно придумали бы

[Kelvin]

А может попробовать пораскладывать исходное число по степеням простых чисел? Конечно же это ресурсоемко, но в итоге (в виду целости числа) должно эффективно сжиматься.

[___Олег___]

Kelvin писал(а):

А может попробовать пораскладывать исходное число по степеням простых чисел? Конечно же это ресурсоемко, но в итоге (в виду целости числа) должно эффективно сжиматься.

А по подробнее? Пример можете привести того, как это делается?

[PAV]

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

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

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

[___Олег___]

PAV писал(а):

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

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

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

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

[Kelvin]

постараюсь привести пример. только чуть позже. сейчас со временем напряг.

[___Олег___]

Пока обедал пришла в голову следующая идея: просто напросто буду делить исходное десятичное число на 2. Но т.к. без остатка на 2 делятся только четные числа, то из исходного числа буду вычитатть простое однозначное число (чтобы получилось четное). Это число (которое вычитал) буду ставить в штрих коде на первое место. Ну а алгоритм обратного преобразования достаточно прост.

[Гость]

___Олег___ писал(а):

Пока обедал пришла в голову следующая идея: просто напросто буду делить исходное десятичное число на 2. Но т.к. без остатка на 2 делятся только четные числа, то из исходного числа буду вычитатть простое однозначное число (чтобы получилось четное). Это число (которое вычитал) буду ставить в штрих коде на первое место. Ну а алгоритм обратного преобразования достаточно прост.

А блин, так все равно кол-во цифр не уменьшается, сорри

[PAV]

Я думаю, что ничего не получится.

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

И еще. Даже если таким путем удастся получить некоторое решение, то без четкого понимания того, почему оно работает, я бы оценил его как ненадежное. Может быть, оно проработает некоторое время, но в любой момент может забарахлить - в том смысле, что результаты кодирования станут достаточно длинными. Например, Вы упоминали, что в последовательности есть значение системного таймера. Соответственно, если весь ваш тестовый набор будет сгенерирован в ограниченный период времени (к примеру, в течении одного дня), то в этом поле будет закономерность, которую Вы случайно можете использовать, но понятно, что тогда в другой день результаты станут хуже.

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

[___Олег___]

PAV писал(а):

Я думаю, что ничего не получится.

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

И еще. Даже если таким путем удастся получить некоторое решение, то без четкого понимания того, почему оно работает, я бы оценил его как ненадежное. Может быть, оно проработает некоторое время, но в любой момент может забарахлить - в том смысле, что результаты кодирования станут достаточно длинными. Например, Вы упоминали, что в последовательности есть значение системного таймера. Соответственно, если весь ваш тестовый набор будет сгенерирован в ограниченный период времени (к примеру, в течении одного дня), то в этом поле будет закономерность, которую Вы случайно можете использовать, но понятно, что тогда в другой день результаты станут хуже.

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

Согласен, думаю тему на этом можно закрыть. Большое спасибо всем откликнувшимся!