Архивация.NEW!

Я предлогаю подумать над новыми алгоритмами архивации!

Старые были разработанны ...лет назад!

Какие будут предложения. Полезное дело сделаем.

Мысди:
1 ASCII- всего 255.Мало.

2 Символ имеет 8х16 матрицу

3 65000 цветов

4 два сивола в ASCII сложить в 1?Реально?!

"Мысди", может и интересные, но посмотри как старый Rar или Zip архивирует, потом подумай можешь ли ты сделать лучше, и есть ли у тебя высшее образование математика и програмиста, и делай супер новый архиватор.  

Сообщение отредактировано: .alex - 09.08.02, 10:43

А я не понял насчет мыслей? Что имелось ввиду?

А имелось в виду то, из чего можно вообще придумать алгоритм{на мой взгляд.Добавь что-нибудь сам}.

.alex! Я в общих чертах. программу то реализуем, главное алгоритм.

Ну к примеру в 2 символа записать 3. 5+5+5=15 + 5
15 - заарх. 3 чила, 5 - ключь и т.д.

символ "А" - матрица: 00011000
                               00100100
                               01111110
                               10000001  
                               10000001
ЭЭЭ... чего-то не то, но в общем...
Принять 1-й бит за ASCII #1, и т.д.

Мысли-то будут? Хоть какие?

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

Предлагаю сделать биты побольше :-)

Здорово!!! Давайте немного поМысдим и подправим эту  старую теорию,
по которой все сверху норовит упасть, и все по голове!
А кто-нибудь задумывался над тем что некоторые буквы сами по себе
не используются, например: п или х ? Разве что с "..."Может целого байта
им жирно?  

Цитата Alexei, 09.08.02, 17:37:54

Здорово!!! Давайте немного поМысдим и подправим эту  старую теорию,
по которой все сверху норовит упасть, и все по голове!
А кто-нибудь задумывался над тем что некоторые буквы сами по себе
не используются, например: п или х ? Разве что с "..."Может целого байта
им жирно?  

Дык для этого и есть старик Хаффман  ;D

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

Ну с текстом думаю покруче Хаффмана придумать что-то новое будет не просто  :-*, разве что кодировать целые слова (тока облом что их чуть больше чем 256 ;D).
А ведь есть еще и графика, тока вот сперва в JPEG'e разобраться не мешало бы, а можно еще и физиологию глаза изучить(эт никогда не помешает ;D). Ну а насчет графики я вообщето серьезно может есть у кого какие мысли, высказывайте, будем развивать.

Цитата DimA2, 09.08.02, 15:31:06

символ "А" - матрица: 00011000
                               00100100
                               01111110
                               10000001  
                               10000001
ЭЭЭ... чего-то не то, но в общем...
Принять 1-й бит за ASCII #1, и т.д.

а вот тут я что-то не понял, зачем букву то рисовать. Во-первых что бы записать эту матрицу понадобиться 5 байт(если я правильно все понимаю). А во-вторых ну нарисовал ты букву "А" а кто знает латинская она или русская, общий код в твоем представлении будет одинаковым, а на самом-то деле:
"A"(лат) -    01000001(b)   65(d)
"А"(рус) -    11000000(b)  192(d)
и то еще от кодировки зависит.

Хорошая статья

http://www.computerra.ru/offline/2002/447/18334/

Цитата Rechkin, 10.08.02, 08:59:24

Хорошая статья
http://www.computerra.ru/offline/2002/447/18334/

да уж, статья ничего так, но я считаю что Голдмен правильно сделал что не выплатил деньги, ведь как-то надо идентифицировать порядок файлов в котором их надо склеивать, пусть даже одним символом, но всеравно эффект от экономии одного байта сводится к нулю :-/, и то это пока файлов < 256 а потом уже еще и груз в имени +1 байт.
Да даже если отстраниться от компьтера и файлов и представить себе такую ситуацию:
   у вас есть рулон туалетной бумаги ;D(просто для примера подходит неплохо), так вот отматываем ее и записываем случайные символы (256 вариаций). Потом берем первый символ и ищем следующий такой же, когда найдем то перерезаем бумагу а сам символ вырезаем(тем самым уменьшаем саммарную длину бумаги, тоесть какбы сжимаем инфу) и так до конца рулона.
 Теперь для того что бы "деархивировать" надо просто склеить все куски, и учесть что каждый кусок начинается с символа который мы запоминаем при "архивации", НО ПРОБЛЕМА то в том что мы не знаем в какой последовательности куски клеить надо. Так что по любому необходимо их как то нумеровать, а это уже ЛИШНЯЯ информация.

Вот собственно и все мои мысли по этому пари,  ндеюсь вы со мной согласитесь, а можете и не соглашаться, с удовольствием выслушаю другие мнения

Цитата evilive, 10.08.02, 04:02:00

Ну с текстом думаю покруче Хаффмана придумать что-то новое будет не просто  :-*, разве что кодировать целые слова (тока облом что их чуть больше чем 256 ;D).

Ну ето ты зря. Не забывай и про LZW. Он есть для етих целей придуман.

HI ALL!

Я вижу тема вам интересна.

Насчёт рисования символа.
я имел в виду, что можно из ASCII символу составить новую матрицу сивола, куда поместить информацию о символах...

10010001... - 1-а,0-nil,0-nil,1-d и т.д.
Проблема в том что сами эти матрицы символов записаны в граф. адаптере,
но если придумать стандартные матрицы, то что-нибудь(может) и выйдит.

Но это 1 способ.

Можно сделать арх. пока только на 40 символов(А-Я,.).

По методу Фурье есть архиватор?

Вся проблема в том, как из 4040, к примеру, получить число до 255!

Можно эти числа делить на определённое число без остатка(найти ближайшей делитель).

JPEG насколько я знаю сжимает с потерями, а это неприемлемо.

Все архиваторы работают примерно по сценарию:

1 Ищут повторяющиеся цепочки символов и сочитаний символов.

Но это и так понятно, а надо именно в 1 символ записать 2.

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

ja tut podumal i pridumal novij arhivator tol'ko vot eshe ne dodumasja kak organizovat' raspokovku.
a ideja zapakovki takova:
berjom 1 j bajt i poslednij i vsje mezhdu nimi udaljaem  ;D

a esli serjeno to na s4et grafiki est' takaja ideja:
kto znaet japonskie krossvordy?
v principe izobrazhenie - ogromnaja matrica kotoruju mozhno szhat' metodom japonskogo krossvorda!
Nu 4to na4nem algoritm pridumyvat'?

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

Fog! Ну-ка ну-ка по подробнее!

Несовсем понимаю, что ты имеешь в виду.

Народ с предложением Outlandr'а согласны?

Выбирем идею и будем разрабатывать алгоритм.

???
Дайко помыслить...
"...файл есть оооочень болльшое число..." - это сумма всех символов, или прсто пипа:

2345678 - #23+#45+#67+#8?

делить это число до получения делителя без остатка? Можно взять 0-255 делителей *10-20!!!

Брать или весь файл(Рубишь, что за число выйдит? 8) ) или по 10-40? символов.

В принципе я так и хотел, но с 2 символами(read^), но проблема в том, что надо записывать и делитель и результат деления! Больше число, больше делитель и результат.

Я всё изложил правильно?

P.S. Будем думать...

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

