Разное

... голову об стену задачу!

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

Посоветуйте, куда пойти лечиться!

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

А то ведь скоро рождество, потом Новый год, потом опять рождество, времени у многих вагон оказывается, если заранее не приготовиться, из рождественской недели есть риск выйти с изрядной головной болью :)

Также принимаются предложения по формату и протоколу ведения сего буйства!

я за. нутром чую будет интересно.

Грех такую тусовку пропустить.)

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

Может, это плохо?

>почему люди добровольно ломают голову над тем, что не имеет для них значения

хотя бы для того, чтобы развивать мышление

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

Что Вы можете сказать по этому поводу?

ПС. А что такое "умный человек"? Можете дать определение?

задача будет совершенно конкретная.

Оффтопик:
Почему плохо? Мне кажется, просто склад характера разный, психика другая.
При чем в данный момент, а не вообще.

Вы полагаете, еще одна тема на форуме так дорого обходится?
У меня возможности вынести эту ветку в отдельную тему нет. А так бы с удовольствием подискутировал.

Вы полагаете, еще одна тема на форуме так дорого обходится?

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

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

>>почему люди добровольно ломают голову над тем, что не имеет для них значения.

Когда большую часть времени проводишь за решением задачь, которые так или иначе уже когда то решались (издержки профессии), очень хочется чего-то нового, неардинарного.
Иначе теряется вся прелесть такого увлекательного дела, как программирование.

Именно потому программисты и толкутся на форумах, жадно ожидая интересного вопроса.

Ну а когда задачу ставит сам Trianоn, тут вообще глупо упускать возможность
А) Размять мозги
Б) Узнать кучу нового
В) Получить порцию адреналина от азарта соревнования
Г) Получить в репозитарий какой то новый, достаточно грамотный релиз. Ибо он будет разобран по косточкам.

Так что тут интерес совершенно меркантильный и очень даже имеет значение.

> не имеет для них значения.
Мне кажется, вы немножко не то слово употребили.
Ну да ладно. Вот смотрите - занимаюсь я в данный момент разработкой сайта, и большинство алгоритмов у меня в голове уже есть. Т.е. я в течении еще двух-четырех недель буду просто набирать код - затухнуть можно.

Отличное предложение. Я тоже попытаюсь, если задача будет.

если она будет интересной и полезной, то я за

Хоть работы и много, но любопытство всё равно не даст работать, если решу пропустить такую тему :)
Принимаю участие!

На счёт протокола предлааю сделать так:
- предложенное решение может относиться к одному из трёх типов: не решает задачу, решает задачу частично, решает задачу полностью.
- к какому типу отнести решение - решает Trianon, если восле вынесения вердикта возникает спор, то вердикт выносится заново публичным голосованием.
- определить дату, по достижении которой новые решения приниматься не будут. После наступления DeadLine определить победителей в каждой из категорий решений(да, победитель в категории самое нерабочее решение пусть тоже будет :). Победители пусть выбираются публичным голосованием.

> Победители пусть выбираются публичным голосованием.
И по номинациями еще разделить: самый быстрый и нересурсоемкий код, самый аккуратный (читабельный), самый защищенный (если будет работа с пользовательскими данными) и т.д.

Я бы поучаствовал :)

Да, можно ещё и такое деление добавить. Причём эти номинации можно добавить внутри каждого из типов (кроме, наверное, "нарабочее решение") решений, которые я предложил, а можно сделать отдельными номинациями, не зависящими от типов решений.

Думаю, это уже по ходу дела нужно будет решить (если, конечно, такой регламент одобрит большинство).

P.S. За прошлое сообщение извиняюсь - я там опечаток много сделал, а отредактировать уже нельзя.

Больше внимания стоит уделить самой задаче, по крайней мере на этом этапе)

Можно, я тоже поучаствую? У меня когда-то получалось.

Хотелось бы уточнить. Это конкурс или просто головоломка?
Если конкурс, готов предоставить небольшой призовой фонд. )

Готов скинуться в призовой фонд.

Друзья!

Спасибо всем за поддержку, вы ж понимаете, без вашего желания затевать очередную авантюру смысл невелик.
Я очень надеюсь, что к нам присоединятся другие посетители.
Я также буду только за, если присоединится cheops, в любом качестве, но видя, что со временем унего швах, так или иначе отнесусь с пониманием.
Несколько отличий от предыдущих забегов.
Минусы. Задача сложная. В основном тем, что для потребуется знание того, как устроена пара видов файлов. Один из них довольно простой, другой, который посложнее, более чем распространен, но ни разу не текстовый, и напрямую в Web применяемый нечасто.

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


