Let xo, . . . , n be integers belonging to a list of integers and X the generated integer. Encoding a natural list of integers into a single integer and its inverse function is equivalent to finding encoding and decoding functions which provide the following correspondence:Code(xo, . . . , n)→XDecode(X)→xo, . . . , n 
A coding system consists of establishing a law of correspondence, called code, between the information to be represented and the obtained numbers, such that for each information usually corresponds to a single number from which it will be possible to retrieve the original information.
Some coding strategies are based on some bijective function mechanisms, for example those in the Fundamental Theorem of Arithmetic or those in methods to generated numbers through polynomials. In the first instance, the uniqueness of the decomposition of a number into a product of prime factors is the bijection's key mechanism. In the second instance, the uniqueness of the decomposition of a number into a sum of elementary numbers must first be established.
For example, Fibonacci coding concatenates a list of integers in a single binary number such that the separators between integers are represented by the binary pattern 11.
            Fibonacci      ⁢                          ⁢              (                  [                      1            ,            2            ,            3            ,            9            ,            8            ,            7                    ]                )              →                            {          11011001110001100001101011          }                2            →                        {          57088107          }                10                        11              ︷        1              ⁢          011              ︷        2              ⁢          00111              ︷        3              ⁢          00011              ︷        9              ⁢          000011              ︷        8              ⁢          01011              ︷        7            
The person skilled in the art will appreciate that, in general, beyond the theoretical choice of encoding method, the length of the list to be encoded and the dimension of integers to be treated should be considered an essential problem from the practical and applicative points of view.
The person skilled in the art will also appreciate that apart from the problem of compression of the integer list, the generated code size, i.e. the number of representative digits, is a fundamental element in the choice of coding methods.
Given the dimension of data to be processed and levels of computational complexity encountered, performance loss, especially during decoding phases, is almost immediate and disqualifies some theoretically interesting methods regarding the initial coding phase.
Various encoding methods addressing different theoretical problems like the compression, transmission, structuration or encryption of data, the properties of generated codes can be very different in each case.
In coding systems which preserve indexing, the law of correspondence is an order relation which calculates the rank of a list or sequence of integers, and allows classifying and sorting of this list from a unique integer which, in turn, can be decoded to restore the list.
The person skilled in the art will appreciate that there are many possible coding applications. In particular, the ordering of certain sequences of integers is generally the first objective of coding methods using indexing.
Sequences to be ordered essentially belong to the field of combinatorics, e.g. combinations or permutations that must be ordered.
There are numerous applications, ranging from linear algebra, algebraic geometry and graph theory, to the sorting of dictionaries in alphabetical order or enumeration and positioning of combinations in game theory.
How to index a lattice is particularly important in routing problems and parallel algorithms. Thus, the routing can be defined as a software or hardware mechanism that routes information between the source and destination in a communication network incompletely connected, static or dynamic: it selects the best paths in a network, it manages conflicts, and finally it ensures that messages arrive well and in the proper order.
The addressing of data as well as its data structure storage areas in databases or data structures is the basis of numeric information access and its structuring.
The interest of coding information by indexing is to overcome any physical memory organization problem, prior to data manipulation. The physical organization is typically based on the notions of tables or lists whose structure, size and memory location must be explicitly declared. In contrast, coding by indexing enables an implicit description of the information through the properties of the encoded number. For example, the representation of the information in spreadsheets uses standard file formats which specify the convention according to which information is encoded for storage. These formats, such as the Comma Separated Value, describe explicitly how the information should be saved.
The person skilled in the art will appreciate furthermore that the lattice indexing functions can be used as powerful hash functions. To optimize information access, using mathematical functions called hash functions, hashing methods allow a table index to be computed directly from an alphanumeric string called the key. The area of the memory directly indexed thus contains the information associated with the key or a new set of addresses, allowing to indirectly access these addresses.
The person skilled in the art will also appreciate that electronic identification is increasingly used to ensure the traceability of objects, food or living beings. The various kinds of identifiers are for registration, for indexing information: the primary key, or else for the connection. Coding-by-indexing systems are particularly well suited to these types of problems because, in particular, they facilitate alphanumeric sorting and allow rapid identification in databases.
Finally, functions for encoding or mathematical pairing provide the foundation of encryption systems and of the biunique relationship between the operation of coding and decoding. The use of properties of coded numbers such as the prime factor decomposition of a number, may also serve as an independent or complementary approach.
In positional coding, positional number systems are used for coding and decoding vectors of integers from a base of numeration greater than the cardinal number count k−1 of the coding alphabet. The result for encoding the vector (α0, . . . , αk) in base k will beIB=α0·Bk+α1·Bk−1+ . . . +ak·B0 
For example, if the integers (1, 2, 3, 4, 5, 6, 7, 8, 9) are associated with letters of the alphabet (A, B, C, D, E, F, G, H, I), the following code will be obtained, 2·106+1·105+2·104+2·103+1·102+7·101+5·100→{2122175}10 corresponding to the word BABBAGE encoded in base 10. In this case, because the alphabet does not exceed the number of digits available, the resulting code is a simple substitution of letters in the word by the corresponding digits. By enriching the alphabet, the computation of polynomials becomes necessary, such as encoding the letters on more than one digit, for example, in hexadecimal numeration with A=10, B=11 . . . .
The person skilled in the art will appreciate that the encoding of a list of integers can be realized from modular representation of integers, called “Residue Number System” i.e. (RNS).
The RNS system is defined from a set of relatively prime integers, called modules and denoted {m0, m1, . . . , mn}. Therefore GCD (mi,mj)=1, with i≠j. An integer X can then be represented by a set of integers called residues {r0, r1, . . . , rn,} such that xi=X mod mi where 0≦xi<mi. Moreover, this representation is unique for X≦M−1 with M=Πi=0n−1mi.
The coding principle is to consider the list of integers to encode as a list of residues and to find the associated decimal representation. To find modules greater than the respective integers of the list, we can use a sequence of successive primes, which are all greater than their residues or start with the first prime number immediately above the maximum integer in the list to encode. The example below shows the encoding of the 5-dimensional projective point with the homogeneous coordinates [69, 78, 73, 71, 77, 65], starting with the module 73. The encoding function, called Chinese, is essentially a function which solves a system of congruencies from a set of residues.Chinese([69,78,73,71,77,65],[73,79,83,89,97,101])→{252617134512}252617134512 mod 73=69 . . . 252617134512 mod 101=65
The decoding of the decimal number not being unique, it follows that we must know the triplet (Code, initial module, length of the list) to perform the decoding. The triplet will be therefore noted {2526171345121}(73,55). The list could be encoded with an infinity of other triplets such as {412251249819}(79,5), 79, being in this case the first integer is greater than 78.
Cantor coding is associated with the notion of pairing function, which was developed to address the problem of countability of natural numbers. Cantor's pairing function is reduced to a second degree polynomial with the X and Y coordinates of the Cartesian plane as variables. Using this formula, FIG. 1 shows the order in which each pair of coordinates is associated with the indices. For example, IK2(1,2)→8. It is possible to obtain another pairing polynomial by substituting y by x, in which case we obtain IK2(1,2)→7.
      I          K      2        =                              (                      x            +            y                    )                *                  (                      x            +            y            +            1                    )                    2        +    y  
