Сжатие данных

Сжатие данных

Иллюстрации

Показать все

Реферат

Область техники, к которой относится изобретение

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

Предшествующий уровень техники

Пользователи имеют доступ к постоянно возрастающим объемам данных все более разнообразными способами. Например, пользователь может осуществлять доступ к Web-сайту и принимать вещание концерта, т.е. пользоваться услугами Web-вещания. Кроме того, пользователь может осуществлять доступ к играм и другим приложениям по беспроводной сети с использованием беспроводного телефона. В порядке предоставления этих данных пользователю данные могут передаваться от сервера к клиенту в потоковом режиме с целью представления на клиенте. Далее, пользователь может взаимодействовать с представляемыми данными, например, смотря кино, слушая песню и т.д.

Потоковая передача данных обеспечивает пользователю повышенные функциональные возможности, так что пользователь может быстро принимать данные. Если бы не было потоковой передачи данных, то нужно было бы принять от сервера полный объем данных прежде, чем клиент их выведет, вследствие чего пользователь мог бы ощущать задержку представления данных на клиенте. Благодаря потоковой передаче данных, задержка, ощущаемая пользователем, может быть уменьшена. Потоковую передачу данных можно использовать для обеспечения представления данных в режиме реального времени.

При потоковой передаче данных данные передаются от сервера в потоковом или непрерывном режиме, обычно в виде пакетов, для представления на клиенте по мере поступления данных, в отличие от данных, которые невозможно представлять, пока на клиенте не будет всего файла, содержащего данные. Потоковый режим передачи можно использовать для различных типов данных, например, видеоданных, аудиоданных, мультимедийных данных и т.д. Поток видеоданных обеспечивает последовательность «движущихся изображений», которые передаются и визуализуются по мере поступления изображений. Аналогично, поток аудиоданных обеспечивает звуковые данные, которые воспроизводятся по мере поступления аудиоданных. Поток мультимедийных данных содержит аудио- и видеоданные.

Поток данных можно сжимать для эффективной передачи потока данных от сервера на клиент по сети для повышения полезности потоковых данных. Например, сеть, служащая средством связи между сервером и клиентом, может иметь ограниченную пропускную способность. Ограниченная пропускная способность может ограничивать объем данных, которые можно единомоментно передавать от сервера на клиент, и, следовательно, функциональные возможности, предоставляемые клиенту при потоковой передаче данных по сети. Например, видеоданные, передаваемые в потоковом режиме, могут быть ограничены более низким разрешением вследствие ограниченной пропускной способности по сравнению с разрешением, которое могло бы иметь место в случае использования сети с более высокой пропускной способностью. Поэтому пользователь, желающий получать потоковые видеоданные с более высоким разрешением, может быть вынужден тратиться на соединение с более высокой пропускной способностью. Благодаря сжатию потоковых данных, по сетям с низкой пропускной способностью можно единомоментно переносить больше данных и, таким образом, повышать полезность потоковых данных.

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

Соответственно, имеется постоянная потребность в сжатии данных.

Сущность изобретения

Описано сжатие данных. В иллюстративной реализации модуль сжатия выполняется сервером для сжатия данных с целью потоковой передачи на клиент, например, данных, отправляемых в ответ на запрос удаленного доступа от клиента, данных в среде терминальных служб и т.д. Модуль сжатия использует буфер истории, который содержит данные, ранее переданные на клиент в потоковом режиме. При выполнении, модуль сжатия сравнивает последовательность данных, подлежащих потоковой передаче, с одной или несколькими последовательностями в буфере истории для нахождения совпадающей последовательности. Для отыскания последовательности в буфере истории используется поисковая таблица, имеющая совокупность ячеек, каждая из которых доступна по одному из совокупности индексов. Каждая из ячеек указывает, имеется ли соответствующий индекс в буфере истории, и, если да, дополнительно указывает одно или несколько положений соответствующего индекса в буфере истории. Поэтому модуль сжатия может использовать первоначальную последовательность в данных, подлежащих потоковой передаче, в качестве индекса в поисковой таблице для отыскания совпадающего индекса в буфере истории. Затем совпадающую последовательность в данных можно заменить представлением, которое описывает положение и длину совпадающей последовательности в буфере истории, чтобы сформировать сжатые данные для потоковой передачи на клиент.

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

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

Перечень чертежей

