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

[Sender]

Боюсь, пока не поймём, зачем эта перекодировка понадобилась, гадать по поводу правильной постановки можно долго. Возможно, у ТС есть некий специфический алгоритм, который принимает на вход произвольную конечную последовательность бит, и ТС хочет максимально ужать в размере входные данные.

[Missir]

хотелось бы ещё услышать что нибудь про булевы функции, если бы не их громоздкость, то решение само по себе не плохое

-- 17.09.2024, 00:17 --

Sender тут все уже поняли, что нужно

[Sender]

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

Sender тут все уже поняли, что нужно

Позволю себе обратить ваше внимание на следующее сообщение:

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

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

[Missir]

Sender

В общем, если строго, то нужно преобразовать 10 битное число в 7 битное, так, чтобы его можно было восстановить обратно. Это возможно потому, что в данных встречаются только 120 чисел из 1024 возможных, и эти числа известны.
Как справедливо заметили, можно составить массив из 1024 чисел и записать нужные коды по соответствующим адресам, но это слишком избыточно.
Можно заполнить массив из 120 элементов с отсортированными 10-битными кодами, и искать в нём полученный код. Индекс элемента и будет искомым кодом. Но тут нужно выполнить несколько доступов к массиву. Можно искать бинарным поиском, но вероятности получаемых символов сильно отличаются, и не соответствуют порядку сортировки. Почти всегда потребуется 7 обращений к массиву. Можно расположить в порядке уменьшения вероятности и проверять подряд. Тогда, в большинстве случаев потребуется только 2-4 обращения, но в редких случаях оно может увеличиться до 120. Что лучше пока не ясно. В обоих вариантах есть большой плюс - можно выявить недопустимые символы, после вычислении укороченного кода этого сделать не получится.

Собственно вариант, который я рассматриваю: просто вычислить 7 битное число по 10 битному. Это можно решить с помощью булевых функций, т.к. имеется таблица истинности. Но нужно какое то ПО, в ручную получается не очень.
Также, участниками было предложено использовать хеш-функции, но как выяснилось, здесь это не работает.

[mihaild]

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

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

Любая такая конструкция это и есть хеш-функция.

Известна конструкция совершенной хеш-функции, требующей $1.56$ бит на ключ https://arxiv.org/abs/1910.06416.

Но я подозреваю что любая штука на практике (кроме может быть совсем экзотического железа) будет работать медленнее чем массив из 1024 чисел. Чем он не устраивает, кроме того что "некрасиво"?

[Dmitriy40]

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

Т.е. нам нужна функция $\{0, 1\}^{10} \to \{0, 1\}^7$, и значения которой на данном наборе из $120$ аргументов все разные?

Да.

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

А зачем тогда все рассказы про 3 одинаковых бита?

Просто человек мыслит битами и байтами (как и я), а не математическими абстракциями. И числа кодирует двумя байтами, т.е. реально ему надо $\{0,1\}^{16}\to\{0,1\}^7$. Но он точно знает что какие-то 6 битов из 16 в каждом числе фиксированы и всегда одинаковы для интересующего его набора чисел, потому 16 можно уменьшить до 10.

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

Соответственно попытка сделать хеш-функцию параметризованную меньше чем 129 битами обречена на провал.

Это если её вычислять по заданному набору чисел. Но всегда есть надежда наткнуться на подходящую функцию случайно (взяв например младшие нечётные биты из MD5 от входного числа). Или можно подобрать (тоже почти случайно) пару-тройку таких функций, коллизии которых компенсируют друг друга. В конце концов даже если одна функция обрабатывает всего 70% входных чисел (как в общем у меня получалось), т.е. оставляет треть ($3^{-1}$) не обработанными, то составив 5 разных функций подряд снизим вероятность коллизии до $(3^{-1})^5=3^{-5}<1/120$, т.е. коллизии могут быть, но их вероятность невелика. Но функции нужны (линейно) независимые. Я не вполне уверен что остаток от деления на взаимно простые числа подходит и уж тем более что уложится суммарно в 7 бит.
Мне потому и кажется что тут больше вопрос кодирования чем математических функций, что можно поискать как поэффективнее кодировать числа, может они как-то похожи друг на друга (вдруг они все кратны 5 или 13, или для этого надо битовую запись перевернуть) (или например можно несложным преобразованием их к такому виду привести, скажем переходя к разностям или xor или реверсом битов или разделением на чётные и нечётные биты или более сложной функции) и тогда можно придумать более эффективный алгоритм преобразования, не перебирая все эти $2^{129}$ вариантов. Но надо знать сами числа и искать чем они похожи.

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

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

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

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

Можно искать бинарным поиском, но вероятности получаемых символов сильно отличаются, и не соответствуют порядку сортировки. Почти всегда потребуется 7 обращений к массиву.

Можно в массиве хранить лишь младшие биты входных чисел, а выделять нужный кусок в основном массиве по второму массиву, индексом в котором будут оставшиеся старшие биты. Тогда 4 старших бита (табличка из 16 байтов) дают один из 16 кусков внутри основной 120 байтовой таблички в среднем длиной в 15 элементов или 3-5 обращения (5 максимум, почти в половине случаев хватит 3 или 4), всего 4-5 обращений к двум массивам. Если куски получаются сильно разного размера, то предварительно перемешать входные числа простой хэш-функцией (типа $(x \cdot d) \bmod 2^{10}$).

[B@R5uk]

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

-- 17.09.2024, 08:03 --

А ещё лучше код генератора тестовых примеров, который вы будете использовать для отладки своего "архиватора", когда перейдёте от теории к написанию программы. Таким образом у всех отпадут вопросы касательно того, с чем именно вы хотите работать.

[mihaild]

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

Но всегда есть надежда наткнуться на подходящую функцию случайно

Вероятность того, что случайная функция с кодоменом из 7 бит подойдет - $2^{-139}$. Так что надежды нет.

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

Или можно подобрать (тоже почти случайно) пару-тройку таких функций, коллизии которых компенсируют друг друга

Это будет уже не 7 бит, а, скорее всего, больше 10.
Собственно стандартная конструкция с perfect hash function из двух линейных, где вторая разщная для разных значений первой, так устроена.

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

Но разбив её на две-три - найти уже легче

Вон статья выше, как такую построить, потратив $\approx 190$ бит. Но работать это будет медленно (хотя и за константу, конечно).

[Missir]

Пришел к компромиссу, первые 5 бит - адрес вспомогательного 32 элементного массива, тут избыточность совсем небольшая.
В этом массиве хранятся позиции основного 120 элементного массива, в котором содержатся все 5 битные остатки в порядке вероятности встречаемости.
Получается 1 обращение к вспомогательному массиву и поиск по основному массиву, который требует максимум 8 обращений, но чаще всего 2-3 обращения. При этом сохраняется возможность обнаружения недопустимых символов.