Вы можете подумать,
а) что у меня уже есть решение задачи.
Это не так. Кончно я знаю, как ней подходить, но мне придется решать со всеми.
И конечно, я не претендую на место.
б) что мне нужно это по работе, заказу, или еще как.
Нет. Если бы такое происходило, я бы заказ делал, а не игрища устраивал.
Так что в результате у каждого будет полезный код, навыки и масса впечатлений.

Если я вас не испугал, неспешно буду готовить формулировку условий.

Я очень надеюсь, что вы не испугались.

Делитесь мыслями по поводу услышанного. :)

PS. Да, всем кто спрашивал, а можно?
Не можно, а нужно! :)

Меня не испугали :)
В остальном - остается ждать формулировки задачи.

Ах да, про призовой фонд - мне, в общем-то, это не важно - в данном случаи интереснее само участие. Но если решим с денежными призами - готов скинуть взнос :)

Крайне интересно. Недавно пытался сделать средствами PHP пароль на ZIP налету, теперь даже жалею, что нашел обходной вариант.

Там схожая была задача - модификация совсем не текстового файла.
Я в теме.

PS По поводу призового фонда - это собственно не ради выигрыша, а ради привлечения массовки. Хотя конечно это все совершенно неважно.

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

UPD. В призовой фонд я скинуться тоже готов.

Небольшая преамбула.

Вскому известно, что В php входит библиотека работы с изображениями Gdlib.
Библиотека эта неплохо работает с большинством форматов, поддерживающих полноцветные и палитровые картинки, но вот с классом двуцветных - черно-белых изображений у нее туговато.
Фактически, единственный формат, в котором можно получить сырой чернобелый образ, это формат Wireless Bitmap (.wbmp) и соответствующая функция imagewbmp().
А меж тем, черно-белые изображения во многих случаях вполне себе полезны, и при оптимальном выборе формата файла могут храниться очень компактно. Типичная страница документа А4 (210x297мм) в разрешении 300 точек на дюйм сжимается до размеров порядка мегабайта, если её сохранять в JPG, и до 30...70Кбайт, если хранить черно-белой сжатой без потерь в одном из факсимильных форматов.
На практике единственным распространенным и усоявшимся форматом, позволяющим хранить такие изображения является TIFF. Вот только выводить данные в файл TIFF Gdlib не умеет.

В формате TIFF предусмотрены схемы компрессии черно-белых изображений, которые с одной стороны, как я показал выше, дают весьма впечатляющие результаты, с другой, для реализации которых не требуется владение какими-то сверхмудреными знаниями в области высшей математики и т.п. Всё что нужно уметь делать, это сосчитать черные точечки, сосчитать белые точечки и т.п.
Фактически в TIFF для хранения черно-белых изображений помимо варианта #1 (вообще без сжатия, то есть как в исходном Wireless BMP) предусмотренно 3 методики компрессии:
#2 - Huffman RLE (описанная в спецификации формата TIFF)
#3 - CCITT Fax Group 3 (описанная в документе ITU-T, recomendation T.4)
#4 - CCITT Fax Group 4 (описанная в документе ITU-T, recomendation T.6)

Как это выглядит на примере IrfanView, и какие дает результаты, можно посмотреть в аттаче к посту :))
Сразу отмечу, что методика #2 - самая простая (если не считать #1 :) , #4 - самая впечатляющая по сжатию, #3 - самая сложная, .(так как фактически #4 - это упрощенная #3) и по большому счету, нам не интересная, так как основной упор в ней сделан на работу на аналоговых телефонных линиях с высоким уровнем ошибок, а вовсе не на степень сжатия. Зато по ней есть качественный перевод на русский язык :)

Итак, условия задачи очень просты:

Общая часть: Есть  (для простоты и ясности - в текщем каталоге со скриптом) файл image.wbmp  в формате Wireless BitMap с черно-белым изображением произвольного размера и содержания. Нужно получить (там же) файл image.tif в формате TIFF с тем же размером, содержимым,  в одной из черно-белых схем компрессии, предусмотренной стандартом. Предлагается написать скрипт, который бы выполнял такое преобразование. Требования к скрипту, частные:  - сжимать картинки по возможности сильнее. - работать с картинками произвольного размера (то есть от очень маленького, до громадного) и как обычно, общие:  - работать быстро. - требовать минимум ресурсов. - иметь опрятный вид, легко читаться, быть понятным.

Для ленивых - ссылки на документы:

