В субботу наблюдал занятное, привычное, но всё равно расстраивающее явление.
Сидит шобла моих любимых деток-восьмиклассников. Каждый из них по отдельности - человек весьма тямущий и толковый. Но когда они сидят вместе - шиш мне. Не, задачи они обсуждают весьма лихо, но... "Думать не хотим!", явственно читается на их лицах и сквозит в их репликах.
Ню-ню.))
Сначала я собирался
выпороть их всех тяжёлым армейским ремнём со всеми пряжками непедагогически втолковать им, что ляпать языком каждый горазд, а умный человек должен хоть каплю соображать, что он ляпает. Но на меня снизошла импровизация. Сначала гавкнуть, чтобы замолчали все.
(А я так умею... редко, но умею.))) Часто нельзя, у спиногрызов иммунитет вырабатывается.) А потом ткнуть пальцем в любого - пусть говорит и доказывает свои слова в гордом одиночестве... Чуть кто что ляпнет
(они же не могут сдержаться))) - гавкнуть, ткнуть в него пальцем и пусть подхватывает эстафету.
И знаете, пошло. Со скрипом, со стонами, охами, воплями,
проклятиями в сторону мерзкого садиста-душителя-мучителя, но мозги начали работать.)))
Так что, чёрт побери, они у меня ещё будут думать своей головой.
И, раз уж речь зашла о своей голове и "думать" - ещё кусочек текста.)) Давно уже хотел написать, да всё руки не доходили. Сразу предупреждаю: много технических подробностей.
Про алгоритмы сжатия данных, Аристотеля и мух.Про алгоритмы сжатия данных, Аристотеля и мух
Есть такой алгоритм сжатия данных - run-length encoding, он же RLE. Пожалуй, это первый из возникших алгоритмов сжатия данных - простой, быстрый, удобный, примитивный, как бревно. Впервые использовался в формате картинок PCX, потом нашлись и другие сферы применения и, разумеется, пошли модификации.
Самый популярный вариант алгоритма звучит примерно так (упрощённо и на примере).
Если входные данные имеют вид, скажем, такой:
а,а,а,а,б,с,в,а,е,е,е,е,е,к,к,к,к,к,к,к,к,у,в,е,к,у.
то упаковываются они в такой массив:
128+4,а,4,б,с,в,а,128+5,е,128+8,к,5,у,в,е,к,у.
Распаковщик же действует так: считал байт L (это длина следующего блока); если байт больше, чем 128 (старший бит установлен) - считать следующий байт со входа и записать его L-128 раз на выход; если же меньше, считать следующие L байт со входа и записать его на выход; повторить, пока данные не закончатся.))
Соответственно, цепочка из 128 одинаковых байт упакуется в два байта, а цепочка из 128 байт без повторов "упакуется" в 129 байт. В сфере применения RLE это обычно приемлемо.
Как я и говорил, алгоритм прямой, как бита, но при этом действующий, применяемый на практике и легко поддающийся анализу. Вероятно, поэтому его рассматривают во всех учебниках по теории кодирования. Причём сразу можно отличить хороший учебник от плохого: в плохом написано, что алгоритм RLE никуда не годится.)) На самом же деле существуют такие источники входных данных, на которых RLE заткнёт за пояс любой другой алгоритм, сколь угодно навороченный.
Дальше начинается самое интересное. Хорошая книжка обязательно приводит анализ: мол, как видно из структуры алгоритма, в лучшем случае входной текст ужмётся в 64 раза (а с некоторыми модификациями - так и в 128), в худшем (т.е., когда текст не упакуется) - объём увеличится на 1/128-ю, что не так уже и много. Ну ведь действительно из структуры алгоритма это видно, правда же?
Можете в Гугле или Яндексе набрать RLE, побегать по ссылкам, почитать... везде будет написанно именно это: в лучшем случае - ужатие в 128 раз, в худшем - увеличение на одну 128-ю. Везде. Такое ощущение, что кто-то один когда-то такое написал, а все остальные тупо копипастили. Я, честно говоря, тоже долгое время так повторял (ну а как же! умные люди написали, разбираются, небось), пока как-то от нечего делать не сел и не написал реализацию алгоритма - так, засолил впрок, авось пригодится когда-нибудь.
И пока писал, понял, что пальцы мои умнее меня: они, набивая примитивный в целом текст декодера, почти сразу засомневались в такой статистике.
И я начал думать.
И тут до меня дошло, что увеличение на одну 128-ю - это далеко не самый худший вариант. Более того, когда я взял бумажку с ручкой и начал считать вероятности, я обнаружил, что это даже не среднее ожидаемое увеличение, а вообще наилучший из всех худших вариантов! А также то, что в наихудшем варианте текст увеличивается на треть - ну, скажем, желающие могут упаковать следущий вход:
а,а,б,а,а,б,а,а,б,...
Считать матожидание увеличения текста меня обломало, признаюсь сразу и честно.
Вот такие пироги.
Аристотель, как известно, посчитал количество лапок у мухи - их оказалось ровно восемь. Это он написал в своих трудах, которые потом объеднили в "Метафизику", и многие последующие античные и средневековые поколения твердили: у мухи восемь лапок! Ну как почему - Учитель сказал!
Две тысячи лет прошло, пока кто-то не выловил у себя в супе муху и от нечего делать не пересчитал у неё лапки...
Выводы пусть каждый делает сам. Мне лень.