А что, если применить расчёт матриц???Скажем 3-го порядка?(9 чисел)
А знаю, их обратно тоже расчитывают?

ой а можно по-подробнее...

Hi!

1 Ну во первых о грустном...
"2345678 - #23+#45+#67+#8?" - это неверно!!!! Знаешь почемУ? потому, что
надо так:#23+#45+#67+#8=023045067008! - уловил разницу? Нули-то где?
#1 - 001, а не просто 1!А нули в начале при счёте убираются 001+001=2, а не 002!
Как нам сделать числа из ASCII кодов?

2 Если не брать во внимание пункт 1 , то ЛЮБОЕ число представляет собой:
число1 в степени число2 + число3! Как ВЫ на это смотрите?
255^255+(0...65535):=...

3 А матрицах... Довольна интересная вещь. Пример(3 -й порядок):

23 х+40 у-65z=101
53 х-45 у-62z=201
71 х+12 у-65z=161


При расчёте находятся x,y,z(для четвертого - z2,z3,z4,z5...zXX);
Т.е. составив матрицу из ASCII кодов мы можем в заархив файл сами x,y,z(для четвертого - z2,z3,z4,z5...zXX) неписать. Вот.

Об эффективности пункта 2,3 - незнаю... надо считать.

Ваши мысли, господа!

Ну, народ предложения какие-нибудь будут, кроме STX'овых?

Цитата Outlander, 14.08.02, 17:54:31

a esli serjeno to na s4et grafiki est' takaja ideja:
kto znaet japonskie krossvordy?
v principe izobrazhenie - ogromnaja matrica kotoruju mozhno szhat' metodom japonskogo krossvorda!
Nu 4to na4nem algoritm pridumyvat'?

Я об этом тоже думал, но проблема то в том что изображения не всегда состоят всего из двух цветов  :-/, как это бывает в японских кроссвордах. Разве что создавать несколько матриц для трех цветов и альфа канала(или скорее каналлов для каждого цвета). Но и тут есть проблемы.

Как вы оцениваите мои идеи?

Цитата evilive, 18.08.02, 02:21:07

Я об этом тоже думал, но проблема то в том что изображения не всегда состоят всего из двух цветов  :-/, как это бывает в японских кроссвордах. Разве что создавать несколько матриц для трех цветов и альфа канала(или скорее каналлов для каждого цвета). Но и тут есть проблемы.

mozhno obojtis' 2umja matricami 1 pikseli 2 cvet sootvetstvueshego pikselja v 1oj matrice

Сообщение отредактировано: Outlander - 19.08.02, 09:45

Цитата Outlander, 19.08.02, 13:43:59

mozhno obojtis' 2umja matricami 1 pikseli 2 cvet sootvetstvueshego pikselja v 1oj matrice

 Во-первых я что-то не понимаю как это можно в матрице, составленной по принципу японского кроссворда, менять какие-то значения в диапазоне большем чем 2 значения (клеточка либо черная, либо белая, все, других вариантов быть не может), так что как ты собираешься записывать цвет каждого пикселя в одной матрице я так и не понял.
 Во-вторых, что значит твое высказывание по поводу 1-ой матрицы которую ты собрался использовать для записи пикселей, каких пикселей и что значит для тебя вообще это слово...???
 И наконец в-третьих если описывать цвет каждого пикселя, то где же тут сжатие данных, в обычном BMP-формате при описании картинки получится меньший размер (в нем не надо строить никаких японских кроссвордов, а просто попорядку описываем каждый пиксель ).

Цитата DimA2, 19.08.02, 11:16:05

Как вы оцениваите мои идеи?

По поводу твоих идей, DimA2, насчет матриц третьего порядка, боюсь что при разворачивании (т.е. разархивации) в первоначальное состояние невозможно будет проконтролировать порядок коэффициентов при x,y,z. Ведь от перемены мест слогаемых сумма не меняется .

Кажись придумал?!! 8) Аж синий от осинения

число Х:=255255255255255255255255255(9 символов 255, т.е. возможный максимум.)


Находим(Расчитываем)  1 число - число, при возведении в степель 255 дающее >X(Находится легко)

Находим  2 число - число < число 1

3,4,5 число  - думаю гдето 2

Все эти числа(1,2,3,4,5) - константы, и всегда неизменны!

Что выходит?

Архив.:
Находим степень1, при которой чило1 в этой степени < X.(Максимально приближено)

Х-число1^степень1:=остаток1(Всегда недРОБНЫЙ!)

остаток1-число2^степень2:=остаток2

остаток2-число3^степень3:=остаток3
остаток3-число4^степень4:=остаток4
остаток4-число5^степень5:=остаток5;

Так!  остаток5 - вот что нам по сути и нужно ухитрится записать 2-3 символами(числами по 255!)

В результирующем(Заархив.) файле:
степень1,степень2,степень3,степень4,степень5,2-3(символы,показ остаток5)!!!

Разархив. наоборот!

ЗЫ!

Ну как? Вопросы...

В итоге 9 символов заархивируются в 8!!!ВСЕГДА!!!!

Ошибок в алгоритме не найдено, в теории тоже.


Т.е. применяя несколько раз алгоритм к одному и тому-же файлу получаем, что файл любых размеров умещается в 9+0..8(неархив. остаток!)

А че такое число X ? Я не понял...

2Dima2 ты статью ,на которую давали линк прочитал?

ладно, предлагаю тебе попробовать реализовать твой алгоритм на практике.
вот тебе число
123 098 435 567 032 006 435 231  856
(9 символов) предлагаю его запаковать в 8 по твоему алгоритму.
ЗЫ, число1 наверное будет равно 2, тк 2 в степени 255 больше число, которое может быть записано в 9 байт (9 байт - 56 бит, следовательно твое числ Х <= 2 в степени 56, а 2 в степени 255 всяко больше 2 в степени 56\%) )

Сообщение отредактировано: Demo_S - 20.08.02, 21:48

Хм...

Вчера алгоритм свой я реализовал, но результаты... оказаливь немного не те...

Сегодня попробую не
остаток1-число2^степень2:=остаток2(после каждой операции на 2 порядка сокращение), а

остаток1/число2^степень2:=остаток2


И ещё... почему при ВЫЧИТАНИИ получается дРоБнОе число? nnn.5

Dr_Freemen! Число Х - это ASCII коды дивети чисел.

Насчёт методов сжатия графики:
Часто бывает что в картинке в 256 цветов получается несколько символов подряд:

abcdefg или 123456 или наоборот gfedcba, но факт то, что почему бы их не записать переходом? от 1 до 6.

Незнаю, может ясказанул, чего не понял, н идея хороша! а есл графика в 24 а не 256 цветов, её можно разложить по цветам, r g b, каждый опять же от 0 до 255!

Подумайте на эту тему, сам всю ноч кшмарил, кто что-лбо придумает, пишите тут!

Ребята!!!!
ау!
почитайте сначала какие-нить алгоритмы сжатия, тот же RLE или LZW, доки+примеры могу дать
а то просто заново изобретаете велосипед, причем очень кривой!.
ЗЫ извиняюсь если кого обидел
ЗЗЫ кстати, 2purpe, я когда то кидал сюда(тебе в смысле) сорс архиватора + дока, оно к сожалению так и не появилось, может кинуть снова?.

Сообщение отредактировано: Demo_S - 23.08.02, 18:26

