Methods of encoding and combining integer lists in a computer system, and computer software product for implementing such methods
First Claim
Patent Images
1. A method of encoding integer lists in a computer system, comprising the steps of:
- dividing a range covering integers of an input list into subsets according to a predetermined pattern; and
producing coding data including, for each subset containing at least one integer of the input list, data representing the position of said subset in the pattern, and data representing the position of each integer of the input list within said subset.
3 Assignments
0 Petitions
Accused Products
Abstract
A range covering integers of an input list is divided into subsets according to a predetermined pattern. The encoding produces coding data including, for each subset containing at least one integer of the input list, data representing the position of this subset in the pattern, and data representing the position of each integer of the input list within this subset. This encoding process may be iterated in several coding layers. It supports very efficient methods for combining the coded integer lists.
27 Citations
72 Claims
-
1. A method of encoding integer lists in a computer system, comprising the steps of:
-
dividing a range covering integers of an input list into subsets according to a predetermined pattern; and
producing coding data including, for each subset containing at least one integer of the input list, data representing the position of said subset in the pattern, and data representing the position of each integer of the input list within said subset. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method of encoding integer lists in a computer system, comprising n successive coding layers, n being a number at least equal to 1, wherein each coding layer comprises the steps of:
-
dividing a range covering integers of an input list of said layer into subsets according to a predetermined pattern;
producing coding data including, for each subset containing at least one integer of the input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;
if said layer is not the last coding layer, forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and providing said further integer list as an input list of the next layer. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. A computerized method of combining a plurality of first integer lists into a second integer list, wherein at least one of the first integer lists is represented by stored coding data provided by a coding scheme comprising n successive coding layers, n being a number at least equal to 1, each layer having a predetermined pattern for dividing a range covering integers of an input list of said layer into subsets, said first integer list being the input list of the first layer, wherein for any layer other than the last layer, an integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list forms the input list for the next layer, wherein the stored coding data representing a first integer list comprise, for each layer and each subset containing at least one integer of the input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last layer, data representing the position of said subset in the pattern of said layer, the method comprising the steps of:
-
defining a combination of intermediary lists each corresponding to at least one of the first integer lists;
for k decreasing from n to 1, computing a layer k result list by combining a plurality of layer k intermediary lists in accordance with said combination; and
producing the second integer list as the layer 1 result list, and wherein, for any intermediary list corresponding to at least one first integer list represented by stored coding data, the layer n intermediary list is determined from said stored coding data as consisting of the integers of any layer n input list associated with said at least one first integer list in the coding scheme and, if n>
1, each layer k intermediary list for k<
n is determined from said stored coding data and the layer k+1 result list as consisting of any integer of a layer k input list associated with said at least one first integer list in the coding scheme which belongs to a layer k subset whose position is represented in the layer k+1 result list. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43)
-
-
44. A computer program product for encoding integer lists in a computer system, comprising instructions for encoding the integer lists in accordance with n successive coding layers, n being a number at least equal to 1, wherein a range covering integers of input lists of each layer is divided into subsets according to a predetermined pattern, wherein an integer list to be encoded is the input list of the first layer, the computer program product comprising, for each coding layer:
-
instructions for producing coding data including, for each subset containing at least one integer of the input list of said layer, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;
if said layer is not the last coding layer, instructions for forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and for providing said further integer list as an input list of the next layer. - View Dependent Claims (45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63)
-
-
64. A computer program product for combining a plurality of first integer lists into a second integer list, wherein at least one of the first integer lists is represented by stored coding data provided by a coding scheme comprising n successive coding layers, n being a number at least equal to 1, each layer having a predetermined pattern for dividing a range covering integers of an input list of said layer into subsets, said first integer list being the input list of the first layer, wherein for any layer other than the last layer, an integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list forms the input list for the next layer, wherein the stored coding data representing a first integer list comprise, for each layer and each subset containing at least one integer of the input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last layer, data representing the position of said subset in the pattern of said layer, the computer program product comprising:
-
instructions for defining a combination of intermediary lists each corresponding to at least one of the first integer lists;
for k decreasing from n to 1, instructions for computing a layer k result list by combining a plurality of layer k intermediary lists in accordance with said combination; and
instructions for producing the second integer list as the layer 1 result list, whereby, for any intermediary list corresponding to at least one first integer list represented by stored coding data, the layer n intermediary list is determined from said stored coding data as consisting of the integers of any layer n input list associated with said at least one first integer list in the coding scheme and, if n>
1, each layer k intermediary list for k<
n is determined from said stored coding data and the layer k+1 result list as consisting of any integer of a layer k input list associated with said at least one first integer list in the coding scheme which belongs to a layer k subset whose position is represented in the layer k+1 result list. - View Dependent Claims (65, 66, 67, 68, 69, 70, 71, 72)
-
Specification