| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > конкурс для кодеров :) |
| Автор: oleg1973 6.8.2004, 19:09 |
| ну так что будем делать конкурс или как? задание уже есть написать упаковщик для bmp 1024*768*24 бит оцениватся будет скорость и степень сжатия, естественно надо и распаковать потом алгоритмы типа jpg и прочие с потерей данных не рассматриваются язык програмирования неважен, наличие исходников приветствуется но не обязательно (ну вдруг там у вас суперпупер идея для комерч. использования) кто переплюнет RAR по размеру и скорости получит 5 + в рейтинг кароче делаем ехе main.exe -p somefile.bmp пакует main.exe -d somefile.pak распаковывает картинку для паковки выберем всеобщим голосованием вопрос модераторам может данный топик перенести из флейма? както он уж не флеймовый |
| Автор: Borland_Delphi_6 6.8.2004, 20:52 |
| oleg1973 Поучавствовать не смогу, но с удовольствием понаблюдаю за ходом событий |
| Автор: oleg1973 6.8.2004, 21:07 |
| значт так вот картинка http://digilander.libero.it/oleg1973/Water%20lilies.rar ужата раром до 993 035 bytes в нормальном виде 2 359 350 bytes принимаются работы до 1 сентября между делом можете сообщать результаты промежуточные, типа для подогрева публики |
| Автор: -=::BlackCat::=- 6.8.2004, 22:12 |
| krasivaja kartinka, kst. u menja ee poka chto udolos sgat do 969 KB (993.030 Bytes) Добавлено @ 22:14 Xa dage do 825 KB (844.918 Bytes) |
| Автор: chipset 6.8.2004, 22:16 | ||
И пару штук баксов за проданные архиваторы До первого сентября говоришь? Я вот немного разберусь с текущими проектами и попробую зачудитЪ |
| Автор: oleg1973 6.8.2004, 22:19 | ||
-=::BlackCat::=-
чем? |
| Автор: Borland_Delphi_6 6.8.2004, 22:22 |
| oleg1973 Всякие CAB-MAN'ы и WinAc'ы вроде лучше рара сжимают |
| Автор: -=::BlackCat::=- 6.8.2004, 22:43 |
| kagetsja chto-to krupnoe namechaetsja, narod ne sowetuju wikladiwat ishodniki otkrito, nu a esli ug tak hochetsja no nuna nowij razdel, gde narod tolko za 200-250 nahoditsja mog bi, inache washi ideii mogut pribawit tjagesti chugim kormanam |
| Автор: oleg1973 6.8.2004, 22:56 |
| значит ставим новый предел 844.918 Bytes |
| Автор: maxim1000 6.8.2004, 23:34 | ||||
jpeg может работать в режиме без потерь Добавлено @ 23:37
любой мало-мальский прдуманный алгоритм сжатия изображений переплюнет Rar, который универсален, именно из-за своей специализации |
| Автор: oleg1973 6.8.2004, 23:37 | ||
зато и жмет при этом не особо |
| Автор: Се ля ви 7.8.2004, 00:23 |
| А если чувак надумает запихнуть данную картинку в екзешник, то сможет вообще ужать до 0 байт - только сверять имя файла и выдавать картику изнутри себя с размером 844.918 по раровскому, скажем, алгоритму |
| Автор: cardinal 7.8.2004, 01:31 | ||
Как скорость будет замерятся, если только main.exe есть? А вообще с удовольствием приму участие в конкурсе. Если что скиньте сообщение по PM. |
| Автор: -=::BlackCat::=- 7.8.2004, 01:35 | ||
Се ля ви
etu chifru RAR ne dostig, eto bil WINACE cardinal ti kagis na VB pishesh mnogo, popitaisja ego propihnut w chislo moshnih jazikow |
| Автор: oleg1973 7.8.2004, 01:42 |
| cardinal думаю что скоростью в данном конкурсе можно и пренебреч |
| Автор: cardinal 7.8.2004, 01:44 |
| Се ля ви, упаковщик - это не разбухальщик. |
| Автор: cardinal 7.8.2004, 02:03 | ||
| oleg1973, ну принебречь, так принебречь, но тогда конкурс несерьезным становится. Так как картинка одна и таже, то соответственно можно под нее подстроится и выбрать алгоритм, который лучше всего ее ужимает. Тогда надо взять эту картинку для начала, а тестить потом по нескольким (причем допустим только тебе известным), тогда будет хоть на что-то похоже. С другой стороны, если мы принебригаем временем, то можно вообще написать десяток алгоритмов и программа будет пять минут думать, а потом выдаст лучший результат. Тоже несерьезно. Вобщем я за время и за качество. Если время не играет никакой роли, то мне уже участвовать не интересно становится по описанным выше причинам.
-=::BlackCat::=-, не беспокойся. То с чем я пришел на это побоище написано (мною) на asm'e А вообще на VB пишу в последнее время очень мало. В основном только для форума. |
| Автор: maxim1000 7.8.2004, 10:00 |
| предлагаю определиться с требованиями более конкретно: потери тут есть два варианта: допустимы и нет если потери допустимы, то нужно указать, как искажение влияет на критерий оценки программы класс изображений вот действительно думал написать прогораммку с прицепленным файлом и показать, как я сжимаю его в 1 байт например, для естественных изображений больше подходят алгоритмы вроде jpeg, для искусственных gif и т.д. так что давайте определимся предложение: давайте просто возьмем какой-то сайт с обоями (например, на тему природы) и будем сжимать их проверять будем на нескольких изображениях скорость как она учитывается, как сильно влияет на критерий оценки программы, что важнее: скорость сжатия или скорость восстановления размер программы как оценивается, возможно, ограничен (еще один способ бороться с прицепленными файлами ---- я бы предложил сжатие без потерь - тогда их не нужно оценивать, а то совсем неочевидно, как именно это делать |
| Автор: RA 7.8.2004, 10:22 |
| oleg идея хорошая но, почему именно картинку я к примеру могу написать архиватор (JPEGconВертор |
| Автор: oleg1973 7.8.2004, 12:45 |
| и так правила 1) сжатие без потерь, должно соответствовать 1*1 2) пока жмем тестовую картинку, в финале будет сделан тест на других картинках 3) время сжатия тоже будем оценивать 4) основная оценка размер выходного файла к примеру баллы так можно начислить размер+(время*1000) 5) размер ехе на баллы не влияет время конкурса до 1 сентября RAdmin шансы у нас всегда есть а JPEGconВертор один фиг без потерь не сделает |
| Автор: gepard 7.8.2004, 14:33 | ||||
Обязательно так? А если я оформлю в Delphi?
Не забывай, что он комерческий. Да и вообще, задолбаешься писать. Там у него 8 уровней сжатия. Хотя я подолбаюсь. Всё равно заняться особо не чем. |
| Автор: cardinal 7.8.2004, 15:49 | ||||
Я бы только немного уточнил. Баллы бы высчитывал так: (Размер картинки после упаковки в байтах + (время в секундах на упаковку + на распаковку) * 100000) / 100000 и округлить до второго знака после запятой Например: размер картинки после упаковки 563400 байт время на упаковку 1.234 сек время на распаковку 3.542 сек получаем: (563400 + 123400 + 354220) / 100000 = 10.4102 => 10.41 балла
Размер картинки на размер exe тоже. |
| Автор: gepard 7.8.2004, 16:06 | ||
Чего-то я пропустил этот пункт. А время-то зачем? Время выполнения может зависить от ОЧЕНЬ многого. Или тогда тестить надо всё в одно время и на одной тачке. |
| Автор: -=::BlackCat::=- 7.8.2004, 18:10 |
| gepard delphi proigrat 100% po wremeni, dumaju dage esli ti cherez ASM wstavki delat budesh |
| Автор: <Spawn> 7.8.2004, 18:52 |
| -=::BlackCat::=- Ни чего подобного - прочитав пол книги Криса Касперски "Оптимизация работы с памятью"(Ну просто супер книга - всем советую, написана классным языком и очень реально оптимизировать работу с памятью можно научиться - я проверял уже пару алгоритмов и даже в интерпертаторах есть прирост!!!!) я думаю, смогу оптимизировать алгоритм по скорости в несколько раз, если буду его делать(Все зависит от свобоного времени - на данный момент я делаю 2 проекта и еще работаю) |
| Автор: -=::BlackCat::=- 7.8.2004, 19:09 |
| <Spawn> dawai bodet ochen interesno gljanut |
| Автор: Monty 7.8.2004, 19:18 | ||
Включи оптимизацию |
| Автор: gepard 8.8.2004, 05:33 |
| Блин, неужели придётся асм ковырять и с++ подключать... |
| Автор: oleg1973 8.8.2004, 12:32 |
| так ну все хватит трепатся, поехали! 3...2...1... старт! |
| Автор: RA 8.8.2004, 13:51 | ||
| Пардон, я тут по делу выскажусь: Но вые пределы_ Мне удалось раром сжать в 969 КБ (993 030 байт) И WinAce-сом в 816 КБ (836 300 байт)
Сынок Делфи это Сила |
| Автор: -=::BlackCat::=- 8.8.2004, 16:47 |
| RAdmin naschot delphi ja verju, prosto vidno ne figa ne umeju optimizirovat, kak ti WINACEom umudrilsja eshe 9 KB ubit? |
| Автор: oleg1973 8.8.2004, 18:02 |
| как уже говорилось выше, язык в данном конкурсе не важен, хоть на Qbasic пишите главное результат ну и желательно свой алгоритм,так как переписывание заново LZW не совсем то что требуется мой результат пока шибко скромный примерно 1,500 , но будем старатся |
| Автор: RA 9.8.2004, 05:29 | ||
WinAce версии 2.6B. если у тебя таже версия то нужно будет порыться в настройках компресси. Добавлено @ 05:35 oleg1973 Алгоритм сжатия PPM (а он круче зипа) выдаёт: 1,45 МБ (1 521 193 байт) поэтому я думаю, что дальше этой цифры никому не светит уйти. |
| Автор: oleg1973 9.8.2004, 11:09 | ||
ну а как же WinAce c 800kb ? переписав LZW олучим примерно тожесамое , а PPM тоже не панацея |
| Автор: maxim1000 9.8.2004, 11:23 | ||
и в чем тут крутость? до такого размера сожмет любой энтропийный кодировщик по той простой причине, что картинка непростая если внимательно посмотреть на значения пикселей, можно увидеть, что, скорее всего, камера, которой все этой снимали, была 5-ти битной Добавлено @ 11:25 кстати, как мне кажется LZW и прочие словарные методы тут не пройдут - это же вам не текст |
| Автор: oleg1973 9.8.2004, 16:53 |
| так пора список участников составить 1) я-Oleg1973 2) cardinal 3) ? |
| Автор: maxim1000 9.8.2004, 17:06 | ||
а зачем? кто пришлет, тот и участник |
| Автор: cardinal 9.8.2004, 17:26 |
| oleg1973, дописывай cardinal |
| Автор: RA 9.8.2004, 20:58 | ||
До винАса как до Генуи из Милана пешком. PPM это и есть переписанный zLIB, причем не за короткий срок. и поскольку единсвенное что светит каждому из нас ( переписать zLIB |
| Автор: AndyY 9.8.2004, 23:29 |
| картинка была предварительно сжата JPEG, а потом распакована. это очевидно из гистограмм по YUV. Вопрос - мы будем пережимать уже сжатые до нас c потерями картинки или пишем общий алгоритм? |
| Автор: RA 9.8.2004, 23:56 |
| AndyY забей на картинку, она просто как ориентир для того чтобы можно было похвастаться. |
| Автор: GrayCardinal 10.8.2004, 12:17 |
| oleg1973 запишите в список участников... буду RLE изучать |
| Автор: oleg1973 10.8.2004, 14:30 |
| RAdmin нееее PPM и zLib этож как пуля и г... отличатся AndyY как справедливо заметил RAdmin картинка так для орентиру ГОСПОДА УЧАСТНИКИ! еще раз напоминаю что жмем картинку, и это дает нам некие перспективы, если учитывать особенности именно картинки а не просто набора данных |
| Автор: GrayCardinal 11.8.2004, 10:50 |
| oleg1973 Трабл возник - картинка не грузится. Как Линуксоид - качал в Линуксе, а мне она выдает ее просто как текст (смотрит его и все тут") пробовал даже wget-ом - нифига, "неправильный формат". если не сложно, зазипь ее... А то все по ней меряют результат... Какие готовые алгоритмы можно использовать а какие нет ? Если я сам напишу то-же дерево Хаффмана (простой линукс-gzip), Пройдет на конкурс ? Или что сможешь реализовать без сдирания с уже готового кода (не алгоритма) то и делаешь ? |
| Автор: oleg1973 11.8.2004, 18:45 |
| задача ужать как можно лучше можеш и Хаффмана написать, я к примеру сижу вот свой выдумваю пока тяжко |
| Автор: chaos 13.8.2004, 15:00 | ||
| а че за картинка?? Добавлено @ 15:00
дайте посмотреть |
| Автор: lynx_916 13.8.2004, 22:15 |
| если у тя ХР, не ищи, она где-то по папкам. Водяные лилии называется |
| Автор: chipset 13.8.2004, 23:40 |
| .... я не опоздал, нет? набор ещё не закончился? |
| Автор: cardinal 14.8.2004, 00:00 | ||
Я думаю главное во время выложить работу. |
| Автор: oleg1973 14.8.2004, 13:30 |
| ну че результаты у кого какие? |
| Автор: GrayCardinal 18.8.2004, 15:22 | ||
почитай - ноль. только много интересного узнал и все. В общем простой модифицированный RLE теоретически может ужать на метр (по максимуму). Одинаковые пикселы искать нереально. Даже если по шесть старших бит совпадение искать. вот если бы потом выкинуть младшие два бита... мммммм не такие ужо и потери, по-мойму |
| Автор: shedon 19.8.2004, 19:47 | ||
| а как вы время собираетсь замерять, верить экзешнику или как, может тогда лучше в длл зделать ? допустим длл будет экспортировать функцию int Compress(char *psInputFile, char *psOutpFile); и int Decompress(char *psInputFile, char *psOutpFile); в случае успеха функция возвращает 1 иначе 0 тогда напишем прогу exe, естсетвенно с открытым кодом для проверки dll и она же будет и время замерять ?
А как тогда определить, что алгоритм не варованный ? |
| Автор: cardinal 19.8.2004, 23:39 | ||||||
то есть наоборот
Кто-нибудь может этот файл dll в исходнике сюда выложить? Мы тогда возьмем эту рамку и вместо
напишем свои функции. Тогда будет у всех одинаково. |
| Автор: GrayCardinal 20.8.2004, 07:25 | ||||
а в чем проблема ? не думаю что стоит считать ms, просто прогнать через прогу N (> 1000
не думаю что все "зажмут" алгоритмы... если он не круче JPG, конечно... а по алгоритму видно будет - на сколько он ворованный... |
| Автор: shedon 20.8.2004, 09:34 | ||||||
А что выкладывать каждый будет писать на своём языке, это тогда надо выкладывать на всех языках...
Почему наоборот ? Хотя это уже кому как больше нравится, но, вроде, принято именно так делать... |
| Автор: cardinal 20.8.2004, 16:28 | ||||||
Я привык, что не ноль - это ошибка, вот как здесь например (MSDN):
Да и вообще если создать в том же MS VS компиляторе новый проект, то он вывалит парочку файлов, а в main написано следующее:
То есть как бы: нет ошибок - return 0. |
| Автор: shedon 20.8.2004, 17:52 |
| Ну это крорее усключение из правила, т.к. 0x00 Это нормалтьное завершение потока/процесса, аты посмотри что возращают все апи функции... Честно говоря у меня был один большой проект, в котором я по глупости зделал, что 0 это нормальное завершение функции, а ысе апи фуенкции у меня возвращали 1, не очень красиво получилось, после этого я взял за правио, что любая функция в случае успеза должна возвращать 1, хотя это всё на любителя. Но это всё оффтоп. А по поводу сабжа, я думаю тут врядли удасться кому либо изобрести новый алгоритм, скорее всего будет некая модификаци/оптимизация одного из известных алгоритмов.... |
| Автор: GrayCardinal 21.8.2004, 10:09 |
| Люди, поделитесь успехами ! А то вырезано цензурой тут с изобретением нового алгоритма и ничерта... у кого что-нибудь рабочее уже есть ? |
| Автор: cardinal 29.8.2004, 12:47 |
| Похоже, что я не укладываюсь в сроки На это появилось по ходу дела две причины: 1. оказалось, что то что я хотел использовать было сделано мной для 4 и 8 битных bmp'шек. С 24 надо придумывать другой способ сжатия. Когда я попробовал сжать по принципу, того каким можно ужать (причем неплохо) 8 битные картинки я получил файл на 100 Kb больше, чем тот который сжимал 2. как всегда напряг со временем Вот так-то... Можно было бы взять что-нибудь готовое, но это было бы нечестно. А на то, чтобы прочитать на чем построены другие (не те которые я уже делал) алгоритмы сжатия и их реализацию времени к сожалению нет... Если бы мы сжимали 8 битную картинку... |
| Автор: oleg1973 29.8.2004, 13:09 |
| я сделал так разбиваем на RGB делаем кусок памяти А равный размеру картинки/8 тоесть 1024*768/8 зануляем его потом берем наш цвет R примеру находим все 0 и ставим соответствующие им биты в куске А и так до 255 получим 0xff кусков заполненых 0 и коегде 1 можно ужать даже RLE и так же для G и B осталось додумать суперRLE так как в данный момент результат не особо 1100 кб даже стыдна перед winace |
| Автор: Girder 30.8.2004, 13:39 |
| oleg1973 я тоже не успеваю. Может и правду сроки продлить? |
| Автор: oleg1973 30.8.2004, 15:23 |
| ну давай продлим на скока? |
| Автор: Girder 30.8.2004, 16:31 |
| Ну я думаю не более чем на месяц |
| Автор: Sardar 30.8.2004, 22:34 |
| Не знаю даст ли это хорошее сжатие: BWT сжатие(сдвиг/сортировка) - получаем данные лучше сгруппированные по однотипным значениям, сжимаем методом RLE(или круче PPM, но это сложно), анализируем данные, находим участки чисел разница которых не велика(оценивать лучше как 16, 24 битные значения), для ущастков задаем смещение, а затем небольшие значения относительно смещения(это даст при хорошем раскладе ~25% сжатия). Jpeg не догонать, но rar, ace наверное метод сделает. Добавленно: 25% в смысле для простого сжатия участки/смещения, сколько будет все сразу сказать трудно. |
| Автор: oleg1973 31.8.2004, 09:35 |
| Sardar джепг не в счет там с потерями, а тот который без потерь джпег жмет не лучше рара |
| Автор: shuricus 27.9.2004, 06:55 |
| Народ, а че, уже всё закончилось? Тогда где можно посмотреть результаты? Если же нет, то я тоже хочу поучаствовать :) |
| Автор: cardinal 27.9.2004, 08:15 |
| Я все таки схожу с динстанции, т.к. не хватает времени... |
| Автор: asdf 29.9.2004, 21:07 |
| кто-нить получил меньше 794287? |
| Автор: chipset 30.9.2004, 02:58 |
| я уже месяц здесь не был, вообще времени НЕТУ... |
| Автор: Girder 1.10.2004, 11:46 | ||
|
| Автор: shuricus 1.10.2004, 13:34 |
| у меня пока ~810 000 :) но и то только потому, что картинку вы выбрали не фонтан - она слишком гладкая (выглядит как получена из 800x600 ресайзом). |
| Автор: oleg1973 1.10.2004, 17:02 |
| у меня как я уже писал примерно 1100 кб будем думать |