Font compression and retrieval

Abstract

Method and apparatus for compressing data representing a set of symbols such that each symbol of the set can be separately accessed and decompressed. Each symbol of the set of symbols is encoded in the form of a two-pair code wherein a first part of the code is common for all encoded symbols and a second part of the code encodes the data representing a symbol. An identifier is given for each symbol for permitting each encoded symbol to be separately accessed and decompressed. The invention is particularly useful for storing large fonts such as a Chinese or Japanese character set.

1 . A method for compressing data representing a set of symbols, comprising: 
 encoding each symbol of said set of symbols in the form of a two-part code wherein a first part of said two-part code is common for all encoded symbols of said set and a second part of said two-part code comprises encoded data representing a symbol of said set,    wherein each encoded symbol of said set can be separately accessed and decompressed.    
     
     
         2 . The method according to  claim 1 , wherein the first part of said two-part code comprises a statistical model of said set of symbols, and wherein said encoding step includes encoding data representing each symbol of said set of symbols with a code derived from said statistical model to provide said second part of said two-part code for each symbol of said set.  
     
     
         3 . The method according to  claim 2 , wherein said data representing each symbol of said set comprises a two-dimensional bitmap of each said symbol.  
     
     
         4 . The method according to  claim 3 , wherein said encoding step includes the step of determining the context of each pixel of a bitmap representing a symbol, and constructing a probability table of pixel values having one entry per possible context.  
     
     
         5 . The method according to  claim 4 , wherein said encoding step comprises encoding each symbol using an arithmetic encoder with said probability table.  
     
     
         6 . The method according to  claim 3 , wherein said encoding step includes the step of determining the context of each pixel of a bitmap representing a symbol, and constructing a prediction table indicating the most probable bit value in each context.  
     
     
         7 . The method according to  claim 6 , wherein the most probable bit value for each bit is exclusive-ORed with the actual bit producing a bit stream that is encoded by a Huffman code.  
     
     
         8 . The method according to  claim 2 , and further including the step of storing said encoded data representing each symbol of said set in a memory.  
     
     
         9 . The method according to  claim 8 , and further including an identifier for each symbol of said set of symbols for identifying a location at which the encoded data representing each symbol is stored in the memory.  
     
     
         10 . The method according to  claim 9 , wherein the encoded data representing each symbol of said set are sorted by length, and wherein a set of indexing tables is created for each length, each indexing table including identifiers for encoded data of its respective length.  
     
     
         11 . The method according to  claim 10 , wherein the identifiers included in each indexing table are arranged in an ascending order.  
     
     
         12 . The method according to  claim 10 , wherein a length table is created, said length table including information about each index table, including the length it corresponds to and the length of the index table.  
     
     
         13 . The method according to  claim 1 , wherein said set of symbols comprises a font, and wherein each symbol comprises a symbol of said font.  
     
     
         14 . The method according to  claim 13 , wherein said font comprises a font selected from the group consisting of a Chinese character set and a Japanese character set.  
     
     
         15 . A method for retrieving encoded data representing a symbol of a set of symbols which are stored in a memory, given an identifier for each symbol of said set of symbols, comprising: 
 identifying a location at which said data representing said symbol of said set of symbols is stored in said memory using the identifier for said symbol; and    retrieving said data representing said symbol from said memory.    
     
     
         16 . The method according to  claim 15 , wherein said providing step includes providing an index table containing a list of identifiers for different symbols of said set of symbols, and wherein said identifying step includes searching said index table to locate the identifier for the symbol.  
     
     
         17 . The method according to  claim 16 , wherein encoded data representing said symbols of said set of symbols are sorted first by length and then by identifier, in ascending order, and wherein said step of providing an index table includes providing an index table for each length, each index table containing a list of identifiers sorted in ascending order for symbols represented by encoded data of a particular length.  
     
     
         18 . The method according to  claim 17 , wherein said searching step comprises searching said index tables for said identifier using a binary search.  
     
     
         19 . The method according to  claim 15 , wherein said method further includes the step of decompressing the retrieved data.  
     
     
         20 . The method according to  claim 19 , wherein said encoded data comprises a two-dimensional bitmap of a symbol.  
     
     
         21 . Apparatus for compressing data representing a set of symbols, said apparatus comprising: 
 an encoder which encodes each symbol of said set of symbols in the form of a two-part code, wherein a first part of said two-part code is common for all encoded symbols of said set, and a second part of said two-part code comprises encoded data representing a symbol of said set;    wherein each encoded symbol of said set can be separately accessed and decompressed.    
     
     
         22 . The apparatus according to  claim 21 , wherein the first part of said two-part code comprises a statistical model of said set of symbols, and wherein said encoder encodes data representing each symbol of said set of symbol with a code derived from said statistical model to provide said second part of said two-part code for each symbol of said set.  
     
     
         23 . The apparatus according to  claim 22 , wherein said data representing each said symbol comprises a bitmap of each said symbol, and wherein said encoder includes: 
 an arithmetic encoder for sequentially encoding pixels of said bitmap; and    a source model for providing coding probabilities for the arithmetic encoder, said source model including a context forming unit for forming a context for each pixel of the bitmap, and a probability table containing the pixel probability of each pixel conditioned on the context formed by the context forming unit.    
     
     
         24 . The apparatus according to  claim 22 , wherein said data representing each said symbol comprises a bitmap of each said symbol, and wherein said encoder includes: 
 a source model for providing a predicted value for each pixel of the bitmap,    a unit for exclusive-Oring the predicted value of each pixel with the actual bit to produce a bit stream, and    a Huffman coding unit for encoding the bit stream.    
     
     
         25 . The apparatus according to  claim 24 , wherein said source model includes a context forming unit for forming a context for each pixel of the bitmap, and a prediction table for providing the predicted value for each pixel in each context.  
     
     
         26 . The apparatus according to  claim 21 , wherein said set of symbols comprises a font.  
     
     
         27 . Apparatus for retrieving data representing a symbol of a set of symbols which are stored in a memory, each of said symbols having an identifier, said apparatus comprising: 
 a locator which identifies a location in said memory at which said data representing a symbol of said set of symbols is stored using said identifier for said symbol; and    a decoder which decodes said symbol, wherein data representing each encoded symbol can be separately accessed and decoded.    
     
     
         28 . The apparatus according to  claim 27 , wherein said locator identifies said location by searching an index table which contains a list of identifiers for different symbols of said set of symbols.  
     
     
         29 . The apparatus according to  claim 28 , wherein data representing said set of symbols are sorted by length, and wherein an index table is provided for each length, each index table containing a list of identifiers for symbols represented by data of a particular length.