Фиг.1 - схема иллюстративной реализации, где показана среда, в которой осуществляется потоковая передача данных от сервера на клиент по сети.

Фиг.2 - схема иллюстративной реализации, где более подробно показаны сервер и клиент, изображенные на фиг.1.

Фиг.3 - логическая блок-схема иллюстративной процедуры, в которой данные, подлежащие потоковой передаче, конфигурируются для сжатия.

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

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

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

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

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

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

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

Подробное описание изобретения

Обзор

Описано сжатие данных. В иллюстративной реализации модуль сжатия выполняется сервером для сжатия данных с целью потоковой передачи с сервера на клиент. Модуль сжатия использует буфер истории, который содержит данные, ранее переданные на клиент в потоковом режиме. При выполнении модуль сжатия сравнивает последовательность данных, подлежащих потоковой передаче, с одной или несколькими последовательностями в буфере истории для нахождения совпадающей последовательности. Для отыскания последовательности в буфере истории, используется поисковая таблица, имеющая совокупность ячеек. Каждая из ячеек доступна по одному из совокупности индексов. Каждая из ячеек указывает, имеется ли соответствующий индекс в буфере истории, и, если да, дополнительно указывает одно или несколько мест размещения соответствующего индекса в буфере истории. Поэтому модуль сжатия может использовать первоначальную последовательность в данных, подлежащих потоковой передаче, в качестве индекса в поисковой таблице для отыскания ячейки. Таким образом, модуль сжатия может быстро отыскивать каждое положение в буфере истории, имеющем первоначальную последовательность, без необходимости сравнивать каждую последовательность в буфере истории с каждой последовательностью в данных, подлежащих потоковой передаче.

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

Иллюстративная среда

На фиг.1 изображена схема иллюстративной реализации, где показана среда 100, в которой осуществляется потоковая передача данных от сервера 102 на клиент 104 по сети 106. Клиент 104 может иметь разнообразные конфигурации. Например, клиент 104 может иметь конфигурацию устройства, которое выполнено с возможностью осуществления связи по сети 106, например, настольного компьютера, который показан, мобильной станции, бытового прибора для развлечений, телевизионной приставки, беспроводного телефона и т.д. Под клиентом 104 также можно понимать лицо и/или сущность, которое/ая оперирует клиентом 104. Иными словами, клиент 104 может описывать логический клиент, который включает в себя пользователя и/или машину. Хотя проиллюстрирован один клиент 104, к сети 106 могут быть подключены с возможностью связи несколько клиентов. Сеть 106 проиллюстрирована как Интернет и может также включать в себя различные другие сети, например, интрасеть, проводную или беспроводную телефонную сеть и т.п.

Сервер 102 выполнен с возможностью передачи данных в потоковом режиме по сети 106 на клиент 104. Сервер 102 может обеспечивать разнообразные потоковые данные для представления на клиенте 104. В одной реализации, сервер 102 может обеспечивать Web-вещание концерта, который передается в потоковом режиме на клиент 104. При представлении на клиенте 104, пользователь может смотреть и слушать Web-вещание. В другой реализации, клиент 104 может принимать данные, включающие в себя песню, передаваемую в потоковом режиме с сервера 102 для вывода на клиенте 104.

В еще одной реализации, сервер 102 может также обеспечивать терминальные службы для удаленного выполнения приложения. Например, сервер 102 может включать в себя совокупность приложений 108(1),..., 108(n),..., 108(N), где «n» может быть любым приложением от 2 до «N». Каждое из приложений 108(1)-108(N) выполняется на сервере 102. Сервер 102 передает в потоковом режиме на клиент 104 по сети 106 экранную информацию, которая обеспечивается выполнением приложений 108(1)-108(N). Например, экранная информация может включать в себя изображение на дисплее настольного компьютера, обеспечиваемое операционной системой, и окно, отображающее информацию, относящуюся к выполнению текстового редактора, а также аудиоинформацию, обеспечиваемую операционной системой и/или текстовым редактором.

