?

Log in

3.14159265... - Книга бревна [entries|archive|friends|userinfo]
Книга бревна

[ картинки | галерея ]

3.14159265... [Aug. 13th, 2013|09:21 am]
Книга бревна
[dow |15419.68]

Разработана файловая система со 100% сжатием - πfs. Принцип работы прост, как и всё гениальное. Известно, что число π обладает тем свойством, что какую бы последовательность цифр вы ни придумали, она обязательно найдётся в числе π на какой-нибудь позиции. Далее автор обратил внимание, что любой файл есть всего лишь последовательность битов. Т.е. любой файл когда либо созданый человечеством уже присутствует в числе π, равно как и все файлы которые создать ещё только предстоит.

Таким образом, чтобы закодировать содержимое любого файла нужно всего два числа - номер позиции с которой файл начинается в π, и длина файла. Файловая система основанная на π распространяется свободно, исходный код выложен на GitHub.

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

Comments:
[User Picture]From: ogn_slon
2013-08-13 01:42 pm (UTC)
По-моему, аффтар алгоритма πfs сильно усложняет дело.

Всё проще: каждый файл как таковой являет собой некое уникальное число -- вот это число и является искомым кодом файла. Тем самым мы приходим к еще более удивительному алгоритму сжатия, ибо он, в дополнение к свойству стопроцентности сжатия, обладает еще и свойством самокодировки.

Зачем автору πfs понадобилось чило пи (нормальность которого, к тому же, никем не доказана) -- ума не приложу!
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-13 01:53 pm (UTC)
Да, у вас вышло ещё проще. Но давайте всё же отдадим должное автору πfs - он был первопроходцем. До него создание систем со 100% сжатием представлялось вообще невозможным.

Теперь же на заложенном им фундаменте можно строить более эффективные системы, например предложенную вами.
(Reply) (Parent) (Thread)
[User Picture]From: ogn_slon
2013-08-13 02:05 pm (UTC)
OK, приоритет первопроходца -- дело святое. Снимаю перед ним шляпу!
(Reply) (Parent) (Thread)
From: tambov_wolf
2013-08-13 03:08 pm (UTC)
каждый файл как таковой являет собой некое уникальное число

Это утверждение ложно. Например:
0х01
0х0001
Число то же самое, файлы - разные

Edited at 2013-08-13 03:08 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: ogn_slon
2013-08-13 06:04 pm (UTC)
Да, Вы правы -- надо единичку спереди приписывать, чтобы решить проблему лидирующих нулей.
(Reply) (Parent) (Thread)
[User Picture]From: maz_d
2013-08-13 05:11 pm (UTC)
/Всё проще: каждый файл как таковой являет собой некое уникальное число/

а каким образом тут достигается сжатие?
(Reply) (Parent) (Thread)
[User Picture]From: ogn_slon
2013-08-13 06:19 pm (UTC)
Никаким -- сжатие не достигается, если серьезно. Мой коммент -- это прикол в ответ на прикольный же способ "сжатия", описанный в самом посте. ;)
(Reply) (Parent) (Thread)
From: glukanat
2013-08-13 01:45 pm (UTC)
Использование файловой системы само по себе вполне законно. Нужно лишь дополнить закон о недрах. Ведь что есть n - нечто во всемирной строчке. Застолби заявку и потребуй чтобы никто больше на твою собственность не покушался. Желающие могут искать другое n и считать что у них - подлинник
(Reply) (Thread)
[User Picture]From: Look4job [ya.ru]
2013-08-13 01:46 pm (UTC)
Если число π содержит в себе цифровые копии всех книг, фильмов, звуковых дорожек в т.ч. и тех, что попадут под защиту только в будущем, то можно больше вообще ничего не писать, не снимать и не сочинять, а заняться вместо этого расшифровкой числа Пи.
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-13 02:05 pm (UTC)
Воистину так. Мог ли Борхес дерзнуть помыслить, что Вавилонская библиотека выйдет на цифровом носителе.
(Reply) (Parent) (Thread)
[User Picture]From: gamak57
2013-08-13 01:56 pm (UTC)
Ничего такого про пи неизвестно, как математик скажу.
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-13 02:18 pm (UTC)
Вы имеете ввиду, что нормальность π не доказана? Но программирование инженерная дисципина. Мы не можем ждать пока математики формально докажут, что P≠NP. Мы уже сегодня строим системы с использованием этого факта.
(Reply) (Parent) (Thread)
[User Picture]From: gamak57
2013-08-13 02:37 pm (UTC)
нормальность - даже более сильное свойство (оно означает, что любая последовательность из n цифр встречается с вероятностью 1/10^n). Не доказано даже, что в pi бесконечно много нулей или любых других цифр.
(Reply) (Parent) (Thread)
[User Picture]From: fat_yankey
2013-08-13 04:54 pm (UTC)
> Не доказано даже, что в pi бесконечно много нулей или любых других цифр.

