оптимальная перекодировка

[Missir]

Имеется массив около 120 чисел, каждое из которых закодировано 2 байтами, при этом, в каждом байте 3 бита имеют одни и те же значения, т.е. не несут информации. Таким образом, для кодирования используется 10 бит, хотя понятно, что для этого вполне достаточно 7 бит. Стоит задача перекодировать исходные числа так, чтобы уместить данные в 7 бит.

Первое, что пришло в голову:
определяется бит, содержащий одинаковое число нулей и единиц, его можно использовать без изменений,
далее определяется второй бит, содержащий в каждой из 2-х полученных ранее групп равное, или почти равное, число нулей и единиц. Этот бит тоже можно использовать без изменений. Найденные биты делят массив на 4 примерно равные части.
Остальные биты уже не позволяют поделить полученные группы поровну. Однако, можно построить логические функции исходных бит, позволяющие это сделать. Первые 2 функции плучаются сравнительно простыми, а их использование в качестве дополнительных битов искомого кода позволяет поделить массив на 16 примерно равных частей. Далее ситуация усложняется, какую либо простую логическую функцию, позволяющую дальше делить полученные группы на равные части, получить сложно. А их нужно построить ещё 3. Вообще подход представляется тупиковым.

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

[dgwuqtj]

А чем не устраивает вариант просто отсортировать все числа, выкинуть повторы и закодировать каждое число его порядковым номером (начиная с 0)?

[mihaild]

Missir в сообщении #1654989 писал(а):

при этом, в каждом байте 3 бита имеют одни и те же значения, т.е. не несут информации

Что это значит? Что в каждом байте например первый и второй бит всегда единицы а третий нуль? Или что в каждом байте например первый второй и третий биты всегда одинаковые?
Или что в каждом байте есть либо три единицы, либо три нуля? (это понятно бесполезное знание)

Missir в сообщении #1654989 писал(а):

Таким образом, для кодирования используется 10 бит, хотя понятно, что для этого вполне достаточно 7 бит

Откуда взялись эти числа? Вроде бы 2 байта - это 16 бит, так что используется 16, а можно было бы обойтись 10.
А на что влияет двухбайтовость чисел, если вся информация про отдельные байты?

[Missir]

mihaild в сообщении #1654998 писал(а):

Что это значит? Что в каждом байте например первый и второй бит всегда единицы а третий нуль?

да именно так

mihaild в сообщении #1654998 писал(а):

Откуда взялись эти числа? Вроде бы 2 байта - это 16 бит, так что используется 16, а можно было бы обойтись 10

это естественные числа, 10 бит из 16 получаются просто отбрасыванием незначащих бит, но нужно убрать ещё 3, проблема в этом

-- 16.09.2024, 21:02 --

есть идея попробовать преобразовывать биты, например так: y1=x1 and x2, y2=x1 or x1, чтобы в итоге выделить незначащий бит, далее второй и третий, но здесь нужна пара булевых функций, применение которой не влечёт потери информации. Функции and и or для этого кажется не подходят. Существует вообще такая пара?

-- 16.09.2024, 21:25 --

dgwuqtj в сообщении #1654997 писал(а):

чем не устраивает вариант просто отсортировать все числа, выкинуть повторы и закодировать каждое число его порядковым номером

стоит задача вычисления 7 битного кода по 10 исходным битам, а не определения соответствия одного другому
можно по идее взять массив размером 1024, и в 120 ячейках, с адресами, определяемыми 10 битным кодом разместить что нужно,
но это слишком брутально и расточительно

[zgemm]

Missir в сообщении #1654989 писал(а):

в каждом байте 3 бита имеют одни и те же значения

а можно полюбопытствовать хотя бы на одно восьмибитное число в двоичном представлении , в котором нет трех бит с одинаковым значением?

[Missir]

нет, нельзя

[Dmitriy40]

Missir
Без дополнительной информации (если все 10024 кода равновероятны) разумеется невозможно универсально сжать 10 бит в 7.
Если не сильно волнуют коллизии, то можно применить хэш-функцию для сворачивания 10 бит в 7, например $H(x)=x \bmod 127$ или $H(x)=(x \cdot d) \bmod 127$ (с каким-нибудь удобным нечётным $d$) или любой другой. Распаковка по табличке длиной 128 элементов по 10 бит.
Проще всего именно что табличка 1024 элементов по 7 бит (или 8), заполняемая обработкой каждого 10-битного кода, плюс одна 7-битная переменная-счётчик заполненности и она же 7-битный индекс каждого 10-битного ключа. Распаковка так же.
Или можно иметь битовый вектор длиной 1024 бита (128 байт), в котором хранить встретился ли такой код. После обработки всех входных чисел в векторе останутся лишь 120 установленных битов, которые легко перенумеровать с 1 по 120. Распаковка или как выше, или по ровно такому же вектору 1024 бита, по которому идти и считать единички пока счётчик не совпадёт с распаковываемым числом (медленно!).

