Determination of compression state information for use in interactive compression

Abstract

The invention is directed at a method and apparatus for determining compression state information which is to be used in the compression of data being transmitted between two communicating parties. The method of determining the compression state information for use in interactively compressing data comprises the steps parsing the data to determine a hierarchical data structure of the data; traversing a shared hierarchical node index to determine common compression state information entries between the hierarchical data structure and the hierarchical node index; and selecting at least one of the common compression state information entries for use in compressing the data.

What is claimed is: 
     
         1 . A non-transitory computer-readable memory storing statements and instructions for execution by a processor to perform a method of:
 receiving a request for data, at one of a server and a client;   identifying common compression state information based on the requested data, the compression state information comprising parameters of previously completed compressions; and   selecting at least one unit of compression state information for use in compressing the data.   
     
     
         2 . The computer-readable memory of  claim 1 , wherein the parameters comprise grammar rules of previously completed compressions. 
     
     
         3 . The computer-readable memory of  claim 1 , wherein the parameters comprise frequency counts of previously completed compressions. 
     
     
         4 . The computer-readable memory of  claim 1 , wherein identifying common compression state information comprises searching a database storing compression state information common to the server and the client. 
     
     
         5 . The computer-readable memory of  claim 4 , wherein searching the database comprises traversing a hierarchical node index. 
     
     
         6 . A non-transitory computer-readable memory storing statements and instructions for execution by a processor to perform a method of:
 parsing an identification of the data;   traversing a side information database, including compression state information for use in interactive compression of data, containing side information identifiers shared by communicating parties in a communication to identify elements of the parsed identification known to both communicating parties; and   selecting at least one unit of side information based on the identified elements for use in compressing the data.   
     
     
         7 . The computer-readable memory of  claim 6 , wherein parsing the identification of the data comprises parsing a Universal Resource Locator (URL) identifying the requested data. 
     
     
         8 . The computer-readable memory of  claim 6 , wherein parsing the identification of the data comprises parsing an email identification string. 
     
     
         9 . The computer-readable memory of  claim 6 , wherein traversing the side information database comprises traversing a hierarchical node index. 
     
     
         10 . The computer-readable memory of  claim 9 , wherein the hierarchical node index is stored in a mobile communications device. 
     
     
         11 . A non-transitory computer-readable memory storing statements and instructions for execution by a processor to perform a method of:
 parsing a data identifier associated with requested data to identify constituent elements of the data identifier;   searching a side information database shared by communicating parties in a communication to identify entries in the side information database corresponding to the constituent elements of the data identifier; and   selecting at least one unit of side information based on the identified entries for use in compressing the requested data.   
     
     
         12 . The computer-readable memory of  claim 11 , wherein selecting the at least one unit of side information comprises applying a pre-determined rule. 
     
     
         13 . The computer-readable memory of  claim 12 , wherein the predetermined rule is based on a minimum number of common elements. 
     
     
         14 . The computer-readable memory of  claim 12 , wherein the predetermined rule is based on a maximum number of unmatched elements. 
     
     
         15 . The computer-readable memory of  claim 11 , wherein searching the side information database comprises traversing a hierarchical node index; and further wherein selecting the at least one unit of side information comprises selecting at least one leaf node of the hierarchical node index. 
     
     
         16 . A non-transitory computer-readable memory storing statements and instructions for execution by a processor to perform a method of:
 synchronizing side information databases at a server and a client;   receiving a request for data, including a data identifier, at one of the server or the client;   parsing the data identifier to identify constituent elements of the data identifier;   searching the synchronized side information database at the one of the server or the client to identify entries in the side information database corresponding to the constituent elements of the data identifier; and   selecting at least one unit of side information based on the identified entries for use in compressing the requested data.   
     
     
         17 . The computer-readable memory of  claim 16 , wherein searching the synchronized side information database comprises traversing a hierarchical node index; and further wherein the side information identifiers are represented as nodes in the hierarchical node index. 
     
     
         18 . The computer-readable memory of  claim 17 , wherein selecting the at least one unit of side information comprises applying a rule based on a minimum distance of a node to a closest common ancestor. 
     
     
         19 . The computer-readable memory of  claim 18 , wherein selecting the at least one unit of side information comprises selecting the most recently used leaf node from a plurality of leaf nodes associated with the constituent elements. 
     
     
         20 . The computer-readable memory of  claim 19 , wherein each of the plurality of leaf nodes is provided with a unique identifier.