Зип-зип-ура!

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

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

Этот формат компрессии, корни которого уходят в начало 90-х (говорят, придуман он был в 1991 американской компанией Nico Mark Computing), на сегодня, вероятно, один из самых популярных - благодаря наличию его многочисленных открытых переложений. Zip, равно как и другие распространённые форматы сжатия данных, основывается на т.н. кодировании Хаффмана - алгоритме, предполагающем отыскание часто повторяющихся длинных цифровых последовательностей и замене их сравнительно короткими метками. Чем длинней и чаще повторяющийся блок - тем более короткой меткой его заменяют. Конечно, на деле всё несколько сложней, но общая идея именно такая. Изюминка в том, что с недавних пор zip начали применять не по назначению. А именно - для классификации текстовых, графических и аудиодокументов.

Использование zip для различения изображений было предложено двумя учёными из США (Frank Corsetti, Michael Storrie-Lombardi), решавших непростую задачу: как отличить окаменелые остатки жизнедеятельности древних бактерий от чрезвычайно похожих структур, образованных неживой природой. Окаменелости, известные как строматолиты, представляют из себя результат проделанной цианобактериями работы миллиарды лет назад. Проблема в том, что такие же пористые образования могут появляться и в ходе простых химических процессов, а различить их на глаз - задача, требующая проведения скрупулёзного анализа. Тут-то и пришла на помощь UNIX-утилита gzip: как оказалось, обработав gzip высококачественные цифровые фотографии среза строматолитов, можно судить об их происхождении по размерам получившихся файлов. Чем выше степень сжатия, тем больше вероятность того, что строматолит, соответствующий данному фото, достался нам от бактерий.

Весьма похоже на этот эксперимент выглядит и классификация с помощью bzip2 (ещё один вариант zip) аудиодокументов. Речь, правда, не о "мпегах", а об обычной нотной записи музыкальных композиций: группа исследователей из Голландии (Dutch National Research Institute in Amsterdam) научилась сортировать музыку по жанрам и композиторам, анализируя всё ту же степень компрессии файлов. Их опыт сводится к следующим несложным операциям: берутся несколько образцов мелодий, определённо принадлежащих к какому-либо музыкальному жанру (классика, рок, джаз), и сжимаются bzip2. Размер получившихся файлов запоминается, после чего в опыт добавляют ещё одну композицию неивестного происхождения - и поочерёдно пристыковывают её к каждой из тех трёх, что были взяты раньше (к несжатым), а результат опять же подвергается компрессии. После этого проводится попарное (к примеру, сжатой исходной рок-композиции и сжатой рок-композиции с добавлением опытного образца) сравнение размеров упакованных файлов. Та пара, которая покажет наименьшее различие в размерах, как раз и свидетельствует о принадлежности опытной мелодии к определённому жанру: к примеру, если минимальным оказывалось увеличение архива джаз-композиции, опытный образец был именно джазовым. Что самое интересное, если исходный набор композиций принадлежал к одному жанру, zip-компрессия помогала выявить работы, созданные одним музыкантом: они точно так же сжимались сильнее других. Аналогичный способ применялся другими исследователями и для дифференциации текстовых документов на разных языках.

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