Экранная информация, передаваемая в потоковом режиме от сервера 102, представляется на клиенте 104 для наблюдения пользователю. Пользователь может взаимодействовать с клиентом 104 для обеспечения вводов с использованием устройств ввода клиента 104, например, мыши 108 и/или клавиатуры 110. Вводы могут соответствовать представляемой экранной информации, как, например, текстовый ввод для текстового редактора, который обеспечивается с использованием клавиатуры 110. Вводы передаются с клиента 104 на сервер 102 по сети 106. Вводы, принимаемые на сервере 102, могут использоваться при выполнении совокупности приложений 108(1)-108(N). Например, текстовый редактор может принимать текстовые вводы для включения в документ и передавать в потоковом режиме экранную информацию на клиент 104, чтобы иллюстрировать документ, в который включен упомянутый текст. Благодаря выполнению приложений 108(1)-108(N) на сервере 102 и передаче в потоковом режиме экранной информации на клиент 104, клиенту 104 могут быть доступны функции, которые, в противном случае, могли бы не присутствовать на самом клиенте 104.

Например, клиент 104 может иметь конфигурацию «тонкого» клиента, который располагает ограниченными ресурсами обработки данных и/или памяти. С другой стороны, сервер 102 может обладать большими возможностями, например, иметь более значительные ресурсы обработки данных и/или памяти, чем клиент 104. Поэтому сервер 102 может выполнять приложения, которые могут не выполняться на клиенте 104 и/или медленнее выполняться на клиенте 104. Сервер 102 выдает результаты выполнения одного или нескольких приложений 108(1)-108(N) на клиент 104, передавая экранную информацию на клиент 104, и принимает вводы от клиента 104 по сети 106. Таким образом, функциональные возможности, обеспечиваемые сервером 102, например, ресурсы обработки данных, ресурсы памяти и совокупность приложений 108(1)-108(N) могут быть предоставлены клиенту 104, который, в противном случае, не имел бы доступа к этим функциональным возможностям.

Для обеспечения связи между сервером 102 и клиентом 104 по сети, сервер 102 и клиент 104 могут реализовывать соответственно протокол удаленного рабочего стола (RDP) 112, 114. RDP 112, 114 предназначены для обеспечения возможностей удаленного отображения и ввода посредством сетевых соединений для приложений 108(1)-108(N) согласно описанному выше. Например, RDP можно использовать, чтобы разрешать отдельные виртуальные каналы, которые переносят информацию устройства и данные представления от сервера 102 на клиент 104, а также зашифрованные вводы, которые передаются от клиента 104 на сервер 102.

Протоколы RDP 112, 114 могут также обеспечивать снижение пропускной способности за счет включения модулей 116, 118 сжатия и восстановления после сжатия на сервере 102 и клиенте 104 соответственно. Модуль 116 сжатия может выполняться на сервере 102 посредством реализации RDP 112 для сжатия данных до их потоковой передачи по сети 106. Аналогично, модуль 118 восстановления после сжатия может выполняться на клиенте 104 посредством реализации RDP 114 для восстановления после сжатия данных, которые были переданы в потоковом режиме по сети 106 с сервера 102.

Модули 116 и 118 сжатия и восстановления после сжатия при выполнении соответственно сжимают и восстанавливают после сжатия данные, передаваемые в потоковом режиме по сети 106. Согласно вышесказанному, сжатие и восстановление после сжатия потоковых данных может приводить к особым трудностям, в отличие от сжатия и восстановления после сжатия сразу всего набора данных, т.е. блочного сжатия. Например, данные могут передаваться в потоковом режиме «в реальном времени», так что задержки, происходящие при потоковой передаче данных, могут уменьшать полезность данных. Модули 116, 118 сжатия и восстановления после сжатия позволяют устранять особые трудности потоковой передачи данных и, таким образом, обеспечивают потоковую передачу сжатых данных по сети 106, что более подробно описано со ссылкой на фиг.3-5.

Благодаря использованию терминальных служб (ТС, TS), клиент 104 может осуществлять доступ к одному или нескольким приложениям 108(1)-108(N), установленным на сервере 102, выполнять приложение на сервере 102 и отображать пользовательский интерфейс (ПИ, UI) приложения на клиенте 104. Поскольку приложения 108(1)-108(N) выполняются на сервере 102, ТС позволяют клиенту 104 пользоваться ресурсами корпоративной инфраструктуры независимо от того, имеет ли клиент 104 соответствующее аппаратное и программное обеспечение для локального выполнения ресурсов на самом клиенте 104.