Общие принипы кодирования черно-белых изоражений:
http://ru.wikipedia.org/wiki/Бинарное_изображение

[url]1. Формат WirelessBitMap:
http://ru.wikipedia.org/wiki/Wbmp[/url]
http://www.wapforum.org/what/technical/SPEC-WAESpec-19990524.pdf

2. Формат TIFF
http://ru.wikipedia.org/wiki/TIF
http://el-izdanie.narod.ru/gl4/4-4.htm
http://partners.adobe.com/public/developer/en/tiff/TIFF6.pdf
Схема алгоритм Huffman-RLE компрессии фиксированной таблицей CCITT Group 3:
http://lib.ru/TECHBOOKS/ALGO/VATOLIN/algcomp.htm#_Toc448152504

3. Рекомендации ITU-T http://www.itu.int/itu-t/recommendations/index.aspx?ser=T
3.1. Рекомендация Т.4 http://www.itu.int/rec/T-REC-T.4-200307-I (имеется русский вариант)
3.2. Рекомендация Т.6 http://www.itu.int/rec/T-REC-T.6-198811-I (перевод содержательной части можно найти в рекомендации Т.4, параграф 4.2.1.3 и 4.2.5, стр 9-16)

Не в бровь, а в глаз - всегда недопонимал все эти изображения, средства работы с ними и т.д. =\
Теперь есть причина подружиться с ними. Или наоборот, рассориться навсегда.

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

Забытый в пылу красноречия аттач. ===>

Ну и подразумевающиеся комментарии к условию.
Скрипт может применять любые стандартные функции, но не может пользоваться внешними утилитами, вроде imagemagic. Да и в чем был бы смак, если б мог?

Зачем вся эта кухня, если любой текст (картинка), если уж на то пошло, и не важно, jpeg, png ли, можно превратить с помощью доступных в GD фильтром до нужного состояния, а затем в палитровое двухцветное, и выводить как gif или png.

Я где-то что-то говорил про выводить?
Выводят такие документы обычно на принтер.
Иногда - в OCR систему.

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

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

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

Вы название темы прочли? Просто для мозгов.
Когда спортсмены ядро толкают, им никто не говорит, что гранату метнуть сподручней.

Смысла не вижу тогда, упоминать о "инвалидности" GD и печати. Ибо GD вполне справится с этим без всяких головоломок излишних.

>Смысла не вижу тогда, упоминать о "инвалидности" GD и печати. Ибо GD вполне справится с этим без всяких головоломок излишних.
Это означает лишь, что Вы меня не поняли.

Возможно ;-)

И надо ж так! Под Новый год!
Назад пятьсот, пятьсот вперёд

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

3. Понимаю, что вопрос глупый, но обстоятельства вынуждают его задать.
Что означает этот знак? Сумма? Как читать это выражение? (в аттаче)

4. Это не вопрос - предложение.
Мне кажется, надо было бы выложить какое-то фото - одно для всех и пусть все его сжимают. Можно два фото - маленькое и очень большое.
Просто искала файл .wbmp в Сети - не нашла.

Можно теперь отвлеченно от общей идеи не в другую, а в соседнюю степь)
Можно попробовать сделать кеширование с помощью этого алгоритма. Если на сайте есть
статические страницы и обновляются они нечасто, генерируем html-страницу, сжимаем ее,
чтобы место не занимала, а при надобности декодируем. Насколько это целесообразно будет?

>Вопросы.
>1. Если сжимается изображение, то сжимается ли его заголовок и вся сопутствующая служебная информация(ширина, длина, тип и т.д.)?

Подразумевалось получить на выходе живой файл в формате TIFF.
стандарт формата TIFF никогда не предполагал сжатия заголовка.
Собственно в заголовке сжимать просто нечего - там 8 байт всего, но каталог файлов изображений (image file directory) тоже никто никогда не сжимал.

>2. Есть два варианта кодирования по алгоритму Хаффмана - статический(классическое сжатие) и динамический(адаптивное сжатие), какой брать?

Стандартом (Section 10 вышеуказанного документа) предусмотрено исключительно статическое сжатие длин смежных участков пикселей по наперед посчитанным и явно заданным (в стандарте же) таблицам, приведеным в приложении (table 1/T.4, table 2/T.4)

>Статический применяется чаще, динамический уступил место каким-то более скоростным алгоритмам.
>Динамический сложнее в реализации, но чего тут сложного-то, если у нас бинарное изображение и всего два символа - 1 и 0, тут дерево в три узла будет, если я правильно суть поняла.