Хм... По-моему это следует из иррациональности. Ну по крайней мере для двоичной записи. Если, скажем, в записи pi у нас конечное число единиц, то начиная с какой-то позиции у нас пойдут одни нули. Но тогда pi - рационально.

Наверное где-то тут дырка, но выглядит убедительно.
(Reply) (Parent) (Thread)
[User Picture]From: gamak57
2013-08-13 05:27 pm (UTC)
Для двоичной записи рассуждение верное. Но для десятичной оно не проходит, я это имел ввиду.
(Reply) (Parent) (Thread)
[User Picture]From: anderson_mike
2013-08-14 12:40 am (UTC)
Так нам-то нужна именно двоичная!
(Reply) (Parent) (Thread)
[User Picture]From: ogn_slon
2013-08-13 06:39 pm (UTC)
> Мы не можем ждать пока математики формально докажут, что P≠NP.

Кстати, про гипотетическое доказательство обратного (что P=NP) не так давно сняли триллер. Я, правда, пока не посмотрел, но, наверное, прикольный...
(Reply) (Parent) (Thread)
[User Picture]From: gamak57
2013-08-13 01:59 pm (UTC)
Предлагаю более простое число:
1234567891011121314151617...
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-13 02:18 pm (UTC)
Простое ли это число?
(Reply) (Parent) (Thread)
[User Picture]From: gamak57
2013-08-13 02:39 pm (UTC)
как минимум, для него доказана нормальность)
(Reply) (Parent) (Thread)
[User Picture]From: petrazmus
2013-08-13 02:24 pm (UTC)
Число гугол получается превышено?:-)
(Reply) (Thread)
From: schaban
2013-08-13 02:48 pm (UTC)
это не сжатие, это поиск
(Reply) (Thread)
[User Picture]From: declen
2013-08-13 03:06 pm (UTC)
Во первых: 265
Во вторых: "Известно, что число π обладает тем свойством, что какую бы последовательность цифр вы ни придумали, она обязательно найдётся в числе π на какой-нибудь позиции." - это шутка?
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-13 05:47 pm (UTC)
> Во первых: 265

Интернет как пи - что бы не подумал, там уже есть.

Однако, в pifs голая теория, которую не использовали ни для чего кроме матерщины, поставлена на службу людям. Горжусь своей профессией.

Edited at 2013-08-13 06:07 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: mechanician
2013-08-13 03:13 pm (UTC)
Подозреваю, что для хранения номера цифры числа пи, с которой начинается файл, может потребоваться число разрядности, превышающей длину исходного файла. :)
(Reply) (Thread)
[User Picture]From: sdvsamara
2013-08-13 03:29 pm (UTC)
Самый правильный комментарий.
(Reply) (Parent) (Thread)
[User Picture]From: rvb_glas
2013-08-14 06:50 am (UTC)
В среднем именно так, да :)
(Reply) (Parent) (Thread)
[User Picture]From: gul_kiev
2013-08-13 03:30 pm (UTC)
Сжатие на 100% - не фокус. Разжать потом - вот проблема.
И в описании упущена деталь - как была посчитана итоговая цифра 100%? Ну номер позиции ладно, можно пренебречь, но длину файла ведь всё равно нужно хранить, а она бывает весьма значительной, иногда даже больше, чем четыре байта необходимо.

Но я знаю обратимый алгоритм компресии, позволяющий сжать "Войну и мир" до одного бита (не 100%, конечно, но близко).
Алгоритм такой:
если первый бит "0", то это "Война и мир", если "1", то все последующие биты составляют исходный файл.
Условие выполнено.
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-13 05:00 pm (UTC)
> И в описании упущена деталь - как была посчитана итоговая цифра 100%?

Ну, это просто. Сжатый файл имеет длину 0.

Метаданные ведь в подсчёте не учитываются, а тут кроме метаданных ничего нет. Т.е. эта файловая система хранит только директории, контент файла восстанавливается при запросе на чтение.
(Reply) (Parent) (Thread)
[User Picture]From: prilezhny
2013-08-13 05:34 pm (UTC)
давайте введем поле "содержимое" в метаданные, и будем считать, что файл хранится там
это даст коэффициент сжатия 100, безотносительно ко всем наукообразным манипуляциям, которые только увеличивают, а не уменьшают длину, с единственной целью ученость показать

(большой палец вниз)
(Reply) (Parent) (Thread)
[User Picture]From: fat_yankey
2013-08-13 05:43 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: ivanov_petrov
2013-08-13 04:51 pm (UTC)
при этом геометрически изображается единственной картинкой. которую и передавать в ответ на любые сообщения
(Reply) (Thread)
[User Picture]From: otrubon
2013-08-13 04:59 pm (UTC)
третий подряд ваш пост "ни о чём"
дисквалифицируетесь потихоньку
я сожалею - в своё время вы были очень даже интересным web-персонажем

