2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 00:11 


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

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 00:15 


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

-- 17.09.2024, 00:17 --

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

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 00:42 


14/01/11
3019
Missir в сообщении #1655033 писал(а):
Sender тут все уже поняли, что нужно

Позволю себе обратить ваше внимание на следующее сообщение:
mihaild в сообщении #1655023 писал(а):
В общем я всё еще не понимаю, в чем задача.

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 01:07 


15/12/22
181
Sender

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

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

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 01:23 
Заслуженный участник
Аватара пользователя


16/07/14
9090
Цюрих
Missir в сообщении #1655038 писал(а):
Также, участниками было предложено использовать хеш-функции, но как выяснилось, здесь это не работает.
Любая такая конструкция это и есть хеш-функция.

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

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

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 01:39 
Заслуженный участник


20/08/14
11687
Россия, Москва
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}$).

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 07:59 
Аватара пользователя


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

-- 17.09.2024, 08:03 --

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

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 08:58 
Заслуженный участник
Аватара пользователя


16/07/14
9090
Цюрих
Dmitriy40 в сообщении #1655040 писал(а):
Но всегда есть надежда наткнуться на подходящую функцию случайно
Вероятность того, что случайная функция с кодоменом из 7 бит подойдет - $2^{-139}$. Так что надежды нет.
Dmitriy40 в сообщении #1655040 писал(а):
Или можно подобрать (тоже почти случайно) пару-тройку таких функций, коллизии которых компенсируют друг друга
Это будет уже не 7 бит, а, скорее всего, больше 10.
Собственно стандартная конструкция с perfect hash function из двух линейных, где вторая разщная для разных значений первой, так устроена.
Dmitriy40 в сообщении #1655040 писал(а):
Но разбив её на две-три - найти уже легче
Вон статья выше, как такую построить, потратив $\approx 190$ бит. Но работать это будет медленно (хотя и за константу, конечно).

 Профиль  
                  
 
 Re: оптимальная перекодировка
Сообщение17.09.2024, 16:00 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group