Всё еще проще. дерево уже составлено, посчитано и преобразовано в кодовые слова.
Я же сказал - никакой математики не требуется. Нужно только сжать.


>3. Это не вопрос - предложение.
>Мне кажется, надо было бы выложить какое-то фото - одно для всех и пусть все его сжимают. Можно два фото - маленькое и очень большое.
>Просто искала файл .wbmp в Сети - не нашла.

Вот эта пара строк строка спасет страждущих:

<?php   $im = imagecreatefromgif($_GET['in']);    var_dump(imagewbmp($im, $_GET['out'])); ?>

если кто совсем сонный, сейчас прикреплю файлик. ====>


>Можно теперь отвлеченно от общей идеи не в другую, а в соседнюю степь)
>Можно попробовать сделать кеширование с помощью этого алгоритма. Если на сайте есть
>статические страницы и обновляются они нечасто, генерируем html-страницу, сжимаем ее,
>чтобы место не занимала, а при надобности декодируем. Насколько это целесообразно будет?

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

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

Все три методики благополучно сдались!

И хотя код выглядит отвратно, и кишит кусками отладочного процесса, как клопами, все же сатисфакция полнейшая :))

аттач послужит пруфлинком . :)

Уфф. Можно идти накрывать стол :))

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

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

Да я уж подумал, что надо было сперва собрать дотаций на приз
Тогда страусы точно подумали бы, стоит ли голову в песок совать.
:))

Перечитал свой пост и понял, что истолкован он может быть двояко.
>>В двойне стыдно от того, что девушка оказалась самой продуктивной.
Я ни в коей мере не имел ввиду, что девушка может быть худшим программистом, чем мужчина.

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

Я имел ввиду, что крайне стыдно быть таким безответственным, особенно на фоне "слабого" пола. Есть огромный риск самому оказаться в рядах слабых, тем более, когда в соперниках такой сильный программист, как Лена

Так что, господа программисты, есть повод задуматься. Я - уже.

>Если вдруг это было истолковано неверно, приношу свои извинения.

Николай, не волнуйтесь, все истолковано верно) Мне на мой слабый пол(это почему это он слабый?) никогда здесь скидки не делали, Trianon пинал наравне с остальными, за что ему в очередной раз спасибо.

>Я имел ввиду, что крайне стыдно быть таким безответственным, особенно на фоне "слабого" пола.

Почему бы не начать исправлять ситуацию уже? Я на три недели вынуждена сделать перерыв, есть возможность догнать ) Тем более, что если делать не в тягость, а в радость, то решение задачи прийдет быстрее, чем вы думаете)

Да, задача сложная. Но интересная. И практическая польза от нее есть. Большая. Мануал в поисках нужных функций исходите вдоль и поперек уж точно ) Потому как там полет фантазии может пойти в такую сторону, о которой в начале задачи даже не подозреваешь )

>Так что, господа программисты, есть повод задуматься. Я - уже.

Задумываться надо не над тем, кто будет участвовать и как будет участвовать , а над самой задачей. И если что-то не понятно, хотя бы начать задавать вопросы. Какими бы глупыми и тупыми они не казались. Главное здесь - двигаться вперед, пусть маленькими шажками, но вперед, а не стоять на месте.
И напоследок. Trianon уже выложил рабочий вариант. Неужели не хочется написать то же? А может, даже лучше? Если вам дается шанс ступить на ступеньку выше, повысить знания, почему бы его не использовать?

PS. В аттаче - картинки wbmp разного размера, на которых тренировалась я.

>...Trianon уже выложил рабочий вариант....

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

Это следствие того, что писал я его, как привык писать на С, экономя каждый байт, и например, двухкилобайтовый буфер для факсовой строки в 1728 пикселей считая непозволительной роскошью.
Понятно, что на php так не пишут, (сейчас и объемы в десятки мегабайт (т.е. на 4 порядка!) почему-то никто бедой не считает) но кардинально отойти от привычки у меня не получилось.
Собственно, подспудной идеей этого шоу было еще и сравнить свой подход с подходами других участников, и сделать оргвыводы, в частности, для себя.

Так что я по прежнему жду конкурентов. И полагаю, что буду ими бит :)

Первую часть, без компрессии, осилила :)
Предполагается, что создается TIFF с одной IFD.
При построении взяты основные теги - те, в которых идет значение по умолчанию, не брала.
И предполагается, что данные в тегах идут только типа SHORT и LONG.

Гуд :)
теперь значит про нудные и противные форматы файлов можно забыть, и решать действительно интересную часть задачи :)