Edited at 2013-08-13 05:00 pm (UTC)
(Reply) (Thread)
(Deleted comment)
From: nealar
2013-08-14 06:40 am (UTC)
Он от этого не перестанет быть нелицензионным контентом. Вот если полные права на π передать в public domain, тогда появится шанс отбиться в суде.
(Reply) (Parent) (Thread)
[User Picture]From: samuel_volkov
2013-08-13 08:42 pm (UTC)
В комментариях столько серьезных людей,что шутить как-то боязно.

Поэтому задам лишь один вопрос Вам, как человеку разобравшемуся в вопросе. Аргументировал ли автор выбор именно "П" в качестве основы для построения файловой системы? И достаточно ли он защитил свой продукт от интеллектуальных воров, которые наверняка сделают нелицензионную копию, прикрывшись тем, что используют другое иррациональное число?
(Reply) (Thread)
[User Picture]From: rvb_glas
2013-08-14 06:50 am (UTC)
Название "efs" уже занятно.
(Reply) (Parent) (Thread)
[User Picture]From: samuel_volkov
2013-08-14 08:12 am (UTC)
Зато eFAT свободно!
(Reply) (Parent) (Thread)
[User Picture]From: fat_yankey
2013-08-18 02:29 pm (UTC)
FAT это уже немодно. It is so 1980s
(Reply) (Parent) (Thread)
[User Picture]From: fat_yankey
2013-08-18 02:25 pm (UTC)
Ну это ж free software - действующая модель коммунизма, - какие тут интеллектуальные воры? Весь код свободно доступен.

Что же до выбора "пи" как основы, то тут видимо никаких исследований не проводилось. Автор прямо указывает, что это альфа, proof of concept. Если community поддержит, то видимо сделают fork'и с другим основанием - нужно только чтобы оно было нормальным.
(Reply) (Parent) (Thread)
[User Picture]From: zveriozha
2013-08-18 10:01 am (UTC)
Забавно. Совсем недавно мы с френдами активно обсуждали похожую тему. Правда в более скромном ключе - какая длина числа Пи нужна, чтоб гарантировано найти там ваш номер мобильного и аську. Даже вышли на примерные цифры опытным путем..)

http://zveriozha.livejournal.com/325869.html
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-18 02:34 pm (UTC)
Если верна гипотеза о нормальности пи (что, как пишут выше, пока недоказано), то вероятность встретить выбранную последовательность цифр длиной n равна 10-n. В среднем значит нужно 10n знаков. Насчёт "гарантированно" тут труднее.

Edited at 2013-08-18 02:35 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]From: zveriozha
2013-08-18 03:11 pm (UTC)
Многие отрезки просто исследованы полным перебором.
(Reply) (Parent) (Thread)
From: (Anonymous)
2013-08-18 11:32 am (UTC)
Это было уже где-то. Даже еще проще: на линии AB ставилась отметка C в некотором месте, соотношение сторон AB и BC и давало то необходимое число, цифровое значение которого как раз и являлось кодируемой на отрезке информацией.

Смартфон справится, чего уж.
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-18 02:26 pm (UTC)
Вот так вот - пока одни обсуждают разные варианты, другие уже написали работающую систему и выложили код в свободный доступ.
(Reply) (Parent) (Thread)
[User Picture]From: egh0st
2013-08-18 05:17 pm (UTC)
ууу какой про-фейл у погромистов.

ладно математики не знают, это априори известно, хоть арифметику бы учили!


политпроствет от сенсея для ликтората:

1. есть файлы, каждый содержимым всего 32бита.
2. Файлов всего 2^32 то есть четыре лярда с гаком, вообще все возможные варианты от 0 до 2^32-1.
3. Погромистам предлагается найти любой алгоримтм, хоть через пи, хоть через е, хоть через гугол, хоть через поллитра :) который бы уменьшил ВСЕ файлы хотя бы на 1 (адын) бит (бит).

Для совсем непосвященных в тонкости арифметики подскажем, что в случае уменьшения всех файлов на 1 бит, количество разных файлов будет аж 2^31. Посему без использования метаданных вы их различить не сможете, чтд и qed, ольса слив защщитан :)


То есть погромисты не смогут сделать не то что 100% компресии, так даже и просто алгоритма гарантированной компрессии без потери данных, при этом любой компрессии, хоть на 1бит с 1гигабита.
(Reply) (Thread)
[User Picture]From: fat_yankey
2013-08-18 05:46 pm (UTC)

Why so serious?



Edited at 2013-08-18 05:51 pm (UTC)
(Reply) (Parent) (Thread)