Хотя клиент 104 описан в среде терминальных служб, в которой совокупность приложений 108(1)-108(N) выполняется на сервере 102, клиент 104 может также выполнять одно или несколько из совокупности приложений 120(1),..., 120(m),..., 120(M). Например, одно из приложений 120(1)-120(M) может обеспечивать интерфейс, используемый в сочетании с RDP 114 для представления данных для просмотра пользователем и для приема вводов от пользователя, например, с помощью мыши 108 и/или клавиатуры 110. Кроме того, хотя модули 116, 118 сжатия и восстановления после сжатия проиллюстрированы как часть соответствующих протоколов RDP 112, 114, модули 116, 118 сжатия и восстановления после сжатия могут действовать как автономные программные компоненты, которые выполняются для сжатия и восстановления после сжатия потоковых данных соответственно.

Кроме того, хотя части нижеследующего рассмотрения описывают использование сжатия в среде терминальных служб, описанные здесь методики сжатия и восстановления после сжатия также можно использовать в различных других средах. Например, методики сжатия можно использовать для сжатия данных, используемых в среде удаленного доступа. Удаленный доступ описывает возможность доступа к компьютеру или сети из удаленного места. Например, удаленному офису корпорации может понадобиться доступ к сети корпорации и использование доступа к содержащимся там файлам и приложениям, например, через телефонную сеть, Интернет и т.п. Сервер 102 может иметь конфигурацию сервера удаленного доступа, имеющего соответствующее программное обеспечение, предназначенное для обслуживания клиентов, запрашивающих удаленный доступ. В одной реализации, сервер удаленного доступа включает в себя сервер брандмауэра (межсетевого средства защиты) для безопасности и маршрутизатор для пересылки запросов удаленного доступа в другие части сети. Сервер удаленного доступа также можно использовать как часть виртуальной частной сети (ВЧС, VPN).

На фиг.2 изображена схема иллюстративной реализации 200, где более подробно показаны сервер 102 и клиент 104, изображенные на фиг.1. Сервер 102 содержит процессор 202 и память 204. Показано, что RDP 112 и его соответствующий модуль 116 сжатия выполняются на процессоре 202 и хранятся в памяти 204. Аналогично, клиент 104 содержит процессор 206 и память 208. Показано, что RDP 114 и его соответствующий модуль 118 сжатия выполняются на процессоре 206 и хранятся в памяти 208.

Данные, подлежащие потоковой передаче с сервера 102 на клиент 104, могут обеспечиваться из различных источников, например, путем выполнения одного или нескольких из приложений 108(1)-108(N), полученных от устройства 210 ввода, например, видеокамеры, микрофона и пр. Модуль 116 сжатия выполняется на процессоре 202 сервера 102 для сжатия данных с целью потоковой передачи на клиент 104. Данные могут передаваться в потоковом режиме с сервера 102 на клиент 104 в виде пакетов.

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

Если модуль 116 сжатия способен сжать последовательность, то сжатые данные передаются на концевую точку соединения RDP, т.е. RDP 114 клиента 104. Модуль 118 восстановления после сжатия выполняется на клиенте 104 для восстановления после сжатия сжатых данных, чтобы восстановить данные. В случае когда модуль 116 сжатия не способен сжать данные, данные могут передаваться на клиент 104 в потоковом режиме в несжатом виде, т.е. в виде последовательности литералов. Затем модуль 116 сжатия может выполняться на сервере 102 в попытке сжать следующую последовательность.

Основная операция, используемая для сжатия данных, предусматривает согласование по шаблону последовательностей в данных, подлежащих сжатию, с последовательностями, которые были переданы в потоковом режиме раньше. Для этого модуль 116 сжатия поддерживает буфер 212 истории, содержащий данные, которые ранее были переданы в потоковом режиме на клиент 104. Модуль 116 сжатия, при выполнении, согласует последовательность в данных, подлежащих потоковой передаче, с одной или несколькими последовательностями, которые входят в состав данных, которые уже переданы в потоковом режиме на клиент 104. Последовательности в данных, подлежащих потоковой передаче, которые совпадают с последовательностями в буфере истории, можно затем представить с использованием одного или нескольких представлений, которые указывают совпадающую последовательность в буфере 212 истории. Представления могут быть меньше, т.е. использовать меньше ресурсов памяти, чем используется для хранения фактической последовательности, подлежащей сжатию, т.е. совпадающей последовательности. Это эффективно уменьшает объем данных, включенных в потоковые данные.

Чтобы проиллюстрировать основной пример согласования по шаблону с использованием буфера 212 истории, предположим, что буфер 212 истории содержит следующую последовательность:

12745639451491

Модуль 116 сжатия выполняется на процессоре 202 сервера 102 и принимает следующую последовательность:

