Encoding and accessing position data

Abstract

In one embodiment, a data structure comprises: a primary index comprising one or more position-block references; and one or more position blocks sequentially following the primary index, wherein: each one of the position-block references corresponds to one of the position blocks; and each one of the position blocks comprises: a secondary index comprising one or more position-data references; and one or more sets of positions sequentially following the secondary index, wherein each one of the position-data references corresponds to of one of the sets of positions in the position block. In one embodiment, an instance of the data structure is stored in a computer-readable memory and accessible by an application executed by a process.

What is claimed: 
     
         1 . A method comprising: by one or more computing devices, accessing position data of a token for one or more documents, wherein:
 the token appears in each one of the documents at one or more positions in the document; and   the position data comprises one or more sets of positions of the token appearing in the documents;   dividing the sets of positions into one or more position blocks;   storing one or more position-block offsets referencing the position blocks in a primary index in an instance of a data structure; and   storing the position blocks sequentially following the primary index in the instance of the data structure, wherein storing one of the position blocks comprises:
 storing one or more position-data lengths in a secondary index of the position block, wherein each one of the position-data lengths equals a total size of one of the sets of positions in the position block; and 
 storing the sets of positions in the position block sequentially following the secondary index. 
   
     
     
         2 . The method recited in  claim 1 , further comprising encoding the position-block offsets in the primary index, comprising:
 selecting the largest one of the position-block offsets;   determining a first bit number that is a minimum number of bits necessary to encode the largest one of the position-block offsets; and   encoding each one of the position-block offsets using the first bit number.   
     
     
         3 . The method recited in  claim 1 , wherein each one of the position-block offsets in the primary index references a memory location at the beginning of the corresponding one of the position blocks. 
     
     
         4 . The method recited in  claim 1 , further comprising encoding each one of the position-data lengths in the secondary index in each one of the position blocks using one byte. 
     
     
         5 . The method recited in  claim 1 , further comprising encoding each one of one or more of the sets of positions, wherein if the position-data length of one of the sets of positions is less than or equal to 255 bits, then encoding the set of the positions comprises:
 selecting the largest one of the positions in the set of positions;   determining a second bit number that is a minimum number of bits necessary to encode the largest one of the positions; and   encoding each one of the positions in the set of positions using the second bit number.   
     
     
         6 . The method recited in  claim 1 , further comprising encoding each one of one or more of the sets of positions, wherein if the position-data length of one of the sets of positions is greater than 255 bits, then the set of positions is encoded using the exponential-Golomb code and stored at the end of the corresponding position block in which the set of positions is stored. 
     
     
         7 . The method recited in  claim 1 , wherein for each one of the sets of positions, the first one of the positions is absolute position; and
 the subsequent ones of the positions are relative positions, wherein each one of the subsequent ones of the positions is a difference between the position and another position immediately proceeding the position.   
     
     
         8 . The method recited in  claim 1 , wherein storing one of the position blocks further comprises storing one or more padding bits following one or more of the sets of positions. 
     
     
         9 . The method recited in  claim 1 , wherein:
 a same number of sets of positions is stored in each one of the position blocks, except the last one of the position blocks; and   the same number or less than the number of sets of positions stored in other ones of the position blocks is stored in the last one of the position blocks comprises.   
     
     
         10 . The method recited in  claim 9 , wherein:
 sixteen sets of positions are stored in each one of the position blocks, except the last one of the position blocks; and   sixteen or less than sixteen sets of positions are stored in the last one of the position blocks comprises.   
     
     
         11 . A system, comprising:
 a memory comprising instructions executable by one or more processors; and   one or more processors coupled to the memory and operable to execute the instructions, the one or more processors being operable when executing the instructions to:
 access position data of a token for one or more documents, wherein:
 the token appears in each one of the documents at one or more positions in the document; and 
 the position data comprises one or more sets of positions of the token appearing in the documents; 
 
   divide the sets of positions into one or more position blocks;   store one or more position-block offsets referencing the position blocks in a primary index in an instance of a data structure; and   store the position blocks sequentially following the primary index in the instance of the data structure, wherein storing one of the position blocks comprises:
 store one or more position-data lengths in a secondary index of the position block, wherein each one of the position-data lengths equals a total size of one of the sets of positions in the position block; and 
 store the sets of positions in the position block sequentially following the secondary index. 
   
     
     
         12 . The system recited in  claim 11 , wherein the one or more processors are further operable when executing the instructions to encode the position-block offsets in the primary index, comprising:
 select the largest one of the position-block offsets;   determine a first bit number that is a minimum number of bits necessary to encode the largest one of the position-block offsets; and   encode each one of the position-block offsets using the first bit number.   
     
     
         13 . The system recited in  claim 11 , wherein each one of the position-block offsets in the primary index references a memory location at the beginning of the corresponding one of the position blocks. 
     
     
         14 . The system recited in  claim 11 , wherein the one or more processors are further operable when executing the instructions to encode each one of the position-data lengths in the secondary index in each one of the position blocks using one byte. 
     
     
         15 . The system recited in  claim 11 , wherein the one or more processors are further operable when executing the instructions to encode each one of one or more of the sets of positions, wherein if the position-data length of one of the sets of positions is less than or equal to 255 bits, then to encode the set of the positions comprises:
 select the largest one of the positions in the set of positions;   determine a second bit number that is a minimum number of bits necessary to encode the largest one of the positions; and   encode each one of the positions in the set of positions using the second bit number.   
     
     
         16 . The system recited in  claim 11 , wherein the one or more processors are further operable when executing the instructions to encode each one of one or more of the sets of positions, wherein if the position-data length of one of the sets of positions is greater than 255 bits, then the set of positions is encoded using the exponential-Golomb code and stored at the end of the corresponding position block in which the set of positions is stored. 
     
     
         17 . The system recited in  claim 11 , wherein for each one of the sets of positions, the first one of the positions is absolute position; and
 the subsequent ones of the positions are relative positions, wherein each one of the subsequent ones of the positions is a difference between the position and another position immediately proceeding the position.   
     
     
         18 . The system recited in  claim 11 , wherein to store one of the position blocks further comprises store one or more padding bits following one or more of the sets of positions. 
     
     
         19 . The system recited in  claim 11 , wherein:
 a same number of sets of positions is stored in each one of the position blocks, except the last one of the position blocks; and   the same number or less than the number of sets of positions stored in other ones of the position blocks is stored in the last one of the position blocks comprises.   
     
     
         20 . The system recited in  claim 19 , wherein:
 sixteen sets of positions are stored in each one of the position blocks, except the last one of the position blocks; and   sixteen or less than sixteen sets of positions are stored in the last one of the position blocks comprises.   
     
     
         21 . One or more computer-readable tangible storage media embodying software operable when executed by one or more computer systems to:
 access position data of a token for one or more documents, wherein:
 the token appears in each one of the documents at one or more positions in the document; and 
 the position data comprises one or more sets of positions of the token appearing in the documents; 
   divide the sets of positions into one or more position blocks;   store one or more position-block offsets referencing the position blocks in a primary index in an instance of a data structure; and   store the position blocks sequentially following the primary index in the instance of the data structure, wherein storing one of the position blocks comprises:
 store one or more position-data lengths in a secondary index of the position block, wherein each one of the position-data lengths equals a total size of one of the sets of positions in the position block; and 
 store the sets of positions in the position block sequentially following the secondary index. 
   
     
     
         22 . The media recited in  claim 21 , wherein the one or more processors are further operable when executing the instructions to encode the position-block offsets in the primary index, comprising:
 select the largest one of the position-block offsets;   determine a first bit number that is a minimum number of bits necessary to encode the largest one of the position-block offsets; and   encode each one of the position-block offsets using the first bit number.   
     
     
         23 . The media recited in  claim 21 , wherein each one of the position-block offsets in the primary index references a memory location at the beginning of the corresponding one of the position blocks. 
     
     
         24 . The media recited in  claim 21 , wherein the one or more processors are further operable when executing the instructions to encode each one of the position-data lengths in the secondary index in each one of the position blocks using one byte. 
     
     
         25 . The media recited in  claim 21 , wherein the one or more processors are further operable when executing the instructions to encode each one of one or more of the sets of positions, wherein if the position-data length of one of the sets of positions is less than or equal to 255 bits, then to encode the set of the positions comprises:
 select the largest one of the positions in the set of positions;   determine a second bit number that is a minimum number of bits necessary to encode the largest one of the positions; and   encode each one of the positions in the set of positions using the second bit number.   
     
     
         26 . The media recited in  claim 21 , wherein the one or more processors are further operable when executing the instructions to encode each one of one or more of the sets of positions, wherein if the position-data length of one of the sets of positions is greater than 255 bits, then the set of positions is encoded using the exponential-Golomb code and stored at the end of the corresponding position block in which the set of positions is stored. 
     
     
         27 . The media recited in  claim 21 , wherein for each one of the sets of positions,
 the first one of the positions is absolute position; and   the subsequent ones of the positions are relative positions, wherein each one of the subsequent ones of the positions is a difference between the position and another position immediately proceeding the position.   
     
     
         28 . The media recited in  claim 21 , wherein to store one of the position blocks further comprises store one or more padding bits following one or more of the sets of positions. 
     
     
         29 . The media recited in  claim 21 , wherein:
 a same number of sets of positions is stored in each one of the position blocks, except the last one of the position blocks; and   the same number or less than the number of sets of positions stored in other ones of the position blocks is stored in the last one of the position blocks comprises.   
     
     
         30 . The media recited in  claim 29 , wherein:
 sixteen sets of positions are stored in each one of the position blocks, except the last one of the position blocks; and   sixteen or less than sixteen sets of positions are stored in the last one of the position blocks comprises.   
     
     
         31 . A system comprising:
 means for accessing position data of a token for one or more documents, wherein:
 the token appears in each one of the documents at one or more positions in the document; and 
 the position data comprises one or more sets of positions of the token appearing in the documents; 
 means for dividing the sets of positions into one or more position blocks; 
 means for storing one or more position-block offsets referencing the position blocks in a primary index in an instance of a data structure; and 
 means for storing the position blocks sequentially following the primary index in the instance of the data structure, wherein the means for storing one of the position blocks comprises:
 means for storing one or more position-data lengths in a secondary index of the position block, wherein each one of the position-data lengths equals a total size of one of the sets of positions in the position block; and 
 means for storing the sets of positions in the position block sequentially following the secondary index.