Цитата fog, 15.08.02, 10:44:32

файл есть оооочень болльшое число, находим ближайшее простое
в качестве результата сжатия записываем порядковый номер этого числа
1   2
2   3
3   5
4   7
5   11
6   13
7   17
...
и разницу между исходным числом и ближашим простым
для 32 бит сжатия нет вообще, а дальше... кто его

Пусть f - очень большое число (последовательность нулей и единиц архивируемого файла). Вы хотите представить его в виде
  f = p + d,
где p - ближайшее простое число, d - добавка. Вы хотите в "архивном" файле хранить числа {n,d}, где n - порядковый номер простого числа p. Поскольку  n < p, значит, казалось бы, места должно занимать меньше. На самом деле это не так. Дело в том,
что с ростом p число n тоже растет достаточно быстро (простых чисел много). Поэтому сумма размеров чисел n и d не будет заметно меньше размера f.

Вместо доказательства, давайте рассмотрим еще более "выгодный" случай. Представим число f в виде "полного квадрата" плюс добавка
 f = g*g + d.
Размер числа g в два раза меньше размера числа f. Значит, если добавка d будет не большой, то мы "заархивируем" почти в два раза!!! Но не тут-то было. Дело в том, что в большинстве случаев размер добавки d тоже равен половине размера числа f (это я оставлю без доказательства), и сохранение вместо f чисел {g,d} не приводит к уменьшению размера. Количество простых чисел растет быстрее чем квадратный корень, поэтому "архивация" f = p + d, тем более не эффективна.

Предлагаю воспользоваться принципом НАОБОРОТ. Будем считать, что число f есть  результат подобного сжатия (g*g+d), при этом число f оказывается с большим количеством знаков, чем изначальное. Теперь проводим операцию РАССЖАТИЯ и получаем исходное число с меньшим количеством знаков. Т.е. фактически получаем сжатие.
Так выглядит теория. Можно ли получить такое на реальных числах - не знаю.

ребята вы меня извините, но вы математику учили.

Не возможно написать ВЗАИМНООДНОЗНАЧНУЮ функцию из пространства с большим числом измерений в меньшее. (поясню нельзя написать архиватор который для ЛЮБОГО ввода в 9 символов кодирует в 8)

это достаточно очевидно ведь различных текстов в 9 байт некоторое число в степени 9, а в 8 байт тоже число в степени 8 , ясно что второе меньще первого.

так что очевидно что бессмысленно изобретать что-то сжимающее все и без потери

на самом деле вы от jpg зря отказались, происходит потеря только высоких частот, которые для   человека неинформативны, и если хотите что-то изобрести, то найдите базис по которому будет легче архивировать типа фурье иди адамара

с уважением

Demo_S можешь по RLE алгоритм + пример написать...или приложить файликом...а то очень нада для работы!

Сейчас я вам скажу способ идеального сжатия!!!

На входе алгоритма есть последовательность символов.
Находим в последовательности символов все возможные комбинации подпоследовательностей.
Это можно делать так же, как и строится контекстная модель. Только её глубину при максимальном сжатии нужно выбрать равной длине исходной последовательности. На практике при достаточно длинных последовательностях это не реализуемо ввиду большого расхода памяти. Поэтому её глубину можно выбирать разумно, чтобы хватило памяти.
Находим такую подпоследовательность, чтобы её длина была больше 1 и произведение её длины на количество её вхождений в исходную последовательность минус один было максимальным. L * (N - 1).
Расширяем алфавит символов ещё одним символом, который будет обозначать найденную подпоследовательность. Заменяем все её вхождения в исходную последовательность этим символом, а саму подпоследовательность добавляем в словарь.
Повторяем эти действия, пока не можно найти такие подпоследовательности. В итоге в исходной последовательности не останется ни одной пары рядом стоящих символов, которая бы повторялась два раза. То есть каждая пара рядом стоящих символов будет уникальна.
Далее полученную последовательность можно сжать арифметическим кодированием. Так же можно сжать некоторые последовательности из словаря.
Вот так вот!

Цитата maggot @ 27.03.08, 10:44

Сейчас я вам скажу способ идеального сжатия!!!

На входе алгоритма есть последовательность символов.
Находим в последовательности символов все возможные комбинации подпоследовательностей.
Это можно делать так же, как и строится контекстная модель. Только её глубину при максимальном сжатии нужно выбрать равной длине исходной последовательности. На практике при достаточно длинных последовательностях это не реализуемо ввиду большого расхода памяти. Поэтому её глубину можно выбирать разумно, чтобы хватило памяти.
Находим такую подпоследовательность, чтобы её длина была больше 1 и произведение её длины на количество её вхождений в исходную последовательность минус один было максимальным. L * (N - 1).
Расширяем алфавит символов ещё одним символом, который будет обозначать найденную подпоследовательность. Заменяем все её вхождения в исходную последовательность этим символом, а саму подпоследовательность добавляем в словарь.
Повторяем эти действия, пока не можно найти такие подпоследовательности. В итоге в исходной последовательности не останется ни одной пары рядом стоящих символов, которая бы повторялась два раза. То есть каждая пара рядом стоящих символов будет уникальна.
Далее полученную последовательность можно сжать арифметическим кодированием. Так же можно сжать некоторые последовательности из словаря.
Вот так вот!

cмешно и грустно.


Идеальное сжатие это ф-я копирования, это факт

Цитата esperanto @ 27.03.08, 11:37

Цитата maggot @ 27.03.08, 10:44

Сейчас я вам скажу способ идеального сжатия!!!

На входе алгоритма есть последовательность символов.
Находим в последовательности символов все возможные комбинации подпоследовательностей.
Это можно делать так же, как и строится контекстная модель. Только её глубину при максимальном сжатии нужно выбрать равной длине исходной последовательности. На практике при достаточно длинных последовательностях это не реализуемо ввиду большого расхода памяти. Поэтому её глубину можно выбирать разумно, чтобы хватило памяти.
Находим такую подпоследовательность, чтобы её длина была больше 1 и произведение её длины на количество её вхождений в исходную последовательность минус один было максимальным. L * (N - 1).
Расширяем алфавит символов ещё одним символом, который будет обозначать найденную подпоследовательность. Заменяем все её вхождения в исходную последовательность этим символом, а саму подпоследовательность добавляем в словарь.
Повторяем эти действия, пока не можно найти такие подпоследовательности. В итоге в исходной последовательности не останется ни одной пары рядом стоящих символов, которая бы повторялась два раза. То есть каждая пара рядом стоящих символов будет уникальна.
Далее полученную последовательность можно сжать арифметическим кодированием. Так же можно сжать некоторые последовательности из словаря.
Вот так вот!

cмешно и грустно.


Идеальное сжатие это ф-я копирования, это факт

Хах, может ты просто не понял, о чем я писал. По твоему такое сжатие не будет работать?

Не будет

Таак.
Тот алгоритм, который я описал, на практике наверное не применим (работает ооочень медленно), но он работает. И сжатие будет. Так что не гоните! Я его реализовал. Прямо точно так, как написал.

Ну для больших текстов сжатие будет, наверно. Но на универсвльный архиватор это естественно не тянет
Кстати, есть модификация LFF алгоритмов LZ, которая как раз и занимается поиском во входном потоке максимальных цепочек (независимо от их положения), которые затем сжимаются, и такая итерация повторяется. Вот только интересно, что сжатие самых длинных цепочек в результате не дает самого лучшего сжатия, а достигается оно при оптимальном разборе, нахождение которого есть NP-полная задача.

