ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Компактная нотация бинарной записи числа
25 сообщений из 83, страница 1 из 4
  1  все
Компактная нотация бинарной записи числа
    #39580885
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Пусть есть задача в начале некоторого большого файла произвольного содержания записывать одно целое число, тоже произвольное.

Проблема в том, что за записью этого числа (по условию задачи) идут какие-то не зависящие от него биты. Как указать, где оканчивается "тело" числа?

Очевидно, возможны разные нотации записи этого числа. Например, если бинарная запись этого числа состоит из К битов, сначала ставить К-1 единиц, потом "0", потом само число. То есть для числа 255 получаем вид: "1111111011111111тело_файла..."

Возможна ли более компактная нотация?
...
Рейтинг: 0 / 0
09.01.2018, 11:21
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580908
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Я так понимаю, что число не ограничено сверху? но какая-то вменяемая граница количества битов в нём есть? 4kkk хватит? Выдели первые 4 байта на количество битов своего числа, потом само число, потом независимый хвост. 4Г мало? выдели 8 байт всё равно столько на диск не поместится...
...
Рейтинг: 0 / 0
09.01.2018, 11:40
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580912
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
M бит размер числа, К бит число, тело.

Размер M фиксированный, т.е. выбрать с запасом чтобы все возможные К входили.
...
Рейтинг: 0 / 0
09.01.2018, 11:44
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580913
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Akina,

запись числа 1 займёт 8 байт + 1 бит? Это компактно?
...
Рейтинг: 0 / 0
09.01.2018, 11:44
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580931
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSзапись числа 1 займёт 8 байт + 1 бит? Это компактно?
Можно еще размер размера писать, для 2^64 потребуется 6 бит
т.е. для числа 1 запись такая:
Код: sql
1.
000001 1 1


всего 1 байт
...
Рейтинг: 0 / 0
09.01.2018, 12:00
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580936
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Иван FXSВозможна ли более компактная нотация? Цель выбрать надо: компактизация в среднем или каждый раз?
Может "оптимальное кодирование" что-то подскажет (подразумевается минимизация с целью передачи по каналам связи.)
...
Рейтинг: 0 / 0
09.01.2018, 12:02
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580943
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima TМожно еще размер размера писать, для 2^64 потребуется 6 бит
т.е. для числа 1 запись такая:
Код: sql
1.
000001 1 1


всего 1 байт
А если размер размера размера добавить, то 6 бит хватит
Код: sql
1.
001 1 1 1
...
Рейтинг: 0 / 0
09.01.2018, 12:06
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580947
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Dima T,

да, размер размера, пожалуй. То есть нужно как-то в более конкретных условиях задачи найти/обосновать выбор -- ограничиться ли размером_размера, или нужно даже с размера_размера_размера начинать ...
...
Рейтинг: 0 / 0
09.01.2018, 12:09
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39580956
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Иван FXSDima T,

да, размер размера, пожалуй. То есть нужно как-то в более конкретных условиях задачи найти/обосновать выбор -- ограничиться ли размером_размера, или нужно даже с размера_размера_размера начинать ...
Для записи числа размером 2^64 бит потребуется 2 млн. террабайт. Т.е. можно смело предположить что писать больше 2^64 точно не потребуется, поэтому достаточно варианта с размером размера 21089437 . Про "размер размера размера" шутка была.
...
Рейтинг: 0 / 0
09.01.2018, 12:18
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581038
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXSDima T,

да, размер размера, пожалуй. То есть нужно как-то в более конкретных условиях задачи найти/обосновать выбор -- ограничиться ли размером_размера, или нужно даже с размера_размера_размера начинать ...
Посмотри Код Левенштейна.
...
Рейтинг: 0 / 0
09.01.2018, 13:47
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581368
Фотография ptr128
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ptr128
Участник
Иван FXS,

Можно воспользоваться следующей логикой: для самого числа используем 7 бит из 8 каждого байта. Последний байт имеет первым битом 0, остальные байты - 1.
...
Рейтинг: 0 / 0
09.01.2018, 23:38
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В BCD-арифметике можно сохранять. Быстро парсится в десятичную.

В системе Фибоначчи можно хранить. Уверен что этот вариант проще чем Левенштейн. Хотя
возможно менее компактный на больших значениях.

Да мало-ли...
...
Рейтинг: 0 / 0
10.01.2018, 00:16
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581377
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Код Левенштейна в Википекдии как-то муторно описан, а другое описание я искать поленился.
...
Рейтинг: 0 / 0
10.01.2018, 00:26
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581379
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Разумеется не надо тебе его реализовывать. Надо найти готовую реализацию.
А кодить свою - это действительно муторно. Особенно в части тестирования. И поиска багов
уже в реализации под разные платформы. Полюбому что-то вылезет пузом.
Толи сдвиг (>>) толи битовые операции толи ХЗ что.

Ты кстати зачем своё кодишь? Спортивный интерес?
...
Рейтинг: 0 / 0
10.01.2018, 00:32
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581382
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
Реально размышляю про архиватор. По-дилетантски, конечно.
...
Рейтинг: 0 / 0
10.01.2018, 00:41
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581388
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Иван FXS, полезная тема. Особенно когда свои структуры данных создаешь.