45974563945146

При выполнении, модуль 116 сжатия находит самую длинную последовательность в буфере истории, которая совпадает с последовательностью в данных, подлежащих сжатию, т.е. совпадающую последовательность. В этом случае совпадающая последовательность, которая появляется в буфере истории, показана ниже жирным шрифтом. Совпадающая последовательность имеет длину десять байтов и начинается с трех байтов от начала буфера 212 истории (начиная слева и продолжая с нуля).

45974563945146

Таким образом, модуль 116 сжатия, при выполнении, может формировать сжатые данные, представляя данные, подлежащие потоковой передаче, следующим образом:

4 5 9 (совпадение длины 10 байтов начиная с 3 байтов от начала буфера) 6.

Благодаря указанию совпадающей последовательности в буфере истории, серверу 102 не нужно повторно передавать последовательности, которые были переданы в потоковом режиме на клиент 104. Таким образом, модуль 116 сжатия сжимает данные, подлежащие потоковой передаче, отыскивая повторяющиеся шаблоны в данных, которые подлежат потоковой передаче, и заменяя повторяющиеся шаблоны, т.е. совпадающие последовательности, представлением, которое использует меньшие ресурсы памяти и полосу пропускания при передаче по сети 106.

Чтобы восстановить после сжатия сжатые данные, клиент 104 включает в себя модуль 118 восстановления после сжатия и буфер 214 истории. В буфере 214 истории клиента 104, как и в буфере 212 истории сервера 102, хранятся данные, переданные ранее в потоковом режиме. Поэтому модуль 118 восстановления после сжатия, при выполнении на клиенте 104, может восстанавливать после сжатия данные, которые были переданы в потоковом режиме на клиент 104, с использованием буфера 214 истории. Продолжая предыдущий пример, предположим, что клиент 104 принимает сжатые данные, которые показаны следующим образом:

4 5 9 (совпадение длины 10 байтов начиная с 3 байтов от начала буфера) 6.

На основании представления, включенного в сжатые данные, модуль 118 восстановления после сжатия, при выполнении, может извлекать сжатую последовательность из буфера 214 истории, которая показана жирным шрифтом следующим образом:

45974563945146

Таким образом, модуль 118 восстановления после сжатия может восстанавливать после сжатия сжатую строку с использованием буфера 214 истории.

Сервер 102 может также содержать поисковую таблицу 216 для отыскания совпадающих последовательностей в буфере 212 истории. Например, поисковая таблица 216 может содержать совокупность ячеек, доступных по одному из совокупности индексов. Каждая ячейка описывает каждое положение в буфере 212 истории, имеющее соответствующий индекс. Таким образом, модуль 116 сжатия, при выполнении на сервере 102, может использовать поисковую таблицу 216 для быстрого определения положения конкретной последовательности в буфере 212 истории. Дальнейшее рассмотрение поисковой таблицы 216 и буфера 212 истории приведено со ссылкой на фиг.3-4.

Сервер 102 может также использовать методы кодирования для дальнейшего сжатия данных для потоковой передачи, например, кодирование по Хаффману, арифметическое кодирование, префиксное кодирование и кодирование по Маркову. Например, данные, подлежащие потоковой передаче, могут включать в себя последовательности, которые не совпадают с последовательностями в буфере истории. Эти последовательности будем называть последовательностями «литералов». С использованием кодирования по Хаффману, некоторые или все последовательности литералов в данных можно сжимать для дополнительного сжатия данных. Например, кодирование по Хаффману может начинаться с таблицы частотности появлений, которая относится к частотности каждой последовательности литералов, которая должна быть дополнительно сжата. Таблицу частотности можно генерировать из самих данных и/или представительных (репрезентативных) данных. Например, частотность последовательности литералов можно получить путем обработки пакетов, ранее переданных в потоковом режиме, и затем использовать для обработки каждого последующего пакета.