Цитата maggot @ 28.03.08, 17:15

Таак.
Тот алгоритм, который я описал, на практике наверное не применим (работает ооочень медленно), но он работает. И сжатие будет. Так что не гоните! Я его реализовал. Прямо точно так, как написал.

Т.е вы клянетесь, что ваш алгоритм работает?


Неубедительно. Все таки математика царица наук не просто так. И "мамой клянусь" не принимает

esperanto
Чесно говоря не понимаю, что смущает тебя...
Меня смущает только "подпоследовательность".
Автор имел ввиду, скорее всего, "цепочку символов".
Т.е. такие подпоследовательности, символы в которой стоят рядом.
В итоге получаем немного измененный LZ

Добавлено 28.03.08, 19:30
Ну еще вот это смущает:

Цитата

способ идеального сжатия!!!

Цитата Hsilgos @ 28.03.08, 19:29

esperanto
Чесно говоря не понимаю, что смущает тебя...
Меня смущает только "подпоследовательность".
Автор имел ввиду, скорее всего, "цепочку символов".
Т.е. такие подпоследовательности, символы в которой стоят рядом.
В итоге получаем немного измененный LZ

Добавлено 28.03.08, 19:30
Ну еще вот это смущает:

Цитата

способ идеального сжатия!!!

Меня смущает то, что автор привел алгоритм. Назвав его илеальным.


Мало того что не ясно что такое идеальный.
Не приведен анализ и доказательство работы алгоритма.

Цитата esperanto @ 28.03.08, 17:37

Цитата maggot @ 28.03.08, 17:15

Таак.
Тот алгоритм, который я описал, на практике наверное не применим (работает ооочень медленно), но он работает. И сжатие будет. Так что не гоните! Я его реализовал. Прямо точно так, как написал.

Т.е вы клянетесь, что ваш алгоритм работает?


Неубедительно. Все таки математика царица наук не просто так. И "мамой клянусь" не принимает

А если ты такой суперматематик, докажи, что в любом случае сжатия не будет. Или за весь курс математики выучил только то, что она царица наук? Я серьёзно. Докажи в таком случае, что алгоритм в любом случае не будет сжимать. А то вот так слово математика везде лепят в основном заучки-тугодумы - абсолютно бездарные математики.

Цитата

Не приведен анализ и доказательство работы алгоритма.

Его и не будет. И вообще алгоритм был придуман за время, когда я писал пост.

Цитата

Ну еще вот это смущает:
Цитата

Цитата

способ идеального сжатия!!!

А меня вся эта тема смущает. Вы что, верите, в то что придумаете алгоритм лучше существующих??

esperanto, а сама программа в прикреплённом файле.

А это код, если ты не веришь, что там этот алгоритм.

typedef std::basic_string<unsigned short int> mystring_type;
 
template<class T> class ContextModel{
    struct Node{
        struct pt{
            Node* _first;
            unsigned int _second;
            pt(): _second(0), _first(0){}
        };
        typedef Map<T, pt , NonHashed<VECTOR>, simpleLink> MapType;
        MapType transition;
        Node(){}
        void Print(const std::basic_string<T>& arg){
            for(MapType::iterator i = transition.first(); i; ++i){
                printString__(arg + (*i)._first);
                std::cout << " : " << ((*i)._second._second) << std::endl;
                if((*i)._second._first != 0) (*i)._second._first->Print(arg + (*i)._first);
            }
        }
    
        unsigned int getTheBest(unsigned int N, std::basic_string<T> & result){
            unsigned int maxFreq = 0;
            for(MapType::iterator i = transition.first(); i; ++i){
                std::basic_string<T> xStr;
                unsigned int xFreq = ((*i)._second._first != 0)?(*i)._second._first->getTheBest(N + 1, xStr) : 0;
                
                if(xFreq == 0 || ((N > 0) && (N + 1)*((*i)._second._second - 1) > (N + 1 + xStr.size())*(xFreq - 1))){
                    xStr = (*i)._first;
                    xFreq = (*i)._second._second;
                }else xStr = (*i)._first + xStr;
                if(maxFreq == 0 || ((N + xStr.size() > 1) && (N + xStr.size())*(xFreq - 1) > (N + result.size())*(maxFreq - 1))){
                    result = xStr;
                    maxFreq = xFreq;                
                }
            }
            return maxFreq;
        }
        ~Node(){
            for(MapType::iterator i = transition.first(); i; ++i)
                if((*i)._second._first != 0) delete (*i)._second._first;
        }
    };
    Node rootNode_;
    unsigned int depth_;
    void addSubstr(const std::basic_string<T>& arg, unsigned int index/*, unsigned int length*/){
        std::basic_string<T> x = arg.substr(index, depth_);
        Node *pNode = &rootNode_;
        for(unsigned int i = 0; i < x.size(); ++i){
            Node * nextNode = 0;
            try{nextNode = static_cast<Node::pt>(pNode->transition[x[i]])._first;} catch (const Out_Of_Range&){}
            if(nextNode == 0 && i != (x.size() - 1)) static_cast<Node::pt&>(pNode->transition[x[i]])._first = nextNode = new Node();
            ++static_cast<Node::pt&>(pNode->transition[x[i]])._second;
            pNode = nextNode;
        }
    }
public:
    ContextModel(unsigned int depth): depth_(depth){}
    void addString(const std::basic_string<T>& arg){
        for(unsigned int i = 0; i < arg.size(); ++i)
            addSubstr(arg, i);
        
    }
    void printCurrentState(){
        rootNode_.Print(std::basic_string<T>());
    }
    unsigned int getTheBestSubsting(std::basic_string<T>& result){
        unsigned int freq = rootNode_.getTheBest(0, result);
        return freq;
    }
};
class BitWriter{
    union BufT{
        unsigned __int64 asLongInt;
        unsigned int asUInt[2];
        unsigned char asUChar[8];
        char asChar[8];
    } buffer_;
    unsigned char shfind_;
    std::ofstream& stream_;
public:
    BitWriter(std::ofstream& stream): stream_(stream){buffer_.asLongInt = 0; shfind_ = 0;}
    void WriteBits(unsigned char bitscount, unsigned int data){
        bitscount %= 32;
        unsigned __int64 mask = 0x0000000000000000 | ((1 << bitscount) - 1);
        unsigned __int64 ldata = mask & data;
        buffer_.asLongInt |= ldata << (64 - shfind_ - bitscount);
        shfind_ += bitscount;
        while(shfind_ >= 8){
            stream_ << buffer_.asChar[7];
            buffer_.asLongInt <<= 8;
            shfind_ -= 8;
        }  
    }
    ~BitWriter(){
        stream_ << buffer_.asChar[7];
    }
};
 
