Здравствуйте, cruse, Вы писали:
C>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт.
Развод! Сжатие будет только в десять раз!
16 * 100 == 1600, а не 160
C>Алгоритм сжатия: C> Файл разбивается на блоки по 160 байт, для каждого вычисляется хеш и помещается в выходной файл.
C>Алгоритм распаковки: C> Из файла читаются хеши и поиском в глобальной базе данных восстанавливаются блоки данных.
C>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма
Здравствуйте, cruse, Вы писали: C>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма
предлагаю разбивать на блоки по 1600 байт, чтобы действительно было сжатие в 100 раз. А еще лучше вообще не разбивать на блоки, зачем? тогда чем болье файл, тем лучше сжатие. любой файл в 16 байт и все.
Здравствуйте, IID, Вы писали:
IID>Здравствуйте, cruse, Вы писали:
C>>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт.
IID>Развод! Сжатие будет только в десять раз! IID>16 * 100 == 1600, а не 160
Здравствуйте, cruse, Вы писали:
C>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт.
C>Алгоритм сжатия: C> Файл разбивается на блоки по 160 байт, для каждого вычисляется хеш и помещается в выходной файл.
C>Алгоритм распаковки: C> Из файла читаются хеши и поиском в глобальной базе данных восстанавливаются блоки данных.
Лучше использовать бит чётности, будет выигрыш в степени сжатия дополнительно в 128 раз по сравнению с MD5 (1 бит против 128).
cruse wrote:
> Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей > всех комбинаций из 160 байт.
Давно такое есть, torrent называется, правда там SHA-хеш
Posted via RSDN NNTP Server 2.1 beta
но это не зря, хотя, может быть, невзначай
гÅрмония мира не знает границ — сейчас мы будем пить чай
Здравствуйте, cruse, Вы писали:
C>Конечно же однозначного соответствия нет, возможны коллизии. C>Но есть и положительный момент в статье, реализация может быть аппаратной!
О да!
Это безусловно победит коллизии!
Здравствуйте, cruse, Вы писали:
C>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт. C>Алгоритм сжатия: C> Файл разбивается на блоки по 160 байт, для каждого вычисляется хеш и помещается в выходной файл. C>Алгоритм распаковки: C> Из файла читаются хеши и поиском в глобальной базе данных восстанавливаются блоки данных. C>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма :)
Здравствуйте, cruse, Вы писали:
C>Конечно же однозначного соответствия нет, возможны коллизии.
C>Но есть и положительный момент в статье, реализация может быть аппаратной!
очуметь.
наша программа дает неверный результат, зато делает это мгновенно.
А еще лучше прочитайте что такое векторное квантования =)
В конце курса по теории информации любой студент который присутствовал на лекциях так и норовит написать подобный архиватор =))
Здравствуйте, cruse, Вы писали:
C>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт.
Коллега, вы не находите, что база в 256^160 * 16 ~= 333050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000000000000000 Терабайт, это несколько много?
I>Коллега, вы не находите, что база в 256^160 * 16 ~= 333050000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 I>0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 I>0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 I>000000000000000000000000000000000000000000000000000000000000000000000000 Терабайт, это несколько много?
А если записи в базу делать только по необходимости? Сжали один блок — получили запись. ))
Разве никто не помнит этого великолепного на мой взгляд анекдота?
Встречаются два программиста:
— Ты чего такой грустный?
— Да вот написал архиватор, который любой файл в 5 байт сжимает.
— Ну и?
— Сейчас над распаковщиком работаю...
Здравствуйте, TarasCo, Вы писали: TC>А если записи в базу делать только по необходимости? Сжали один блок — получили запись. ))
Тогда можно попытаться прикинуть, на сколько терабайт в день будет возрастать объем базы.
C>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт. C>Алгоритм сжатия: C> Файл разбивается на блоки по 160 байт, для каждого вычисляется хеш и помещается в выходной файл. C>Алгоритм распаковки: C> Из файла читаются хеши и поиском в глобальной базе данных восстанавливаются блоки данных. C>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма
А еще.. а еще. есть такое замечательное число ПИ. Замечательно оно потому что обладает св-ом трансцендентности. А это означает что само по себе оно содержит в себе все возможные комбинации цифр. Все симфонии моцарта во всех возможных кодировках, все библиотеки, ДНК всех людей... Вопрос лишь в том чтобы найти с какой цифры после запятой идет нужная последовательность, и в том чтобы вычислить число ПИ с такой точностью
Как много веселых ребят, и все делают велосипед...
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, cruse, Вы писали:
C>>Конечно же однозначного соответствия нет, возможны коллизии. C>>Но есть и положительный момент в статье, реализация может быть аппаратной! CC>О да! CC>Это безусловно победит коллизии!
Победить конечно не победит, но позволит обработать большее количество коллизий за единицу времени
Здравствуйте, cruse, Вы писали:
C>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт.
Ну, я на досуге, чисто для своего удовольствия и чтобы не забыть программирование, делаю нечто подобное.
Правда это не архиватор, но принцип работы похож.
Кстати, очень похоже, что firewall от Comodo использует такой же алгоритм для части своего функционала.
Здравствуйте, cruse, Вы писали:
C>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма
Вас уже опередили ) http://www.info-save.info/sert.php
не знаю, что там правда... но слежу за событиями )
+ Ваша реализация не предусматривает сжатие бинарных кодов )
А вообще принято, дай бог память, что качество проверяют в том числе и коэффициентом:
Изначальные объемы / ( Объем после сжатия + исполнимый код распаковщика )
По этому поводу ходит байка еще со времен фидо:
Где один из споривших написал "упаковщик", получив от оппонента исходный "текст" ("белый шум"... он плохо/практически не сжимается, т.к. в нем нет связанной информации). Тот собрал частотность исходника и разрезал исходный файл на части по символу наиболее часто встречающемуся в тексте (не включая его в итоговые куски) + написал сборщик, который эти куски последовательно склеивал, дописывая в конец каждого куска тот самый символ распила и выложил в обсуждение ))) Вроде как деньги в этом споре он и выиграл, но заключавший пари обвинил его в жульничестве и денег не отдал ) надо бы поискать в сети то событие )
C>>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма А>Вас уже опередили ) А>http://www.info-save.info/sert.php А>не знаю, что там правда... но слежу за событиями )
Не понял, а что по российскому законодательству не нужен ерализованный рабочий прототип алгоритма для получения патента? То есть я могу вот ща запатентовать антигравитацию?
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
O>Не понял, а что по российскому законодательству не нужен ерализованный рабочий прототип алгоритма для получения патента? То есть я могу вот ща запатентовать антигравитацию?
Помнится из института — в России алгоритмы не патентуются, патентуются программы. А на западе патентуются алгоритмы. Запомнил это потому как интересно получается — можешь использовать свободно любой западный алгоритм, только потом в ту страну лучше не ездить
Надеюсь не наврал.
Здравствуйте, ononim, Вы писали:
C>>>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма :) А>>Вас уже опередили ) [....] не знаю, что там правда... но слежу за событиями ) O>Не понял, а что по российскому законодательству не нужен ерализованный рабочий прототип алгоритма для получения патента? То есть я могу вот ща запатентовать антигравитацию?
Не знаю про патент точно, были под руками требования и шаблоны запросов (они стоят денег )))), но в целом там чистая бюрократия с публикацией части исходных кодов.
Но по ссылке заключение некой комиссии ) "показатель" )
Здравствуйте, Spiceman, Вы писали:
S>Помнится из института — в России алгоритмы не патентуются, патентуются программы. А на западе патентуются алгоритмы. Запомнил это потому как интересно получается — можешь использовать свободно любой западный алгоритм, только потом в ту страну лучше не ездить :) S>Надеюсь не наврал.
Наврал, я долго вспоминал пример... вот пример западного панента:
Здравствуйте, Альт, Вы писали:
А>Здравствуйте, Spiceman, Вы писали:
S>>Помнится из института — в России алгоритмы не патентуются, патентуются программы. А на западе патентуются алгоритмы. Запомнил это потому как интересно получается — можешь использовать свободно любой западный алгоритм, только потом в ту страну лучше не ездить S>>Надеюсь не наврал.
А>Наврал, я долго вспоминал пример... вот пример западного панента:
Так я ж не сказал, что на западе программы не патентуют. Я сказал, что у нас алгоритмы не патентуют
А>cdq А>xor eax, edx А>sub eax, edx
А>угадаете суть по патентованной реализации?
Здравствуйте, Альт, Вы писали:
А>Здравствуйте, Spiceman, Вы писали:
S>>Помнится из института — в России алгоритмы не патентуются, патентуются программы. А на западе патентуются алгоритмы. Запомнил это потому как интересно получается — можешь использовать свободно любой западный алгоритм, только потом в ту страну лучше не ездить S>>Надеюсь не наврал.
А>Наврал, я долго вспоминал пример... вот пример западного панента:
А>cdq А>xor eax, edx А>sub eax, edx
А>угадаете суть по патентованной реализации?
на входе в eax — число, на выходе в eax — его модуль
интересно придумано
Здравствуйте, ononim, Вы писали:
O>А еще.. а еще. есть такое замечательное число ПИ. Замечательно оно потому что обладает св-ом трансцендентности. А это означает что само по себе оно содержит в себе все возможные комбинации цифр.
Откуда такая информация?
Здравствуйте, Demon, Вы писали:
D>Здравствуйте, ononim, Вы писали:
O>>А еще.. а еще. есть такое замечательное число ПИ. Замечательно оно потому что обладает св-ом трансцендентности. А это означает что само по себе оно содержит в себе все возможные комбинации цифр. D>Откуда такая информация?
Дык, очевидно же.
Есть поистене чудесное доказательство этого утверждения, но ширина поля этого сообшения слишком мала для него.
С другой стороны, чтобы убедиться в этом, достаточно посчитать число с нужной точностью.
К этому моменту у меня внутри 0.5, 0.7, 0.33 (с) НС
Здравствуйте, WPooh, Вы писали:
O>>>А еще.. а еще. есть такое замечательное число ПИ. Замечательно оно потому что обладает св-ом трансцендентности. А это означает что само по себе оно содержит в себе все возможные комбинации цифр. D>>Откуда такая информация? WP>Дык, очевидно же. WP>Есть поистене чудесное доказательство этого утверждения, но ширина поля этого сообшения слишком мала для него.
Доказательство чего? Что число пи трансцендентное? Ну это еще в 1882 году доказали.
А вот содержание в трансцендентных числах всевозможных комбинаций пока является гипотезой, на сколько я помню.
В итоге после многократного хеширования хешированного хеша получаем 1 байт
Здравствуйте, igna, Вы писали:
I>Здравствуйте, IID, Вы писали:
IID>>Развод! Сжатие будет только в десять раз!
I>Применяем тот же алгоритм повторно, вот и все.
Здравствуйте, WPooh, Вы писали:
O>>>А еще.. а еще. есть такое замечательное число ПИ. Замечательно оно потому что обладает св-ом трансцендентности. А это означает что само по себе оно содержит в себе все возможные комбинации цифр. D>>Откуда такая информация? WP>Дык, очевидно же.
WP>Есть поистене чудесное доказательство этого утверждения, но ширина поля этого сообшения слишком мала для него.
WP>С другой стороны, чтобы убедиться в этом, достаточно посчитать число с нужной точностью.
Есть поистине чудесное доказательство отрицания этого утверждения
Допустим начиная с какого-то знака повторяется и само число Пи, в той части что до этого знака уже пройдена, тогда на втором периоде этой дроби число Пи станет периодично повторять эту последовательность
следовательно оно станет рациональным
Здравствуйте, mister-AK, Вы писали:
MA>Здравствуйте, WPooh, Вы писали:
O>>>>А еще.. а еще. есть такое замечательное число ПИ. Замечательно оно потому что обладает св-ом трансцендентности. А это означает что само по себе оно содержит в себе все возможные комбинации цифр. D>>>Откуда такая информация? WP>>Дык, очевидно же.
WP>>Есть поистене чудесное доказательство этого утверждения, но ширина поля этого сообшения слишком мала для него.
WP>>С другой стороны, чтобы убедиться в этом, достаточно посчитать число с нужной точностью.
MA>Есть поистине чудесное доказательство отрицания этого утверждения
MA>Допустим начиная с какого-то знака повторяется и само число Пи, в той части что до этого знака уже пройдена, тогда на втором периоде этой дроби число Пи станет периодично повторять эту последовательность MA>следовательно оно станет рациональным
Очевидно, что имеются ввиду все конечные комбинации цифр, поэтому этот контрпример ни о чём не говорит.
Здравствуйте, cvetkov, Вы писали:
C>Здравствуйте, cruse, Вы писали:
C>>Конечно же однозначного соответствия нет, возможны коллизии.
C>>Но есть и положительный момент в статье, реализация может быть аппаратной! C>очуметь. C>наша программа дает неверный результат, зато делает это мгновенно.
Здравствуйте, Константин, Вы писали:
К>Здравствуйте, cruse, Вы писали:
C>>Хеш MD5 занимает 16 байт. Делаем глобальную базу данных в интернет хешей всех комбинаций из 160 байт.
C>>Алгоритм сжатия: C>> Файл разбивается на блоки по 160 байт, для каждого вычисляется хеш и помещается в выходной файл.
C>>Алгоритм распаковки: C>> Из файла читаются хеши и поиском в глобальной базе данных восстанавливаются блоки данных.
К>Лучше использовать бит чётности, будет выигрыш в степени сжатия дополнительно в 128 раз по сравнению с MD5 (1 бит против 128).
На самом деле идея не лишена здравого смысла:
Если сделать веб сервис, который будет по содержимому файла возвращать его хеш (реально кэшируя содержимое), а по хешу возвращать содержимое (беря его из кэша), то всё получится — ведь реальное количество различных существующих файлов конечно!
тогда передавать файл можно будет путем передачи только его хэша
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, TarasCo, Вы писали: TC>>А если записи в базу делать только по необходимости? Сжали один блок — получили запись. )) MC>Тогда можно попытаться прикинуть, на сколько терабайт в день будет возрастать объем базы.
Ну и что с того? База данных индексированного интернета в Live Search растет изо дня в день...
Здравствуйте, cruse, Вы писали:
C>Прошу высказать ваше мнение о достоинствах, недостатках и возможных улучшениях алгоритма
Поздравляю, ты изобрёл колесо.
Эта идея использовалась в файловой системе Venti ( http://en.wikipedia.org/wiki/Venti ) в 2002-м году (только там SHA-1 хэши), а потом в git'е.
Только вместо MD5 и SHA-1 лучше использовать что-нибудь типа SHA-256. Вероятность коллизии среди разумного числа блоков будет чрезвычайно мала, так что на практике ей можно пренебречь (при использовании 256-битного хэша и 4.8*10^35 объектов вероятность будет один из миллиона).
Здравствуйте, Cyberax, Вы писали:
C>Только вместо MD5 и SHA-1 лучше использовать что-нибудь типа SHA-256. Вероятность коллизии среди разумного числа блоков будет чрезвычайно мала, так что на практике ей можно пренебречь (при использовании 256-битного хэша и 4.8*10^35 объектов вероятность будет один из миллиона).
Можно поступить ещё проще: использовать не один метод получения хэша, а два и больше.
A>На самом деле идея не лишена здравого смысла: A>Если сделать веб сервис, который будет по содержимому файла возвращать его хеш (реально кэшируя содержимое), а по хешу возвращать содержимое (беря его из кэша), то всё получится — ведь реальное количество различных существующих файлов конечно!
Я тебе больше скажу — такое уже реализовано, файлообменник называется.
Здравствуйте, Real 3L0, Вы писали:
C>>Только вместо MD5 и SHA-1 лучше использовать что-нибудь типа SHA-256. Вероятность коллизии среди разумного числа блоков будет чрезвычайно мала, так что на практике ей можно пренебречь (при использовании 256-битного хэша и 4.8*10^35 объектов вероятность будет один из миллиона). R3>Можно поступить ещё проще: использовать не один метод получения хэша, а два и больше.
Это ничего особого не меняет, просто увеличивает эффективную длину хэша.
Здравствуйте, Альт, Вы писали:
А>Где один из споривших написал "упаковщик", получив от оппонента исходный "текст" ("белый шум"... он плохо/практически не сжимается, т.к. в нем нет связанной информации). Тот собрал частотность исходника и разрезал исходный файл на части по символу наиболее часто встречающемуся в тексте (не включая его в итоговые куски) + написал сборщик, который эти куски последовательно склеивал, дописывая в конец каждого куска тот самый символ распила и выложил в обсуждение ))) Вроде как деньги в этом споре он и выиграл, но заключавший пари обвинил его в жульничестве и денег не отдал ) надо бы поискать в сети то событие )
это не байка. был такой compression challenge. платишь 100 баксов, если сжимаешь файл хотя бы на 100 байт — получаешь 5000. это кстати было сделано чтобы не объяснять каждому идиоту, что сжать белый шум нельзя — пусть платит 100 баксов за науку и убеждается сам
и один умник разрезал файл на 100 там или 200 частей по какому-то символу, и прислал bat-файл, который из этих файлов исходный собирает. т.е. фактически переложил информацию в файловую систему. но поскольку в условиях конкурса никаких ограничений на число файлов предусмотрено не было — он честно заработал свои 5000. но ему их так и не отдали, хотя предложили вернуть сотню
S>>Помнится из института — в России алгоритмы не патентуются, патентуются программы. А на западе патентуются алгоритмы. Запомнил это потому как интересно получается — можешь использовать свободно любой западный алгоритм, только потом в ту страну лучше не ездить S>>Надеюсь не наврал. А>Наврал, я долго вспоминал пример... вот пример западного панента: А>cdq А>xor eax, edx А>sub eax, edx А>угадаете суть по патентованной реализации?
Я подавал на патент US (через стороннего юриста нашей фирмы конечно). Так вот выглядело это не как 3 строчки кода на асме, а подробное описание идеи, алгоритма, куски псевдокода реализующие его, и, обязательно — скомпилированный работающий прототип.
Потому запатентовать идею супер архиватора без оно самого — не выйдет.
Как много веселых ребят, и все делают велосипед...
Здравствуйте, ononim, Вы писали:
O>Я подавал на патент US (через стороннего юриста нашей фирмы конечно). Так вот выглядело это не как 3 строчки кода на асме, а подробное описание идеи, алгоритма, куски псевдокода реализующие его, и, обязательно — скомпилированный работающий прототип. O>Потому запатентовать идею супер архиватора без оно самого — не выйдет.
Ещё как выйдет. Патентование НЕ ТРЕБУЕТ наличие работающего образца.
Здравствуйте, ononim, Вы писали:
O>Я подавал на патент US (через стороннего юриста нашей фирмы конечно). Так вот выглядело это не как 3 строчки кода на асме, а подробное описание идеи, алгоритма, куски псевдокода реализующие его, и, обязательно — скомпилированный работающий прототип. O>Потому запатентовать идею супер архиватора без оно самого — не выйдет.
насколько я помню, патентовали. в патенте было много псевдонаучной белиберды, или даже чего-то научного, но не по делу. а ещё хитрозадые ...израильтяне запатентовали алгоритм paq
Здравствуйте, Aleksey Katorgin, Вы писали:
AK>Предложен для сжатия картинок моим другом, когда мы учились с нем в шестом классе. Разработан для "Спектрумов".
то, что предложен — не сомневаюсь....
но, вот, разработан ли ?
AK>
Берем экранную память, выстраиваем в одно большое двоичное число и переводим его в плавающую форму. Вуаля! Теперь наш экран сжат до пяти байт.
: 4000654 