A boustrophedon version is illustrated in FIG. 1b. 
The Cantor pairing function, which allows encoding and decoding of a pair of integers, has been extended to any number of integers in two different ways. The first is by regrouping successively integers by forming pairs of pairs of integers. Based on the initial Cantor encoding function, this method has the advantage of simplicity; a polynomial of degree 2 generates n-degree polynomials. This exponential growth affects in particular the dimension of the calculated indices. An alternative to this approach is the n-dimensional extension of the pairing function. An expression based on binomial coefficients is presented by Cegielski and Richard, in the following form:
      K    ⁡          (                        x          1                ,        …        ⁢                                  ,                  x          k                    )        =            (                                                                  x                1                            +              …              +                              x                k                            +              k              -              1                                                            k                              )        +          (                                                                  x                1                            +              …              +                              x                                  k                  -                  1                                            +              k              -              2                                                                          k              -              1                                          )        +    …    +          (                                                                  x                1                            +                              x                2                            +              1                                                            2                              )        +                  (                                                            x                1                                                                        2                                      )            .      
Unfortunately the n-dimensional Cantor pairing function is not bijective. Some vectors of integers of different dimensions can generate the same encoded number. This problem also exists with the pairing of successive pairs. In this case and by convention, we can add a new coordinate, as arity of the initial vector. In Ernesto Pascal's coding, an integer N can be represented in a unique way for a certain degree n as follows:
      N    =                  (                                                            x                n                                                                        n                                      )            +      …      +              (                                                            x                2                                                                        2                                      )            +              (                                                            x                1                                                                        1                                      )              ,            x      n        >    …    >          x      2        >          x      1        ≥    0.  
The number 1000 will be represented for example by the sequence (12, 9, 8, 7, 6, 5, 3)Cns7 corresponding to the first seven columns of the Pascal's triangle or by the sequence {19, 8, 3}Cns3 corresponding to the first three columns. Therefore, this coding applies to strictly decreasing sequences of integers and is used to solve the problem of lexicographic ordering of r-combinations of a1, a2, . . . , ak of {1, 2, . . . , r}. The formula can be slightly modified to calculate the index of a given combination in the form of an increasing sequence of integers, in which case the following is obtained:
      (                            r                                      k                      )    -      (                                        r            -                          a              1                                                            k                      )    -      (                                        r            -                          a              2                                                                        k            -            1                                )    -  …  -      (                                        r            -                          a              2                                                            2                      )    -            (                                                  r              -                              a                k                                                                          1                              )        .  
There is therefore a need for a method of encoding information which solves at least one problem of the prior art.
USPTO Backgrounds
USPTO Backgrounds