Когда СКО подало свое судебное дело против ИБМ, ИБМ решило действовать как в поговорке “я ему отомщу, на балкон надрищу” и открыло судебные дела о нарушении СКО их патентов. Соответственно, потребовалось оценить, насколько эти претензии спреведливы. Мне достался вопрос о патенте на сжатие данных командой compress – это был такой классический юниксный архиватор, который существовал еще до gzip’а. Но на самом деле не только, та же компрессия используется и во все еще популярном формате графических файлов GIF. Компрессией я до того не занимался, так что интересно было в этом разобраться.
Нет, ну кодирование Хаффмана, где повторяющиеся строки бит кодируются битовыми строками переменной длины согласно частоте их встречания в тексте (чем чаще, чем короче назначается кодированная битовая строка), и совсем примитивные варианты типа run length encoding (замены многократных повторов одного символа счетчиком повторов), мы в институте проходили, но это не то, как типично делается сжатие в современной реальности.
Хотя вообще архиваторы на основе кодов Хаффмана существовали – так был устроен совсем древний юниксный архиватор pack. Но они уже давно не используются. Кстати, интересной особенностью сжатия по Хаффману является то, что если попытаться сжать его результат другим архиватором, он не очень-то и сожмется. Другие алгоритмы обычно предполагают, что данные состоят из целых байтов, а Хаффман производит битовые строки произвольной длины, которые не выровнены по границам байтов, и соответственно когда эти битовые строки оказываются сдвинуты внутри байтов на 1, 2, и так далее бит, то они выглядят разными байтами. И заодно другое отступление, почему программы сжатия по-русски традиционно называются “архиватор”. Так сложилось, что первой массово распространившейся такой программой стал pkarc на МС-ДОСе. “pk” - это инициалы автора (который позднее создал pkzip, который до сих пор является популярным форматом), а “arc” - сокращение от “archive”, архив. Соответственно, архиватор. Потом были и другие программы, называвшиеся аналогично. Скажем, одно время очень популярным был lha, где опять же “lh” - инициалы автора, а “a” означает “архив”.
Ключом ко всей современной архивации стал алгоритм Лемпеля и Зива (Lempel and Ziv), патентом на который владеет (точнее, владела, поскольку сейчас его срок уже истек) фирма Юнисис. Я начал с чтения этого патента. В самом патенте оно излагается несколько запутанно, но суть на самом деле там довольно простая. Алгоритм находит повторяющиеся строки байт и кодирует их числами фиксированной длины. То есть, например, если взять фиксированную длину в 16 бит, можно закодировать 65536 строк. Что делать, если мы исчерпали все возможное число строк, а текст не кончился, и мы в нем обнаружили новую строку, которую до того не видели, и нужно ей назначить новый код? Тут есть варианты. Один вариант – начиная с этого момента увеличить длину кода, и теперь кодировать каждую строку не двумя байтами, а тремя. Другой вариант – сбросить всю память о назначенных строках и начать их кодировать сначала. Это выглядит на первый взгляд странно, но часто большие файлы состоят из разных частей, и строки, которые часто встречаются в одной части, оказываются редкими в другой, так что избавление от знаний о предыдущих давних частях – не такая уж и большая потеря.
Вторая часть проблемы заключается в том, как находить эти повторяющиеся строки, и когда они найдены, то как записать “словарь” соответствия строк кодам в сжатый файл, не тратя на это чересчур много байт. Это главная проблема, которую решает алгоритм Лемпеля и Зива. Он начинает с того, что первые 256 значений в коде отводятся под просто байты – то есть, если надо передать просто байт, то он раширяется слева нулями до фиксированной длины кодового значения. Потом мы начинаем читать входной файл и пытаться найти в словаре самую длинную строку, которая будет соответствовать началу файла. Если мы ее нашли, то записываем на выход код этой строки, плюс один следующий байт (его можно не расширять, а так и записать одним байтом). И добавляем в словарь новую строку, состоящую из найденной строки плюс следующего байта, со следующим доступным кодом. Если же мы не нашли в словаре ничего соответствующего, то записываем один следующий байт из файла, расширенный до длины кода, плюс второй байт, который следует за первым. И потом точно так же добавляем эту новонайденную двухбайтовую строку в словарь. В-принципе, можно на это посмотреть и с другой стороны, и сказать, что мы сначала инициализируем словарь всеми возможными однобайтовыми строками, и тогда вторая ситуация сводится к первой – мы всегда сможем найти в словаре какую-то строку, которая просоответствует началу оставшегося файла, хотя бы из одного байта.
И особая прелесть этого алгоритма заключается в том, что он одновременно записывает сжатые данные и сжатый же словарь! Когда вторая часть алгоритма начинает разжимать данные, она добавляет в словарь строки, которые она разжимает, назначая им первый свободный код. И поскольку при сжатии и разжатии проходят одинаковые данные, первый свободный код оказывается в обоих случаях одинаковым, его даже не надо передавать в явном виде! Результат, конечно, получается не идеален, например длинные повторяющиеся последовательности из одного символа набираются в словарь долго, из кусочков, которые каждый раз удлиняются на один символ, и в словаре оказываются и строки, которые потом никогда не повторяются. Но в общем и целом результат лучше, чем у всего, что было придумано до того.
Следующим усовершенстованием, сделанным Велчем (Welch) владел тоже Юнисис, и вся эта комбинация из двух идей известна как LZW (Lempel-Ziv-Welch). Тут фокус в том, что классический алгоритм ЛЗ строит словарь в виде больших префиксных деревьев, хранение которых в виде собственно деревьев довольно неэффективно и требует много памяти, а в 1980-х годах, когда этот алгоритм был придуман, памяти в компьютерах было мало. Поэтому вместо деревьев, словарь хранится в памяти в виде хэш-таблицы. Первые 256 ячеек в ней все еще отведены под строки из одного байта, а вот добавление новых строк делается по-другому. Вместо того чтобы взять следующий свободный номер, новый номер получается комбинированием номера префиксной строки и нового байта через хэш-функцию. И тогда в ячейку таблицы по этому номеру записывается номер префиксной строки и новый байт. Это дает компкатное представление, по которому можно восстановить строки, а так же удобно отыскивать префиксы. Но, конечно, когда таблица оказывается прилично заполненной, то сильно увеличивается вероятность конфликтов, когда мы посчитали номер новой ячейки, а опаньки, там уже оказываются другие значение. Тогда это трактуется как переполнение словаря, вся хэш-таблица очищается, и заполнение начинается сначала.
Внимательный читатель на этом месте спросит: погодите, а где же тут ИБМ? Именно так, ИБМа тут нет. ИБМу принадлежит другой патент, который ни в команде compress ни в ГИФах не используется. Суть того патента в том, чтобы строить новые строки в словаре не как “строка + байт”, а как “строка + строка”. Это позволяет быстро выращивать длинные повторяющиеся последовательности – скажем, если у вас есть подряд сто букв “а”, то классический ЛЗ и ЛЗВ будут удлинять строки линейно - “а”, “аа”, “ааа”, “аааа”, и так далее, а ИБМовский вариант – по экспоненте - “а”, “аа”, “aaaa”, “aaaaaaaa”. Но оно нигде в Юниксе не используется.
Когда я стал это объяснять юристам, пришлось потратить довольно много сил на разъяснение разницы между строкой, пусть даже содержащей один байт, и одним байтом. Среди юристов есть большая разница между юристами младшими и старшими. Сначала я общался с младшей юристкой, как бы даже не паралегалом (это младший юрист без собственно университетской юридической степени, примерно как выпсуник техникума, и без самостоятельной юридической лицензии), а потом уже с настоящим юристом. Если младшая была ни в зуб ногой, то старший просек фишку быстро.
Следующим их вопросом было, а вот до того ИБМ судился с Информиксом и выиграл, и в доказательство ссылался вот на эту книжку. Почитал я еще и ту книжку. И обнаружил, что книжка описывает ИБМовский алгоритм, но называет его ЛЗВ. Но это совсем не то, что говорится в патентах, книжка эта оказалась ошибочной и ссылаться на нее как на доказательство напрочь нельзя.
Младшая юристка почитала описание дела Информикса, и нашла, что Информикс приводил в аппеляции этот аргумент, что книжка неправильная, но этот аргумент не был допущен. Но тут старший юрист ее поправил – надо, говорит, разобраться, почему он не было допущен, может они аппеляцию подали не вовремя. Ну, и поскольку до суда с моим экспертным присутствием дело не дошло, видимо, разобрались, и ИБМ сама отлезла. Меня вот эта ИБМовская наглость, со ссылкой на совсем левую и неправильную книжку как доказательство, несколько поразила. Ну, а люди из Информикса, видимо, не прочухали понять собственно текст патентов.
Надо сказать, что тут еще патенты были написаны довольно популярно. Вот потом в одной из боле епоздних компаний, когда подавали патент на мою идею, ее написали в таком виде, что не зная своего изначального изложения, я бы ни в жисть не догадался, что и зачем там имеется в виду. Похоже на то, что это стало самостоятельной целью юристов: с одной стороны защитить свою идею патентом, с другой стороны сделать этот патент максимально нечитаемым, чтобы было как можно сложнее по нему догадаться, что имеется в виду, и понять изобретение.
Занятие экспертной оценки патентов мне понравилось, но как-то вот больше заняться им не довелось. Зато этот опыт отразился на моем восприятии кампании Electronic Frontier Foundation (EFF) о патентном праве. ЭФФ – бесприбыльная организация, существующая на пожертвования, и согласно своему уставу занимающаяся защитой свобод в электронном мире. Примерно в 2010 году ЭФФ начало возмущаться ситуацией, когда мелкие изобретатели или сами требуют денег с компаний, использующих их патент, или продают свои права компаниям, специализирующимся на таких делах (ЭФФ называет их “патентными троллями”). Ну, в некоторых случаях, когда патентуемое тривиально, то можно повозмущаться тому, какие тривиальные патенты выдают, но не самой практикой. Ведь это – единственный способ, каким мелкие изобретатели могут получить доход со своих патентов. Суть патента – именно в том, чтобы он лиценизировался кому угодно за деньги. А настоящие патентные тролли – большие компании типа ИБМ или Гугла, которые сидят на своих патентах и не лицензируют их, зато используют их как средство внерыночного давления на конкурентов, как ИБМ давило на СКО. Надо, конечно, не забывать, что те же ИБМы и Гугли дают ЭФФу пожертвования, так что направление их возмущения не случайно. С этого началось мое разочарование ЭФФом. А потом они и вовсе проявили себя коммуняками, выступающими за Вселенское Зло, так что своих денег я им уже очень давно не жертвую, и другим не советую.
Я, честно говоря, не знаю, как людям удается получать тривиальные патенты. Я, было дело, уже в более недавние времена пытался получить патент самостоятельно, правда не в компьютерной области, а на косилку. У моего участка находится довольно высокая дорожная насыпь, и косить на ней траву ручной косилкой очень неудобно и утомительно, а трактором не заедешь. И вот я придумал этакую раму, чтоб привесить ручную косилку к трактору, трактором ездишь сбоку по плосокй части, а косилка ездит по косогору. Гораздо легче и быстрее. И решил попытаться ее запатентовать и продать какому-нибудь производителю. Этих мелких тракторов продается дикое количество, если одному проценту их владельцев надо как и мне косить косогор, и если получить по десятке-другой с каждой продажи, то это бы приличные деньги набрались. Заявку я написал, пришлось довольно долго переписываться с патентным офисом по поводу новизны и отличий от предыдущих патентов. Но в итоге мне все равно патент зарубили, поскольку формулировка сделана неправильно.
Американские патенты состоят из двух основных частей. В первой части свободным слогом описывается изобретение, приводятся картинки и прочее. Во второй части идет формулировка патента (patent claims). Это формулировка довольно краткая, и пишется в специфическом формате: каждая формула – одно предложение, но с массой сложноподчиненных частей. И когда дело доходит до суда, то играет роль только то, что написано в формулировке, первая часть если и участвует, то только в качестве контекста, если во второй части обнаруживаются какие-то спорные моменты. Поэтому важно ее сформулировать правильно. Ну, базовые вещи типа использовать слово “включает” (comprises), а не “состоит из” (consists of), я уловил – если писать “состоит из”, то добавление любого нового элемента к рецепту сделает его не попадающим под действие патента, а если “включает”, то вариант с дополнительным элементом может быть самостоятельно патентуемым, но все равно попадающим под изначальный патент. Но, видимо, тонкости я не прочухал, поскольку мне сказали, что мои формулы написаны неграмотно.
Можно было, конечно, пойти к профессиональному юристу, но это дорого, я поинтересовался – они брали по $400 в час, встало бы в несколько тысяч. Ну и поскольку продать свое изобретение мне к тому времени так и не удалось, то я решил, что бессмыссленно делать лишние траты. С продажей мелких изобретений большим производителям все непросто. До некоторых производителей вообще не достучаться. У них, видимо, политика подобная тому, что я когда-то читал в мемуарах Азимова: “когда люди присылают мне свои рукописи на оценку, я их не читаю, чтобы они потом не обвинили меня в том, что я использовал их идеи”. Так и тут, чтобы в присылаемых идеях не оказалось таких же идей, до каких они дошли самостоятельно. До некоторых производителей я достучался, но толку не вышло: как они сказали, это устройство слишком опасное, и им такое выпускать не позволят федеральные требования по защите прав потребителей. Ну да, немножко опасное, зато удобное. В моей личной шкале оценок рисков против удобств, тут удобства напрочь побеждают риски, и я с радостью пользуюсь своим устройством. А федеральные законы с примерно 1970-х годов направлены на защиту идиотов в ущерб разумным людям, спасибо проклятому Ральфу Нейдеру.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