Некоторое время назад я предложил форуму написать утилиту для поиска
уникальных строк в большом текстовом файле. И ты не поверишь, сколько
идей было. И Диме - спасибо. И даже сердитый Зяма отметился.
Но вот в чем штука. Любая хорошая идея требовала тщательно
продумать как в памяти распределить структуры данных. Биткарты там..
хеш-таблички... деревья. Найти золотую пропорцию. А там еще столько
технических нюансов - мама не горюй. И строки... и поиск и алгоритмизация
и оптимизация. Вобщем у меня от этой задачи так голова разболелась
что я даже ее отложил на годик. И хотя свои собственные решения
для себя - очевидны как божий день - но когда занимашеся перфекционизмом
то эти решения тухнут так и не выйде в альфа версию. И ты смотришь
на них такой и думаешь... а задлянахрена вообще это? Так - то..
...
Рейтинг: 0 / 0
10.01.2018, 00:50
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581574
Фотография ptr128
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ptr128
Участник
maytonПосмотри Код Левенштейна.
Во-первых, Омега-код Элиаса на один бит экономичней.
Во-вторых, оба кода дают экономию для чисел меньше 16, и перестают быть экономичными для 16 и более.
То есть, если преобладают числа от 1 до 16, то битовое кодирование оправдано. Если нет, эффективней кодировать байтами или иным размером слова.
...
Рейтинг: 0 / 0
10.01.2018, 11:10
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581636
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
ptr128,

вопрос не в кодировании самом по себе, а в том ЕЩЁ, чтобы отделить запись числа от следующих непосредственно за ней произвольных битов.
...
Рейтинг: 0 / 0
10.01.2018, 12:08
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581663
Фотография ptr128
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ptr128
Участник
Иван FXSptr128,

вопрос не в кодировании самом по себе, а в том ЕЩЁ, чтобы отделить запись числа от следующих непосредственно за ней произвольных битов.
Это я понимаю, но в чем проблема, если кодирование не битовое, а по словам?
То есть длина кода всегда кратна N бит, а сам код позволяет определить количество слов по N бит.
Даже если слово у нас 8 бит (байт), то совсем не обязательно выравнивать его на границу байта в файле.
...
Рейтинг: 0 / 0
10.01.2018, 12:44
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581803
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
Иван FXSПусть есть задача в начале некоторого большого файла произвольного содержания записывать одно целое число, тоже произвольное.

Проблема в том, что за записью этого числа (по условию задачи) идут какие-то не зависящие от него биты. Как указать, где оканчивается "тело" числа?

Очевидно, возможны разные нотации записи этого числа. Например, если бинарная запись этого числа состоит из К битов, сначала ставить К-1 единиц, потом "0", потом само число. То есть для числа 255 получаем вид: "1111111011111111тело_файла..."

Возможна ли более компактная нотация?тут снова можно обратиться к Шеннону, который все это обдумал еще в 1945 году :)
...
Рейтинг: 0 / 0
10.01.2018, 15:27
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581809
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Иван FXSвопрос не в кодировании самом по себе, а в том ЕЩЁ, чтобы отделить запись числа от следующих непосредственно за ней произвольных битов. В теори кодирования это свойство называется префиксностью. Необязательно префикс в программистском смысле. Есть срогое определение, не помню только. В пересказе - примерно то самое, что требуется.
...
Рейтинг: 0 / 0
10.01.2018, 15:34
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581818
Иван FXS
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иван FXS
Участник
"Префиксность" -- это про все подстроки строки. А здесь - только в одном месте, в начале строки.
...
Рейтинг: 0 / 0
10.01.2018, 15:41
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39581919
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
А вот и нет. Это относится к методу кодирования (строке, закодированной метдом). Я подразумевал, что заголовок строки и собственно строка "закодированы" разными методами.
...
Рейтинг: 0 / 0
10.01.2018, 17:16
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39582120
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ptr128maytonПосмотри Код Левенштейна.
Во-первых, Омега-код Элиаса на один бит экономичней.
Во-вторых, оба кода дают экономию для чисел меньше 16, и перестают быть экономичными для 16 и более.
То есть, если преобладают числа от 1 до 16, то битовое кодирование оправдано. Если нет, эффективней кодировать байтами или иным размером слова.
Во первых я ничуть не против кодов Элиаса.

Во вторых во втором вашем тезисе есть заявление о том что "эффективней кодировать байтами". Это странно.
Вы фактически опровергли работы Левенштейна и Элиаса. Чтобы что-то кодировать байтами или иным размером
слова вы должны вернуться к началу и определиться с диапазоном. А поскольку автор еще не определился
с диапазоном - то спорить не о чем. Если вы решили кодировать "байтами" то вам все равно необходимо
где-то хранить длину байтов и мы неизбежно приходим к префиксным или унарным или любым другим способам
кодирования.
...
Рейтинг: 0 / 0
10.01.2018, 22:56
| Ответить | Цитировать | Написать  
Компактная нотация бинарной записи числа
    #39582126
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
S.G.тут снова можно обратиться к Шеннону, который все это обдумал еще в 1945 году :)
Работы Шеннона относились к проблемам и вызовам которые стояли в середине 20-го века.
Шеннон оперировал понятием "символа". Это понятие возникло задолго до байта или бита.
Символ - это единица информации в телеграфе. В телексе. И в прочих простых устройствах
связи которые работали по аналаговым каналам.

Нисколько не умаляя работ этого замечательного инженера я скажу что он жил в своё
время и писал про своё. И актуальность и применимость его исследований к современным
архиваторам - весьма ограничена. Так-же как и работы Дональда Кнута для современного
веб-разработчика. Большая часть материала - не нужна.
...
Рейтинг: 0 / 0
10.01.2018, 23:06
| Ответить | Цитировать | Написать  
25 сообщений из 83, страница 1 из 4
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Компактная нотация бинарной записи числа
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]