void saveToFile(const Map<unsigned short int, mystring_type >& extCharsetTable, const mystring_type& dest_str, const char* destFName){
    std::ofstream oFile(destFName, std::ios::binary);
    BitWriter myBitWriter(oFile);
    myBitWriter.WriteBits(9, extCharsetTable.size());
    for(Map<unsigned short int, mystring_type >::iterator i = extCharsetTable.first(); i ; ++i){
        myBitWriter.WriteBits(2, (*i)._second.size() - 1);
        for(mystring_type::const_iterator j = (*i)._second.begin(); j != (*i)._second.end(); ++j)
            myBitWriter.WriteBits(9, *j);
    }
    myBitWriter.WriteBits(31, dest_str.size());
    for(mystring_type::const_iterator j = dest_str.begin(); j != dest_str.end(); ++j)
        myBitWriter.WriteBits(9, *j);
    
}
 
class BitReader{
    union BufT{
        unsigned __int64 asLongInt;
        unsigned int asUInt[2];
        unsigned char asUChar[8];
        char asChar[8];
    } buffer_;
    unsigned char shfind_;
    std::ifstream& stream_;
public:
    BitReader(std::ifstream& stream): stream_(stream){buffer_.asLongInt = 0; shfind_ = 0;}
    unsigned int ReadBits(unsigned char bitscount){
        bitscount %= 32;
        while(shfind_ < bitscount){
            buffer_.asLongInt <<= 8;
            stream_.get(buffer_.asChar[0]);
            shfind_ += 8;      
        }
        union{
            unsigned __int64 ldata;
            unsigned int asUInt[2];
        } x;
        x.ldata = buffer_.asLongInt;
        x.ldata >>= (shfind_ - bitscount);
        shfind_ -= bitscount;
        unsigned int mask = 0x00000000 | ((1 << bitscount) - 1);        
        unsigned int data = mask & x.asUInt[0];
        
        return data;
    }
};
void readFromFile(Map<unsigned short int, mystring_type >& extCharsetTable, mystring_type& dest_str, const char* destFName){
    std::ifstream iFile(destFName, std::ios::binary);
    BitReader myBitReader(iFile);
    unsigned int sz =  myBitReader.ReadBits(9);
    for(unsigned int i = 0; i < sz; ++i){
        mystring_type stri;
        unsigned int leng = myBitReader.ReadBits(2) + 1;
        for(unsigned int j = 0; j < leng; ++j)
            stri += static_cast<unsigned short>(myBitReader.ReadBits(9));
        extCharsetTable[256 + i] = stri;
    }
    unsigned int leng =  myBitReader.ReadBits(31);  
    for(unsigned int j =  0; j < leng; ++j)
        dest_str += static_cast<unsigned short>(myBitReader.ReadBits(9));  
}
 
 
void Compress(const char* sourceFName, const char* destFName){
    std::ifstream iFile(sourceFName, std::ios::binary);
    mystring_type mystr;
    char c;
    while (iFile.get(c)) mystr += 128 + c;
    unsigned int uncompressedStringSize = mystr.size();
 
    Map<unsigned short int, mystring_type > extendedCharsetTable;
    unsigned short int index = 255;
 
    std::cout << "Input file size: " << mystr.size() << " bytes" << std::endl;
    mystring_type bestStr;
    unsigned int maxCount = 255; //250
    do{
        
        ContextModel<unsigned short int> myCM(4);
        myCM.addString(mystr);
        unsigned int freq = myCM.getTheBestSubsting(bestStr);
        extendedCharsetTable[++index] = bestStr;
        std::cout << static_cast<char>(static_cast<unsigned char>(13)) << 100 * (255 - maxCount) / 255 << "% completed";
        
        mystring_type::iterator pos;
        pos = std::search (mystr.begin(), mystr.end(), bestStr.begin(),bestStr.end());
 
 
        while (pos != mystr.end()) {
            mystr.replace(pos, pos + bestStr.size(), 1, index);
            pos = std::search (mystr.begin(), mystr.end(), bestStr.begin(),bestStr.end());
        }
                --maxCount;
    } while(bestStr.size() > 1 && maxCount);
    std::cout << std::endl;
    unsigned int tblSize = 0;
    for(Map<unsigned short int, mystring_type >::iterator i = extendedCharsetTable.first(); i ; ++i) tblSize+= 2 + 9*((*i)._second.size());
    std::cout <<"Table size: " << tblSize/8 + 9 << " bytes" << std::endl;
    std::cout <<"Data size: " << 9*mystr.size()/8 + 31 << " bytes" << std::endl;
    std::cout <<"Compression : " << 100*(tblSize/8 + 9*mystr.size()/8 + 31 + 9) / uncompressedStringSize  << " %"<< std::endl;
 
    saveToFile(extendedCharsetTable, mystr, destFName);
}
void Decompress(const char* sourceFName, const char* destFName){
    mystring_type mystr2;
 
    Map<unsigned short int, mystring_type > extendedCharsetTable2;
    readFromFile(extendedCharsetTable2, mystr2, sourceFName);
    bool flag = true;
    while (flag){
        flag = false;
        mystring_type newString;
        for(unsigned int i = 0; i < mystr2.size(); ++i){
            unsigned int cChar = mystr2[i];
            if(cChar > 255){
                flag = true;
                newString += extendedCharsetTable2[cChar];
            }else newString += cChar;
        }
        mystr2 = newString;
    }
    std::cout << "Decompressed!" << std::endl;
    std::ofstream oFile(destFName, std::ios::binary);
    for(unsigned int i = 0; i < mystr2.size(); ++i){
        unsigned short int cChar = mystr2[i];
        if(cChar < 255) oFile << static_cast<char>(static_cast<int>(cChar) - 128);
    }
}
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    _CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    
    if(argv[1] == std::string("compress"))
        Compress(argv[2], argv[3]);
    else if(argv[1] == std::string("decompress"))
        Decompress(argv[2], argv[3]);
    else std::cout << "compression.exe [compress/decompress] inputfile outputfile" << std::endl;
    return 0;
}

Сообщение отредактировано: maggot - 29.03.08, 09:38

Прикреплённый файлmycompression.rar (26.94 Кбайт, скачиваний: 193)

maggot, Как вы знаете "Один глупец может задавать вопросов на сотню мудрецов" (с)

Так вот, неужели вы думаете, я за свою жизнь преподавания и работы не встречал таких гениальных программистов как вы. "Я написал нечто докажите что это неправильно."
Не раз и не два.


Зачем?

Во-первых, это пустая трата, в данном случае, времени.
Во-вторых идеальным по шенону является то же энтропийное сжатие.
В-третих, вы даже не удосужились привести определение идеального.


Начните с определенния идеального алгоритма сжатия. Иначе разговор будет пустой тратой времени.

Цитата

Докажи в таком случае, что алгоритм в любом случае не будет сжимать

Цитата

Не возможно написать ВЗАИМНООДНОЗНАЧНУЮ функцию из пространства с большим числом измерений в меньшее. (поясню нельзя написать архиватор который для ЛЮБОГО ввода в 9 символов кодирует в 8)

Очень даже математически он доказал. Если не что-то непонятно - учи алгебру и ФАН.
Это значит, в частном случае, что для любого точного алгоритма можно найти такую последовательность символов, которую он не сожмет.

Добавлено 29.03.08, 10:48
http://ru.wikipedia.org/wiki/Арифметическое_кодирование

Добавлено 29.03.08, 10:54
Выдержка:

Цитата

Обеспечивает почти оптимальную степень сжатия с точки зрения энтропийной оценки кодирования Шеннона.
...
Однако в случае равновероятного распределения символов, например для строки бит 010101...0101 длины s метод арифметического кодирования приближается к префиксному коду Хаффмана и даже может занимать на один бит больше.