[Missir]

Dmitriy40 в сообщении #1655016 писал(а):

можно применить хэш-функцию для сворачивания 10 бит в 7, например $H(x)=x \mod 127$ или $H(x)=(x \cdot d) \mod 127$ (

очень заманчиво, но пока не получается чтобы все числа были разные

[mihaild]

Missir в сообщении #1655000 писал(а):

да именно так

Тогда я не понимаю, в чем проблема.
В начале пишем 3 бита и их позиции (можно упихать еще в 9 бит). Дальше от каждого из интересующих байт пишем по 5 значащих бит.

[Dmitriy40]

Missir в сообщении #1655017 писал(а):

но пока не получается чтобы все числа были разные

Вероятно и не получится, у меня обычно коэффициент заполнения порядка 70%, остальное коллизии. Так что Вам надо увеличивать размер хэш-таблицы до ~200. И то от коллизий это не гарантирует.
Можно уменьшить число 127 до скажем 113 (или 101), коллизий станет чуточку больше, и все их сохранять начиная с последнего числа, 120 или лучше 127. Тоже вряд ли получится, но исключений должно стать меньше.
Ну и поиграться с $d$, вдруг удастся подобрать чтобы всё уместилось (все 7-битные числа разные).
Хотя я бы сделал на 1024-битовом векторе.

mihaild
Чел хочет закодировать 120 разных 10-битных чисел в 7 битов каждое (ведь $120<2^7$). Вы же предлагаете от каждого двухбайтного числа писать 5+5=10 битов, вообще без сжатия.
Т.е. у него не все 1024 (65536) чисел реально встречаются, а лишь их подмножество (заранее неизвестное) размером 120 штук. Вот и хочет их кодировать 7-ю битами.

[Missir]

Dmitriy40 в сообщении #1655019 писал(а):

Ну и поиграться с $d$, вдруг удастся подобрать чтобы всё уместилось.

нет, не получается, я перебрал все варианты до 3 млн. основание увеличивал до 200

[Dmitriy40]

Missir
Хэш-функций много разных, возьмите другую, не остаток от деления. Например младшие (или средние) 7 битов MD5, или CRC7, или ещё что угодно.
Но повторю, коэффициент заполнения $120/128=93.75\%$ очень высок, такую хэш-функцию можно искать годами. Тем более если эти 120 чисел заранее неизвестны.

-- 16.09.2024, 23:07 --

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

-- 16.09.2024, 23:15 --

А почему можете посчитать довольно сложную функцию (деление обычно не столь уж быстро), но не можете выделить 128 байтов под массив(ы)?
Можно обойтись 124 байтами для таблицы длиной 120 элементов по 10 битов плюс 4 номера где меняются старшие два бита, т.е. в таблице хранить только младшие 8 битов входного числа. Таблицу отсортировать по возрастанию и искать входное число в ней двоичным поиском, это всего максимум 7 обращений к ней (в кусок задаваемый старшими двумя битами входного числа).

[mihaild]

Dmitriy40 в сообщении #1655019 писал(а):

Чел хочет закодировать 120 разных 10-битных чисел в 7 битов каждое (ведь $120<2^7$)

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

В общем я всё еще не понимаю, в чем задача.

[Dmitriy40]

Судя по тому как уцепились за хэш-функции, 120 чисел заданы заранее и фиксированы. И вопрос лишь как 10(16)-битное число из известного фиксированного подмножества размером 120 штук из всех возможных превратить в 7-битное. Т.е. нужна функция выдающая уникальный код для каждого из 120 разных чисел по 10 (или 16, не суть) бит каждое.
На самом деле математики тут немного, тема скорее для CS.

[mihaild]

Я считаю, что эта часть CS на самом деле математика :)

Т.е. нам нужна функция $\{0, 1\}^{10} \to \{0, 1\}^7$, и значения которой на данном наборе из $120$ аргументов все разные? А зачем тогда все рассказы про 3 одинаковых бита?
Одна функция подходит максимум для $8^{120} \cdot C_{128}^{120}$ разных наборов, всего наборов $C_{1024}^{120}$, так что нужно чуть больше чем $2^{128}$ разных функций. Соответственно попытка сделать хеш-функцию параметризованную меньше чем 129 битами обречена на провал.