Например, каждой последовательности литералов можно присвоить строку переменной длины, которая уникально представляет конкретную последовательность литералов, например, в качестве уникального префикса. Затем строки переменной длины организуются в дерево для кодирования и декодирования каждой(го) последовательности литералов и представления соответственно. Чтобы закодировать последовательность литералов, последовательность литералов, подлежащую кодированию, помещают в дерево. Ветви дерева, которые используются для определения положения листа (концевого узла), который содержит последовательность литералов, используются для кодирования последовательности литералов, т.е. обеспечивают представление последовательности литералов. Например, каждую ветвь дерева, используемого для кодирования по Хаффману, можно пометить символом выходного алфавита, например, битами 0 и 1, так что кодирование представляет собой перечисление меток ветвей на пути от корня дерева к кодируемой последовательности литералов. Декодирование каждого представления осуществляется обходом дерева от его корня вниз по ветвям до листа дерева на основании каждого последующего значения в строке переменной длины, пока не будет достигнут лист дерева, который содержит последовательность литералов.

Хотя было описано кодирование по Хаффману последовательностей литералов, кодирование по Хаффману можно использовать для дополнительного сжатия различных данных. Например, с помощью таблицы 218 Хаффмана можно кодировать как последовательности литералов 222, так и обратные указатели 224. Вышеописанные последовательности литералов включают в себя последовательности, не найденные в буфере 212 истории. Поэтому последовательности литералов 222 можно сжимать с использованием таблицы 218 Хаффмана. Обратный указатель 224 описывает положение конкретной последовательности в буфере 212 истории. Например, согласно описанному выше последовательность в данных, которая совпадает с последовательностью в буфере 212 истории, т.е. совпадающую последовательность, можно описывать как «совпадение длины Х байтов начиная с Y битов от начала буфера». Обратный указатель 224 описывает положение совпадающей последовательности в буфере 212 истории, т.е. 7 байтов. Таблицу 220 Хаффмана можно использовать для сжатия длины 226, т.е. Х байтов, совпадающей последовательности.

Чтобы восстановить после сжатия сжатые данные, передаваемые в потоковом режиме от сервера 102 на клиент 104, модуль 116 восстановления после сжатия выполняется на клиенте 104 с использованием таблиц 228, 230 Хаффмана, которые соответствуют соответственно таблицам 218, 220 Хаффмана сервера 102. Например, таблицу 228 Хаффмана можно использовать для восстановления после сжатия последовательностей литералов 232 и обратного указателя 234, а таблицу 230 Хаффмана можно использовать для восстановления после сжатия длины 226 совпадающей последовательности. Дальнейшее рассмотрение таблиц Хаффмана приведено со ссылкой на фиг.7.

Сервер 102 и клиент 107 могут также включать в себя соответствующие таблицы 236, 238 наиболее давнего использования (НДИ, LRU). Каждую из таблиц 236, 238 НДИ можно использовать для дальнейшего кодирования обратных указателей в зависимости от того, является ли обратный указатель одним из «наиболее давно используемых» обратных указателей. Например, таблицу 236 НДИ можно использовать для обеспечения представления НДИ соответственно для каждого из последних четырех обратных указателей. Представление НДИ используется в качестве индекса для определения положения в таблице 236 НДИ. Таким образом, можно дополнительно сжимать повторяющиеся обратные указатели. Дополнительное рассмотрение таблиц НДИ приведено ниже со ссылкой на фиг.7.

Хотя описано сжатие данных, передаваемых в потоковом режиме от сервера 102 на клиент 104, клиент 104 также может сжимать данные и передавать их в потоковом режиме обратно на сервер 102. Кроме того, хотя в нижеследующем рассмотрении описано сжатие данных в отношении пакетов, передаваемых в потоковом режиме с сервера 102 на клиент 104, для сжатия данных можно использовать разнообразные совокупности данных, например, последовательности байтов подпакета, множественные пакеты и т.д. Кроме того, хотя в нижеследующем рассмотрении описаны последовательности байтов, можно также рассматривать другие последовательности данных, например, битов.

Иллюстративные процедуры

На фиг.3 изображена логическая блок-схема иллюстративной процедуры 300, в которой данные, подлежащие потоковой передаче, конфигурируют для сжатия. На этапе 302, данные добавляют в буфер 212 истории. Например, буфер 212 истории может содержать совокупность пакетов 304(1), 304(2), переданных в потоковом режиме, и/или готовых к потоковой передаче с сервера 102 на клиент 104, как показано на фиг.2, по сети 106. В одном варианте осуществления, пакеты 304(1), 304(2) могут соответствовать данным, которые раньше были обработаны посредством модуля 116 сжатия.

Сервер 102 принимает пакет 304(3), подлежащий потоковой передаче. Модуль 116 сжатия, при выполнении на сервере 102, добавляет пакет 304(3) в буфер 212 истории, так что буфер истории включают в себя пакеты 304(1), 304(2), которые были переданы в потоковом режиме, и пакет 304(3), подлежащий передаче.