[offtop

Цитата

А то вот так слово математика везде лепят в основном заучки-тугодумы - абсолютно бездарные математики.
Цитата
"Не приведен анализ и доказательство работы алгоритма."
Его и не будет. И вообще алгоритм был придуман за время, когда я писал пост.

Прямо comedy club на сорцах.
Вот на случай цитата от бездарного математика-тугодума:
"При грамотном программировании на тысячу строк программного текста нужно написать в десять раз больше рассуждений и доказательств, гарантирующих применимость программы".
Э. Дейкстра
offtop]

Цитата esperanto @ 29.03.08, 10:14

maggot, Как вы знаете "Один глупец может задавать вопросов на сотню мудрецов" (с)

Так вот, неужели вы думаете, я за свою жизнь преподавания и работы не встречал таких гениальных программистов как вы. "Я написал нечто докажите что это неправильно."
Не раз и не два.


Зачем?

Во-первых, это пустая трата, в данном случае, времени.
Во-вторых идеальным по шенону является то же энтропийное сжатие.
В-третих, вы даже не удосужились привести определение идеального.


Начните с определенния идеального алгоритма сжатия. Иначе разговор будет пустой тратой времени.

Да, это пустая трата времени, точно такая же, как и вся эта тема. Не понятно? Естественно, алгоритм не идеальный.
Я не претендую на изобретение нового алгоритма. Я просто написал очередной глупый ответ в эту тему. НО, заметьте, я же не написал полный бред, я за свои слова отвечаю - алгоритм работает и сжимает. Это можно проверить, запустив программу. А теоретически мне это доказывать неохото, да и я считаю, в этом нет смысла, тк алгоритм не эффективный.

А ваш опыт преподавания - это совсем не гарантия того, что вы всегда правы.
У меня был один учитель по программированию, который мне как то пытался объяснить, что указателя на указатель в языке программирования Паскале не может быть. Но вот моя программа почему то работала. Мне это тоже надо было доказывать?

Я не отрицаю роль доказтельств. Просто не во всех предметах можно строить хорошие доказательства. Можно в математическом анализе. В алгебре доказательства уже хуже. В теории графов тоже плохие. Хорошие - значит, что сложно усомниться в истинности этого доказтельства.

Цитата

В теории графов тоже плохие.

Наверное мы учили разные теории графов =)

А вообще, у нас в последнем семе на 5 курсе был веселый пропод. Проподавал препод "Историю математики".
И говорил он нам там удивительные вещи. В часности, что математика базируется на таких аксиомах, верность которых невозможно как доказать, так и опровергнуть.
Попал тогда под раздачу и матан, со своей "аксиомой выбора", о которой никто никогда не задумывался...
Основным его стремлением было донести, что все, что мы учили в универе, по сути, фуфло, и "строгой наукой" может назваться только с натяжкой. ( Тоже самое нам говорили на первом курсе про школьную математику =) )
Хороший был, препод, да...

Цитата Hsilgos @ 29.03.08, 11:36

И говорил он нам там удивительные вещи. В часности, что математика базируется на таких аксиомах, верность которых невозможно как доказать, так и опровергнуть.

Самое удивительное - то, что кто-то находт удивительным факт невозможности доказания аксиом.

Цитата

Самое удивительное - то, что кто-то находт удивительным факт невозможности доказания аксиом.

Я немного не так выразился.
Суть в том, что аксиомы "верны", только пока не находится контрпример. А контрпример, соответственно, найти невозможно, как, в принципе, невозможно и доказать аксиому.
Она нам ясна только как само собой разумеющееся, не терпящее сомнений.
В то же время математика - точная наука, которая неприемлет такого отношения к себе.
В общем, тут вопрос, скорее, филосовский.

Но этим он хотел показать, что нужно сомневаться во всем сказанном, если нет строгого логического безошибочного докозательства

Цитата Hsilgos @ 30.03.08, 00:36

Я немного не так выразился.
Суть в том, что аксиомы "верны", только пока не находится контрпример. А контрпример, соответственно, найти невозможно, как, в принципе, невозможно и доказать аксиому.
Она нам ясна только как само собой разумеющееся, не терпящее сомнений.
В то же время математика - точная наука, которая неприемлет такого отношения к себе.
В общем, тут вопрос, скорее, филосовский.

Ничего подобного.
Совнетую на досуге почитать историю науки. Например, как попытки доказания пятого постулата Евклида привели к созданию геометрий Римана и Лобачевского.

Цитата

Но этим он хотел показать, что нужно сомневаться во всем сказанном, если нет строгого логического безошибочного докозательства

Если даже есть строгое логческое безошибочное доказательство, то оно отнюдь не является противопоказанием для сомнений.

Сообщение отредактировано: andriano - 30.03.08, 18:12

Цитата

Ничего подобного.
Совнетую на досуге почитать историю науки. Например, как попытки доказания пятого постулата Евклида привели к созданию геометрий Римана и Лобачевского.

Я это прекрасно знаю и хотел об этом сюда написать =)
Аксиома-то "интуитивно" верна, правильно? Через одну точку может проходить только одная прямая, паралельная данной...
Получается Геометрия Лобачевского и проективная геометрия опровергают Евклидову.
Хотя на самом деле геометрии сосуществуют и очень хорошо применяются.
Каждая в определенном пространстве.

На матане и прочих, часто говорили про "Аксиому выбора".

Цитата

Аксиома выбора принимается не всеми математиками безоговорочно: некоторые относятся к ней с недоверием. Бытует мнение, что доказательства, полученные с привлечением этой аксиомы, имеют иную познавательную ценность, чем доказательства, независимые от неё.

Сообщение отредактировано: Hsilgos - 30.03.08, 23:40

Авторам алгоритмов советую почитать книжку Ватолина про сжатие данных. И вспомнить теоремки, накладывающие ограничения на степень сжатия информации. Например, не может существовать архиватор, который сжимал (хоть немного) бы все входящие последовательности. Или, степень сжатия ограничена информационной энтропией.

Цитата Navi1982 @ 31.03.08, 15:47

Цитата

Например, не может существовать архиватор, который сжимал (хоть немного) бы все входящие последовательности. Или, степень сжатия ограничена информационной энтропией.

Глупее ничего не слышал. А выглядит как "невозможно оторватся от земли и улететь в космос" 100 лет тому назад. Или, далеко ходить ненадо - споры о пределе вычислительной техники... интернета, нейросетей и т.д. и т.п.

Простите, но вы сказали ересь.

-Added 31.03.08, 16:26

Цитата Hsilgos @ 30.03.08, 00:36

Цитата

Самое удивительное - то, что кто-то находт удивительным факт невозможности доказания аксиом.

Я немного не так выразился.
Суть в том, что аксиомы "верны", только пока не находится контрпример. А контрпример, соответственно, найти невозможно, как, в принципе, невозможно и доказать аксиому.
Она нам ясна только как само собой разумеющееся, не терпящее сомнений.
В то же время математика - точная наука, которая неприемлет такого отношения к себе.
В общем, тут вопрос, скорее, филосовский.

Но этим он хотел показать, что нужно сомневаться во всем сказанном, если нет строгого логического безошибочного докозательства

Не Вы, тут тоже не правильно выразились.


Короче, система аксиом теории чисел(аксиом Пеано) не полна. Т.е в ней нельзя доказать любую верную теорему. Причем ее нельзя дополнить, непротиворечивыми аксиомами, так чтобы она стала полной.

Набор аксиом называется непротиворечивым, если
Или он не доказывает любую теорему.

Или в нем неможно доказать одновременно некую теорему и ее отрицание.



А вообще почитайте или Геделя или замечательную книгу "Гедель, Эшер и Бах"

Цитата

Не Вы, тут тоже не правильно выразились.


Короче, система аксиом теории чисел(аксиом Пеано) не полна. Т.е в ней нельзя доказать любую верную теорему. Причем ее нельзя дополнить, непротиворечивыми аксиомами, так чтобы она стала полной.

Набор аксиом называется непротиворечивым, если
Или он не доказывает любую теорему.

Или в нем можно доказать одновременно некую теорему и ее отрицание.

О! Прям его словами говорите =)

Добавлено 31.03.08, 17:26

Цитата

Глупее ничего не слышал. А выглядит как "невозможно оторватся от земли и улететь в космос" 100 лет тому назад. Или, далеко ходить ненадо - споры о пределе вычислительной техники... интернета, нейросетей и т.д. и т.п.

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

Простите, но вы перечислили факты физические, а математика физике имеет весьма отдаленное отношение.

Архивация же - чистая математика. Технологии будут совершенствоваться, математика так же будет развиваться. Но, мне кажется, невозможность "универсальной архивации" практически очевидно.

Сообщение отредактировано: Hsilgos - 31.03.08, 17:27

[offtop
Нажать "Ответить" и внизу появится обзор для прикрепления файла
offtop]

Цитата Navi1982 @ 31.03.08, 18:33

Перебор вариантов (даже слегка оптимизированный) может длится неделями и не завершится

Алгоритмы которые могут не завершиться, не называют алгоритмами.

Это в принципе ничто

А почему бы MS не выпустить файл-словарь, в котором будут наиболее часто встречающиеся выражения или последовательности (заранее сделав тесты) и поставлять его вместе с Виндой?

Сообщение отредактировано: ZOXEXIVO - 01.04.08, 15:16

ZOXEXIVO
А зачем?

Ну некоторые выражения можно будет сократить в несколько раз

Цитата Hsilgos @ 29.03.08, 11:36

А вообще, у нас в последнем семе на 5 курсе был веселый пропод. Проподавал препод "Историю математики".
И говорил он нам там удивительные вещи. В часности, что математика базируется на таких аксиомах, верность которых невозможно как доказать, так и опровергнуть.

Хм неужели препод мог нести такую чушь?
Как говорится почуствуйте разницу.
Аксиома - утверждение верность которого невозможно как доказать, так и опровергнуть. (Чушь несусветная)
Аксиома - это утверждение не требующее доказательства. (вот так и никак иначе)

Цитата ZOXEXIVO @ 04.04.08, 10:31

Ну некоторые выражения можно будет сократить в несколько раз

И что это даст?:

-Added 04.04.08, 12:24

Цитата Pavlovsky @ 04.04.08, 11:02

Аксиома - утверждение верность которого невозможно как доказать, так и опровергнуть. (Чушь несусветная)
Аксиома - это утверждение не требующее доказательства. (вот так и никак иначе)

В чем то вы правы, но в отношении аксиомы нет.


Теория состоит из аксиом и правил вывода.


Докозательство аксиомы есть аксиома.

Ну как? Например вместо выражения в 20 символов можно использовать только позицию а словаре. Так можно много чего сократить

Цитата ZOXEXIVO @ 05.04.08, 16:19

Ну как? Например вместо выражения в 20 символов можно использовать только позицию а словаре. Так можно много чего сократить

Так ничего нельзя сократить.

Добавлено 05.04.08, 16:50
Хотя смотрите, можно сархивировать всю войну и мир в 1 бит.

Закодируем 1 все войну и мир. ВСе остальное кодируем без изменения просто припишем слева один ноль.

---------

Получили крутой архиватор? Война и мир в одном бите, а все остальное на бит длинее.

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

Цитата

Аксиома - утверждение верность которого невозможно как доказать, так и опровергнуть. (Чушь несусветная)
Аксиома - это утверждение не требующее доказательства. (вот так и никак иначе)

А почему не требующее? В силу своей очевидности?

Добавлено 07.04.08, 20:47
esperanto

Цитата

Закодируем 1 все войну и мир. ВСе остальное кодируем без изменения просто припишем слева один ноль.

Я придумал просто
МЕГААРХИВАТОР! Позволяющий архивировать любую информацию в конечное (несравненно маленькое) число.
Берем любое иррациональное число (например число пи) и ищем первую входимость нашей последовательности в дробную часть этого числа. И нам остается только запомнить позицию, с которой начинается эта последовательность.
Естественно, чем длинее последовательность, тем сложнее найти совпадение.
Вопрос лишь в том, за какое время найдется это самое вхождение

Сообщение отредактировано: Hsilgos - 07.04.08, 20:52

Цитата Hsilgos @ 07.04.08, 20:41

А почему не требующее? В силу своей очевидности?

Математика наука абстрактная. Оперирует абстрактнми объектами. Почему аксиома не требует доказательства? Потомому что так захотели математики! Вы тоже имеете право любое утвержднеие объявить аксиомой.

Сообщение отредактировано: Pavlovsky - 08.04.08, 01:58

Цитата

Математика наука абстрактная. Оперирует абстрактнми объектами. Почему аксиома не требует доказательства? Потомому что так захотели математики! Вы тоже имеете право любое утвержднеие объявить аксиомой.

Цитата

Докозательство аксиомы есть аксиома.

Даже если б они захотели ПО ДРУГОМУ, то используя математический аппарат, который используется сейчас, они бы не смогли её доказать или опровергнуть

Цитата Hsilgos @ 08.04.08, 08:10

Даже если б они захотели ПО ДРУГОМУ, то используя математический аппарат, который используется сейчас, они бы не смогли её доказать или опровергнуть

Кого его?


Логика состоит из аксиом суть набор логических утверждений и правил вывода.



Аксиомой может быть любое лог утверждение даже противоречивое.

Цитата

Кого его?

Цитата

её

аксиому

Цитата

Аксиомой может быть любое лог утверждение даже противоречивое.

И каким образом это противоречит тому, что я написал?

Сообщение отредактировано: Hsilgos - 08.04.08, 08:38

Цитата Hsilgos @ 08.04.08, 08:10

Даже если б они захотели ПО ДРУГОМУ, то используя математический аппарат, который используется сейчас, они бы не смогли её доказать или опровергнуть

Cмогли бы.

Цитата

Cмогли бы.

Значит я что-то не понимаю... Зачем тогда аксиома, если ей можно доказать через какие-то более простые еденицы?
А тем более опровергнуть.

Что значит зачем Аксиома.


Теория это набор правил вывода и аксиом. ЭТо определение.


Вы не можете спросить зачем нужно определение квадрата если круг это множество точек.

Hsilgos

Цитата Hsilgos @ 07.04.08, 20:41

Я придумал просто
МЕГААРХИВАТОР! Позволяющий архивировать любую информацию в конечное (несравненно маленькое) число.
Берем любое иррациональное число (например число пи) и ищем первую входимость нашей последовательности в дробную часть этого числа. И нам остается только запомнить позицию, с которой начинается эта последовательность.
Естественно, чем длинее последовательность, тем сложнее найти совпадение.
Вопрос лишь в том, за какое время найдется это самое вхождение