На этапе 306 модуль 116 сжатия, при выполнении на сервере 102, обновляет поисковую таблицу 216 ссылкой на добавленные данные, т.е. пакет 304(3). Поисковая таблица 216 может включать в себя совокупность индексов 308(k), где «k» может быть любым индексом от «1» до «K». Каждый из индексов 308(k) используется для нахождения соответствующей одной из совокупности ячеек поисковой таблицы 216. Каждая ячейка указывает, находится ли соответствующий из совокупности индексов 308(k) в буфере 212 истории, и, если да, одно или несколько положений соответствующего индекса 308(k) в буфере 212 истории. Например, одна из совокупности ячеек может указывать совокупность положений в буфере 212 истории, которые имеют соответствующие индексы 308(k). Каждое из совокупности положений показано как описываемое с использованием соответствующей одной из совокупности цепочек 310(k) хэширования.

Например, показано, что индекс 308(k) имеет последовательность «4 5». Соответствующая ячейка для индекса 308(k), т.е. цепочка 310(k) хэширования в поисковой таблице 216, описывает каждое положение индекса 308(k) «4 5» в буфере 212 истории. Например, на фиг.3 показано, что пакет 304(1) имеет следующую последовательность:

01234567

На фиг.3 показано, что пакет 304(2) имеет следующую последовательность:

89453130

На фиг.3 показано, что пакет 304(3), подлежащий потоковой передаче на клиент 104, имеет следующую последовательность:

45670824

Пакеты 304(1)-304(3) можно последовательно организовать в буфере истории так, чтобы наблюдалась следующая последовательность:

012345678945313045670824

Цепочка 310(k) хэширования описывает каждое положение индекса 308(k) «4 5» в буфере 212 истории. Каждое положение можно описывать различными способами. Например, положения можно описывать как положение первого байта последовательности при отсчете от начала буфера 212 истории, начиная с номера нуль. Цепочка 310(k) хэширования описывает первое положение индекса 308(k) «4 5» в 16 байтах от начала последовательности в буфере 212 истории, что показано на фиг.3 пунктирной линией, идущей от «16» в цепочке 310(k) хэширования к началу пакета 304(3). Аналогично, цепочка 310(k) хэширования описывает второе положение индекса 308(k) «4 5» в десяти байтах от начала последовательности в буфере 212 истории, что показано на фиг.3 пунктирной линией, идущей от «10» в цепочке 310(k) хэширования к третьему байту пакета 304(3). Далее, цепочка 310(k) хэширования содержит третье и последнее положение индекса 308(k) «4 5» в 4 байтах в буфере 212 истории. Таким образом, поисковая таблица 216 содержит индекс 308(k), например, «4 5», имеющий соответствующую ячейку, которая указывает цепочку 310(k) хэширования, которая описывает каждое положение, например, 4, 10, 16 индекса 308(k) в буфере 212 истории. Обновляя поисковую таблицу 216, модуль 116 сжатия может, при выполнении, сжимать данные, подлежащие потоковой передаче, более эффективным образом, что будет более подробно описано со ссылкой на фиг.4.

Хотя на фиг.3 показано, что каждый индекс 308(k) имеет соответствующую одну из совокупности цепочек 310(k) хэширования, могут быть случаи, когда индекс 308(k) не имеет соответствующей цепочки хэширования. Например, в некоторых случаях буфер 212 истории может не содержать индекс. Поэтому ячейка поисковой таблицы 216, которая соответствует этому индексу, может не содержать цепочку хэширования. Иными словами, цепочка хэширования для этого индекса имеет значение нуль, т.е. в буфере 212 истории нет места, где располагается соответствующий индекс. Кроме того, хотя показано, что каждая из совокупности цепочек 310(k) хэширования включена в поисковую таблицу 216, одну или несколько цепочек 310(k) хэширования можно обеспечивать разными способами. Например, каждая ячейка поисковой таблицы 216 может содержать указатель на соответствующую цепочку хэширования, которая имеет конфигурацию массива, отдельного от поисковой таблицы 216.

На фиг.4 показана логическая блок-схема иллюстративной процедуры 400, в которой показанная на фиг.3 поисковая таблица 216, сконфигурированная для включения ссылок на пакет 304(3), подлежащий потоковой переда