Кстати мне нравиться этот алгоритм. А Словарь можно и заранее составить - степень сжатия определяется длинной фрагмента. + Рекурсивное применение алгоритма выдаст дополнительную компактность. Осталось расчитать отпимальные показатели . Кстати на этой же идее можно реализовать очень даже эффективный алгоритм шифрования.

Цитата esperanto @ 18.09.02, 08:00

ребята вы меня извините, но вы математику учили.

Не возможно написать ВЗАИМНООДНОЗНАЧНУЮ функцию из пространства с большим числом измерений в меньшее. (поясню нельзя написать архиватор который для ЛЮБОГО ввода в 9 символов кодирует в 8)

это достаточно очевидно ведь различных текстов в 9 байт некоторое число в степени 9, а в 8 байт тоже число в степени 8 , ясно что второе меньще первого.

так что очевидно что бессмысленно изобретать что-то сжимающее все и без потери

на самом деле вы от jpg зря отказались, происходит потеря только высоких частот, которые для   человека неинформативны, и если хотите что-то изобрести, то найдите базис по которому будет легче архивировать типа фурье иди адамара

с уважением

Народ если верить "теории большога взрыва" то информацию можно довольно плотно разместить.
Я сам занимаюсь сжатием и некоторые вектора данных(хаотичных) мне удалось сжать на 97%.
И я не согласен с esperanto по поводу что нельзя.
Все как мне кажется упирается в самые сокровенные неоткрытые уголки матемматики.
Это напоминает мою учительницу по матем.которая захлебываясь говорила что уравнение с 5 неизвестными не возможно решить кроме как методом Монте-карло,я доказал ей обратное.Так что дерзайте парни!!!

PS esperanto я как раз и пользуюсь большими размерностями при сжатии.Поменьше скептиса

Сообщение отредактировано: Dethlord - 30.04.08, 04:05

Цитата Dethlord @ 30.04.08, 04:02

Цитата esperanto @ 18.09.02, 08:00

ребята вы меня извините, но вы математику учили.

Не возможно написать ВЗАИМНООДНОЗНАЧНУЮ функцию из пространства с большим числом измерений в меньшее. (поясню нельзя написать архиватор который для ЛЮБОГО ввода в 9 символов кодирует в 8)

это достаточно очевидно ведь различных текстов в 9 байт некоторое число в степени 9, а в 8 байт тоже число в степени 8 , ясно что второе меньще первого.

так что очевидно что бессмысленно изобретать что-то сжимающее все и без потери

на самом деле вы от jpg зря отказались, происходит потеря только высоких частот, которые для   человека неинформативны, и если хотите что-то изобрести, то найдите базис по которому будет легче архивировать типа фурье иди адамара

с уважением

Народ если верить "теории большога взрыва" то информацию можно довольно плотно разместить.
Я сам занимаюсь сжатием и некоторые вектора данных(хаотичных) мне удалось сжать на 97%.
И я не согласен с esperanto по поводу что нельзя.
Все как мне кажется упирается в самые сокровенные неоткрытые уголки матемматики.
Это напоминает мою учительницу по матем.которая захлебываясь говорила что уравнение с 5 неизвестными не возможно решить кроме как методом Монте-карло,я доказал ей обратное.Так что дерзайте парни!!!

PS esperanto я как раз и пользуюсь большими размерностями при сжатии.Поменьше скептиса

Глупостями земля полниться.


Вы в своем посте только что заявили, что ВСЯ математика противоречива. Я конечно вас уважаю. Но я вам не верю.

Цитата Dethlord @ 30.04.08, 04:02

Я сам занимаюсь сжатием и некоторые вектора данных(хаотичных) мне удалось сжать на 97%.

Это возможно только если очень долго перебирать хаотичные векторы, пока не попадется удачный, и, как правило, в случае коротких векторов. Но если вы так уверены в себе, то у меня есть отличная идея! Dethlord, я предлагаю вам Пари!

Условия: я высылаю вам файл из случайных байтов длиной мегабайт. Вы высылаете мне в ответ файл, сжатый вашим алгоритмом (результатом сжатия должен быть один файл, имя и прочие атрибуты не важны для корректной распаковки), плюс распаковщик, который превращает сжатый файл в распакованный файл (те же условия, что и для сжатого файла). Если суммарный размер сжатого файла плюс размер распаковщика будет хотя бы на 10% меньше, чем размер исходного файла, я выплачиваю вам 5000 рублей. В свою очередь, если вы не можете обеспечить результат, 5000 рублей получаю я Согласны?

Если да, можем обсудить способ расчетов.

А откуда берется число в 10%????
В таких задачах ставят условие - хотя бы на один байт меньше )

esperanto Не возможно написать ВЗАИМНООДНОЗНАЧНУЮ функцию из пространства с большим числом измерений в меньшее, при условии сохранения размерности измерений

Цитата Хакас @ 30.04.08, 12:16

В таких задачах ставят условие - хотя бы на один байт меньше

Если для всех возможных входов, то да. А мы тут тестируем только один файл, так что просто подстаховка
В конце концов, если Dethlord научился сжимать файлы до 97% от первоначального размера, то сжав файл 4 раза он без труда наберет 10%

albom, по данным Dethlord'а он сжимал данные не до 97%, а на 97%. Т.е. заявлено сжатие в 30 раз.

Цитата Dethlord @ 30.04.08, 04:02

Я сам занимаюсь сжатием и некоторые вектора данных(хаотичных) мне удалось
сжать на 97%

Так что мои условия довольно-таки либеральны Впрочем, если это всего лишь опечатка, я готов опустить планку. Точную величину желаемого сжатия (не менее 1%, хотя чем больше, тем лучше) и размер файла готов обсудить, если Dethlord откликнется на мое предложение.

Добавлено 30.04.08, 14:12
P.S. хочу добавить, что я в состоянии без проблем выплатить этот проигрыш. Готов предоставить любые доказательства платежеспособности, хоть выписку со счета в банке, в которой виден текущий остаток. Так что если Dethlord не откликается только потому что сомневается в том, что увидит свой выигрыш, я готов обсудить возможные гарантии участникам.

Цитата Dethlord @ 30.04.08, 04:02

уравнение с 5 неизвестными не возможно решить

В общем случае действительно аналитического решения нет. Хотя есть частные случаи, допускающие аналитическое решение.

Метод Монте-Карло правда тут вообще ни при чем. Есть куча методов, позволяющих получить приближенное решение и быстрее и точнее.

Добавлено 30.04.08, 17:41
Аналогично и со сжатием. Можно придумать алгоритм, сжимающий определенный частный вид данных (текст например) лучше универсальных методов. Но на не текстах он скорее всего начнет проигрывать.

Судя по отсутствию ответов от Dethlord'а, моё пари не принято

Удалил все свои посты... Я на радостях стал писать много лишнего и даже то, что действительно работает. И минус мне за зря поставили! Больше в этом топике не участвую.

Цитата Navi1982 @ 12.11.09, 21:07

Удалил все свои посты... Я на радостях стал писать много лишнего и даже то, что действительно работает. И минус мне за зря поставили! Больше в этом топике не участвую.

Поздно удалили.

Но молодец.