WO2013067629A1 - Méthode et système pour coder de l'information - Google Patents

Méthode et système pour coder de l'information Download PDF

Info

Publication number
WO2013067629A1
WO2013067629A1 PCT/CA2012/001042 CA2012001042W WO2013067629A1 WO 2013067629 A1 WO2013067629 A1 WO 2013067629A1 CA 2012001042 W CA2012001042 W CA 2012001042W WO 2013067629 A1 WO2013067629 A1 WO 2013067629A1
Authority
WO
WIPO (PCT)
Prior art keywords
list
integers
pyramid
indexing
hyperspace
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/CA2012/001042
Other languages
English (en)
Inventor
Jean-François ROTGE
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
PARALLEL GEOMETRY Inc
Original Assignee
PARALLEL GEOMETRY Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by PARALLEL GEOMETRY Inc filed Critical PARALLEL GEOMETRY Inc
Priority to EP12847457.4A priority Critical patent/EP2777159A4/fr
Priority to US14/357,468 priority patent/US9900024B2/en
Priority to CA2855169A priority patent/CA2855169C/fr
Publication of WO2013067629A1 publication Critical patent/WO2013067629A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/16—Matrix or vector computation, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization

Definitions

  • This invention relates to the field of coding. More specifically, this innovation relates to a method and a system for encoding information using a hyperspace pyramid.
  • x 0 , ..., n be integers from a list of integers and X be the generated integer; to encode a list of natural numbers into a single integer and its inverse return to finding coding and decoding functions ensuring the following correspondence:
  • An encoding system consists in establishing a correspondence law called code between the information to be represented and the numbers obtained, of so that each information corresponds to one and usually a single number from which it will be possible to retrieve the initial information.
  • Some coding strategies rely on functional bijective mechanisms contained, for example, in the fundamental theorem of arithmetic or in polynomial generation methods of numbers. In the first case, the uniqueness of the decomposition of a number into a product of prime factors is the key to the bijective mechanism. In the second case, the uniqueness of the decomposition of a number into a sum of elementary numbers must be established beforehand.
  • Fibonacci encoding makes it possible to concatenate a list of integers into a binary number such that the separators between the integers are represented by the binary pattern 1 1.
  • the person versed in the field will appreciate that in general, beyond the theoretical choice of the coding method, the length of the list to be coded and the size of the whole numbers to be treated must be considered as an essential problem from the point of view practical and application.
  • the person versed in the domain will also appreciate that apart from the problem of compression of the list of integers, the size of the generated code, ie its number of representative digits, is a fundamental element in the choice of the methods of coding. Given the size of the data to be processed and the levels of algorithmic complexity encountered, performance collapse phenomena, particularly during the decoding phases, are practically immediate and disqualify certain theoretically interesting methods with regard to the initial coding phase. .
  • the properties of the generated codes can in this case be very different.
  • the law of correspondence is a relation of order which calculates the rank of a list or sequence of integers, and which makes it possible to classify or to sort this list starting from a unique integer which can in turn be decoded to restore the list.
  • the routing can be defined as a software or hardware mechanism that routes the information between the source and the destination during a communication in an incompletely connected network of static or dynamic type: it makes the choice of the paths when there are some many, he manages the conflicts, finally he ensures that the messages arrive well and in the right order.
  • indexing coding an implicit description of the information through the properties of the encoded number.
  • the representation of information in spreadsheets uses standard description formats that specify the organization conventions of the files. These formats, such as the Comma Separated Value, explicitly describe how information should be recorded.
  • lattice indexing functions can be used as powerful hash functions.
  • hash techniques allow from hash math functions to directly calculate the index of a table from an alphanumeric string called the key.
  • the directly indexed memory zone then contains the information associated with the key or a new set of addresses allowing indirect access to these addresses.
  • identifiers are the identifiers for the registration, for the indexing of the information: the primary key, or else for the connection.
  • Index coding systems are particularly well suited to W these types of problem because they facilitate inter alia alphanumeric sorts and allow quick identification in databases.
  • the functions of encoding or mathematical coupling are often the basis of encryption systems and can be the basis of the one-to-one relationship between the encoding and decoding operation.
  • the use of the properties of the coded numbers, for example the decomposition into a product of prime numbers, can also serve as an independent or complementary approach.
  • positional numeration systems are used to encode and decode integer vectors from a counting base higher than the k - 1 cardinal of the encoding alphabet.
  • the encoding of a vector ( ⁇ 0 , ⁇ ⁇ ⁇ ⁇ ⁇ ) in base k will then be
  • I B cc Q .B k + a v B k - l + - - - + a k .B °
  • the alphabet does not exceed the number of available digits, the code obtained corresponds to a simple substitution of the letters of the word by the associated digits.
  • RNS Residue Number System
  • the coding principle is therefore to consider the list of integers to be coded as a list of residues and find the associated decimal representation. It is possible to find modules higher than the respective integers of the list, to use a sequence of successive prime numbers all higher than their respective residues or beginning with the prime number immediately greater than the maximum integer of the list to be encoded.
  • the following example makes it possible to code the projective point [69, 78, 73, 71, 77, 65] in dimension 5 from the module 73.
  • the Chinese coding function is essentially a function making it possible to solve a congruence system. from a list of integer residues.
  • the decoding of the decimal number is not unique, it follows that it is necessary to know the triplet (Code, initial module, length of the list) to perform the decoding.
  • the necessary triplet will be noted ⁇ 252617134512 ⁇ ( 7 3 5 ).
  • the list could be encoded with an infinity of other triplets such as for example ⁇ 412251249819 ⁇ (79.5), 79 being in this case the first integer greater than 78.
  • Cantor's coding is associated with the notion of coupling function developed to answer the enumerability problem of natural numbers.
  • the coupling function of Cantor is reduced to a polynomial of the second degree having the abscissa and the ordinate of the Cartesian plane as a variable.
  • Figure 1 shows the order in which the polynomial associates the pairs of coordinates with the indices according to the following formula. For example I K (1, 2) ⁇ 8. It is possible to obtain a second coupling polynomial by substituting x for y and in this case I K (1, 2) -> ⁇ 7.
  • the variant illustrated in FIG. 1b presents a boustrophedonic variant.
  • the Cantor coupling function for encoding and decoding a pair of natural numbers has been extended to any number of integers in two ways different.
  • the first is to group the integers by successively constituting pairs of pairs of integers.
  • This method has the advantage of the simplicity of Cantor's initial coding function: a polynomial of degree 2 but generates polynomials of degree n 2 .
  • This exponential growth affects in particular the size of the calculated indices.
  • An alternative to this approach is the n-dimensional extension of the coupling function.
  • An expression based on binomial coefficients is presented by Cegielski and Richard in the following form:
  • N N ⁇ n ⁇ n ⁇ n ⁇ n ⁇ n ⁇ n ⁇ n ⁇ n ⁇ n ⁇ n ⁇ ⁇ n ⁇ ⁇ n ⁇ ⁇ n ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ n n ⁇ n ⁇ n ⁇ ⁇ n ⁇ ⁇ n ⁇ ⁇ n ⁇ ⁇ ⁇ n ⁇ ⁇ ⁇ n ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇ ⁇
  • N , x "> ⁇ ⁇ ⁇ > x 2 > X j > 0.
  • the number 1000 will for example be represented by the sequence ⁇ 12,9,8,7,6,5,3 ⁇ Cm corresponding to the first seven columns of Pascal's triangle or else by the sequence ⁇ 19,8,3 ⁇ C 3 ns corresponding to the first three columns.
  • the coding therefore applies to strictly decreasing integer sequences and is used to solve the problem of lexicographic ordering of the r-combinations of Cl ⁇ 2 of ⁇ 1,2, ⁇ ⁇ ⁇ , r).
  • the formula can be slightly modified to calculate the index of a given combination in the form of a sequence of increasing integers and it is obtained:
  • Figure la illustrates the Cantorian order while figure lb illustrates the Cantorian order boustrophedonique.
  • Figure 2 illustrates the De Gua triangle of Malves and its projective extension.
  • Figure 3 illustrates a pyramidal lattice and the labeling of projective coordinates.
  • Figure 4 illustrates an embodiment of the coding and decoding system.
  • Figure 5 illustrates an implementation of the GLOBAL algorithm and an implementation of the LOCAL algorithm.
  • Figure 6 illustrates recursive trees for
  • Figure 7 illustrates the positional indexing for T 3 2 in quaternary base.
  • Figure 8 illustrates the expansion of large integers.
  • Figure 9 illustrates the numerical order for the T4.3 lattice.
  • Figure 10 illustrates an implementation of the NUMORD algorithm.
  • Figure 11 illustrates a pyramidal decomposition of a number.
  • Figure 12 illustrates an implementation of the ORDNUM algorithm.
  • Figure 13 illustrates the lexicographic coding of the T4.3 lattice.
  • Figure 14 illustrates an implementation of the LEXORD algorithm.
  • Figure 15 illustrates an implementation of the ORDLEX algorithm.
  • Figure 16 illustrates the Projective Gray coding (4.3).
  • Figure 17 illustrates an implementation of the GRAORD algorithm.
  • Figure 18 illustrates the course of T4,3 in projective Gray.
  • Figure 19 illustrates an implementation of the ORDGRA algorithm.
  • Figure 20 illustrates an implementation of the VN2VM algorithm and the VM2VN algorithm.
  • Figure 21 illustrates the combinatorial tree
  • Figure 22 illustrates the tree and the digital tags.
  • FIG. 23 illustrates the tree and the lexicographic labels.
  • Figure 24 illustrates an example of a combinatorial projective subspace.
  • Figure 25 illustrates an example of a bijection between projective points and combinations.
  • Figure 26 illustrates an example of projective and binary generation of combinations.
  • Figure 27 illustrates the Euclidean and affine coordinates of a Cantorian point.
  • Figure 28 illustrates the taxonomy of orders.
  • Figure 29 illustrates Cantorian paths.
  • Figure 30 illustrates a possible implementation of the method for encoding information.
  • Figure 31 illustrates spiral paths.
  • Figure 32 illustrates an implementation of the SPIORDc algorithm and the ORDSPIc algorithm.
  • Figure 33 illustrates an implementation of the SPIORDa algorithm and the ORDSPIa algorithm.
  • Figure 34 illustrates a spiral chain for T 63 .
  • Figure 35 illustrates a convolution mechanism.
  • Figure 36 illustrates convolutions of Vandermonde for
  • Figure 37 illustrates an implementation of the CRKREC algorithm.
  • Figure 38 illustrates an implementation of the XENUME algorithm and the YENUME algorithm.
  • Figure 39 illustrates an implementation of the COMBO algorithm.
  • Figure 40 illustrates the optimized calculation of the binomial coefficient.
  • Figure 41 illustrates an implementation of the PRODYN algorithm.
  • Figure 42 illustrates an implementation of the MATPRT algorithm.
  • Figures 43a and 43b illustrate a matrix multiplication between columns.
  • Figure 44 illustrates a curve that represents for a given dimension the values of the binomial coefficients.
  • Figure 45 illustrates an implementation of the ENCDEC algorithm and the DIGBIN algorithm.
  • Figure 46 illustrates an implementation of the NUMFCT algorithm.
  • Figure 47 illustrates an implementation of the DRVREC algorithm.
  • Figure 48 illustrates an implementation of the DRVSYM algorithm.
  • Figure 49 illustrates an implementation of the BINRP4 algorithm.
  • Figure 50 illustrates an implementation of the BINRPNi algorithm and RPNBINi algorithm.
  • Figure 51 illustrates an implementation of the GLOBALo algorithm and the LOCALo algorithm.
  • Figure 52 illustrates an implementation of the ORDNUMo algorithm and the ORINUMo algorithm.
  • Figure 53 illustrates an implementation of the INDCOM algorithm and the COMIND algorithm.
  • Figure 54 illustrates an implementation of the MPLNUM algorithm.
  • a method for encoding information, the method comprising obtaining a list of integers to be encoded; determining a hyperspatial pyramid having a size suitable for encoding the list of integers, the hyperspace pyramid having a plurality of vertices the number of which is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers of the integer list and by the dimension of the hyperspatial pyramid which is equal to the number of integers in the list of integers minus one; index the list of integers in this pyramid by means of an indexing system; and providing an indication of indexing the list of integers in the hyperspace pyramid to thereby encode said list of integers to be encoded.
  • the method further comprises providing a list of alphanumeric codes and transforming the list of alphanumeric codes into a list of integers to code.
  • the indexing system makes it possible to index each of the plurality of vertices of said hyperspace pyramid.
  • the indication of the indexation of the list of integers in the hyperspace pyramid comprises an integer representing the index of the projective point in the indexing system, m the total degree of said list of integers and n the number of integers in the list of integers.
  • the method further comprises transforming the integer representing the index of the projective point by mx and nx combinatorial coordinates.
  • the method further comprises the transformation of m the total degree of the list of integers and n the number of integers of the list of integers by an integer Y representing a global index .
  • the method further comprises summing the integer Y representing a global index to the integer representing the index of the projective point to provide a total index Z, the indication of indexing in the hyperspace pyramid comprising the total index Z.
  • the list of integers is obtained from a file.
  • the step of providing indexing indication in the hyperspace pyramid includes storing said indexing indication in a file.
  • the step of providing the indication of the indexation of the list of integers in the hyperspace pyramid comprises the transmission of said indication of the indexation of the list of integers to a processing unit via a network.
  • the method is used to code a list of relative integers, the method comprising providing the list of relative integers and generating the list of integers by means of the list of integers .
  • the step of providing the indication of the indexing of the list of integers in the hyperspace pyramid comprises displaying said indication of the indexing of the list of integers. on a screen.
  • the method described above is used to compress a string in which the string is associated with said list of integers.
  • the method described above is used to code a list of lists, the method comprising the iterative use of the method described above for encoding a list of lists.
  • the method described above is used to encrypt a list of integers, in which the indexing of the list of integers corresponds to the encryption of the list of integers.
  • a method for decoding coded information by means of the method for coding information described above, the method comprising obtaining an indication of the indexation of the list of whole in the hyperspace pyramid; obtaining an indication of an indexing system used to generate said indication of the indexing of the integer list in the hyperspace pyramid and determining by indexing and indicating an indexing system used said list of integers.
  • an information storage device is described for storing executable instructions by a processor, which when executed will cause the processor to execute a method for encoding information.
  • the method comprising obtaining a list of integers to be encoded; determining a hyperspatial pyramid having a size suitable for encoding the list of integers, the hyperspace pyramid having a plurality of vertices the number of which is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers of the integer list and by the dimension of the hyperspatial pyramid which is equal to the number of integers in the list of integers minus one; index the list of integers in this pyramid by means of a system indexing; and providing an indication of indexing the list of integers in the hyperspace pyramid to thereby encode said list of integers to be encoded.
  • a computer comprising a display unit; a processor; a data storage unit comprising a program configured to be executed by the processor, the program for encoding information, the program comprising instructions for obtaining a list of integers to be encoded; instructions for determining a hyperspatial pyramid having a size suitable for encoding the integer list, the hyperspace pyramid having a plurality of vertices the number of which is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers in the list of integers and by the dimension of the hyperspatial pyramid which is equal to the number of integers in the list of integers minus one; instructions for indexing the list of integers in this pyramid by means of an indexing system; instructions for providing an indication of indexing the list of integers in the hyperspace pyramid to thereby encode said list of integers to be encoded.
  • An advantage of the system described is that it is intended for encoding / indexing / transcoding lists of any integers without predefined combinatorial structures as well as for particular lists with predefined combinatorial structures such as polynomial coefficient lists or lists of combinations without repetitions.
  • Another advantage of the system described is that it allows to work in bijective encoding mode Code (X) ⁇ Y and Decode (Y) ⁇ X or in encryption mode Code (X) ⁇ Y Decode (Y, key 1, key 2) ⁇ X.
  • Another advantage of the system described is that it can provide a solution to various problems such as the nature and size of the data, the size of the coding / decoding program, the size of the generated code and the properties of the generated code.
  • the method described may allow the use of structured or non-structured data of any size.
  • the size of the coding / decoding program is possibly implementable by means of a few dozen instructions and a standard multiprecision integer processing library, such as for example GMP.
  • the generated code can be indexed multi-use for for example at least one of the scheduling of the integer lists, the routing architectures, the addressing and the hashing of data. electronic identification and cryptography.
  • Pyramidal numbers are figured numbers, ie numbers decomposed and visualized from points distributed on regular polytopes. Pascal's triangle is formed from triangular, tetrahedral and generally hyperte- torric numbers.
  • the disclosed system is based on the idea of using the combinatorial properties of the Pascal triangle and the algebraic properties of the hyperspace projective extensions of the De Gua triangle of Malves as a general indexing and coding system of integer lists. natural. For this, the one-to-one correspondence between the monomials of a polynomial P mn and the points of a lattice T mn will be used. The ordering of the monomials of this polynomial will consequently be equivalent to the ordering of the points of this lattice.
  • Figure 2 shows the transition between the original triangle described by De Gua and its two-dimensional projective extension for a third-degree curve.
  • a pyramidal lattice is as much a combinatorial structure as a hyperspace geometrical structure whose study concerns the algebraic geometry.
  • the lattices are in the form of hyperspace pyramids, such as the tetrahedron of FIG. 3 or the triangle of FIG. 2.
  • a tetrahedral pyramidal lattice, denoted T mn corresponding to the line m + n and to the column m of the Pascal triangle, is associated with each binomial coefficient and therefore a hyperte- toric projective configuration of dimension n in homogeneous points, linearly
  • the points of the lattice are organized in a combinatorial way, in sub-lattices of dimension n - ⁇ and of degree from 0 to m - ⁇ (rule of the summation of the diagonal).
  • Each lattice is located in Pascal's triangle by the pair (m, n) or by the summation of all the points of all the preceding lattices, which we will name the global index.
  • the number of points, the associated pyramidal number is equal by definition to the number of monomials of a homogeneous polynomial of degree m in n dimensions.
  • the homogeneous projective coordinates of the points of a lattice T mn can therefore be interpreted as the exponents of the monomials of an associated polynomial of degree m and of dimension n.
  • Each square of Pascal's triangle corresponds to a hyperspace pyramid whose number of vertices is equal to the number indicated in the box.
  • the Euclidean definitions of the orders of the monomials of the nonhomogeneous polynomials are based on the notion of lexicographic order and of total degree of the monomials, ie the sum of the exponents of the variables of the monomials.
  • the pure lexicographic order the total and then the lexicographic order, the total order then the inverse lexicographic one.
  • all monomials have by definition the same total degree and the ordering of the monomials can be realized from two ducal projective lexicographic orders, one on the exponents and the other on the indices, the monomials being represented in tensorial notation.
  • inverse lexicographical orders are simple upward or downward variants of lexicographical orders.
  • the lexicographic order of the indexes of variables such as Vfla k ⁇ ⁇ if and if only the non-zero most left value of vn " ⁇ is negative will be named lexicographic order.
  • De Gua de Malves polynomial of figure 2 corresponding to a Euclidean curve of the third degree is ordered in the lexicographic order of its coefficients, it is obtained: a, by, ex, ey 2 , fxy, gx 2 , hy 3, IXY 2, kx 2 .y, 2.x 3.
  • x for x0 / x2 and y for xl / x2
  • the homogeneous representation of the polynomial is obtained: IX Q.
  • the position of a square in Pascal's triangle and consequently of the hyperspace pyramid and the associated hypersurface is given by the line and column of Pascal's triangle.
  • the lines and columns associated with a square of Pascal's triangle correspond to the algebraic degrees and dimensions of the associated polynomials.
  • Each vertex of the same pyramid: its support pyramid has a signature formed of an equal number of coordinates whose sum represents the degree and the length the dimension minus one.
  • This signature can be interpreted in combinatorial theory either as the projective coordinates of the vertex point belonging to the pyramid, or as the powers of the monomials of the polynomial representing the associated hypersurface, or as indices of the variables composing the monomials of this same polynomial. 2.
  • the vector of homogeneous coordinates of type [a t) : a x : ...: a n ⁇ is considered as the vector of exponents of a monomial of total degree m, belonging to a polynomial of degree m in n dimensions .
  • Each trellis is associated with a travel order, also called indexing indication, points on particular Hamiltonian paths passing through all the points of the trellis according to one embodiment of the invention.
  • the local index of any monomial is considered as the index of the homogeneous point associated, that is to say the number of the point in the order of course of the chosen path.
  • any coordinate vector is coded or decoded in local mode thanks to the triplet (local index, total degree of the vector, dimension),
  • any coordinate vector is coded or decoded, in global mode, by virtue of the total index obtained by adding the local index and the global index.
  • the notion of coordinate vector is extended to any set of natural integers representing arbitrary alphanumeric codes.
  • the coding is to find bijective systems of numbering or indexing of the messages by double-numbering first in the Pascal triangle, the hyperspatial pyramid associated with the given message: the support pyramid, then the point -statement of the pyramid whose signature represents the message.
  • the integer or tuple usually the triplet of integers, resulting from this double numbering represents the encoded message in indexed form.
  • the coding can be based on different numbering and vertex-point routing methods on the same support pyramid, and the resulting code differs from one method to another.
  • the decoding is to find from the code the support pyramid of the message and the signature of the vertex-point belonging to the pyramid.
  • a method for coding information comprising obtaining a list of integers to code; determining a hyperspatial pyramid having a size suitable for encoding the integer list, the hyperspace pyramid having a plurality of vertices such that the degree of the hyperspace pyramid is equal to the sum of the integers of the integer list and the dimension of the Hyperspatial pyramid is equal to the integer number of the list of integers minus one; index the list of integers in this pyramid by means of an indexing system; and provide an indication of indexation in the hyperspace pyramid.
  • the list of integers is obtained from a file.
  • files can be used to store the list of integers.
  • the step of providing indexing of the list of integers in the hyperspace pyramid may include in one embodiment indexing storage in a file.
  • the step of providing indexing of the list of integers in the hyperspace pyramid may include in one embodiment transmitting the list of integers to a processing unit by through a network.
  • the network may include at least one of a local area network, a MAN type network and a WAN type network. In one embodiment, the transmission will take place over the Internet.
  • an indication of the indexation of the integer list in the hyperspace pyramid will include displaying said indication of indexing the integer list on a screen.
  • the method will include the steps of obtaining the indexing indication of the integer list in the hyperspace pyramid.
  • the method will further include the step of obtaining an indication of an indexing system used to generate said indication of the indexation of the integer list in the hyperspace pyramid.
  • the method will further include the step of determining by means of indexing and indicating an indexing system used said list of integers, and finally, the step of providing said list of integers.
  • the diagram of Figure 4 illustrates an embodiment for providing several coding and decoding options for a list of integers ⁇ >.
  • the function CODE is a family of encoding functions which index the list of integers ⁇ > with respect to the lattice T mn where m is the total degree of the list and n - 1 its length.
  • the result is a triplet ⁇ X, m, n>, X, representing the integer corresponding to the index of the projective point having the initial list of integers in input as vector of homogeneous coordinates.
  • this triplet can be provided to the DECODE function that will restore the initial list or separated into two parts to form a single integer Z that can be decoded bijectively without any other information.
  • the left-hand part of the diagram of FIG. 4 shows another way of constituting a single integer W, allowing a bijective decoding. It is a family of functions denoted K 2 , which couple the triplet two by two, m and n producing an integer, itself a pair at X. Successively applied two-dimensional decoding functions then make it possible to restore the initial code.
  • the right part of the diagram of Figure 4 corresponds to a bijective encoding-decoding scheme coupled to a combinatorial compression mechanism.
  • the triplet ⁇ X, m, n> is first transformed into a quadruplet, the integer X being replaced by particular combinatorial coordinates mx and nx.
  • the quadruplet (mx, nx, m, ri) is then encoded by a four-dimensional coding scheme to produce a C code.
  • This type of bijective code can be decoded by a four-dimensional inverse decoding scheme.
  • the compression principle lies in the significant decrease in the degree of the quadruplet compared to the degree of the triplet, which largely offsets the increase of an additional character between the triplet and the quadruplet.
  • the indexing of a lattice makes it possible to code with a single integer the degree and the dimension of the lattice.
  • Global indexing makes it possible to ensure the bijection between the points of a lattice and their indexing in a n-dimensional space. Instead of calculating the number of cells preceding the binomial coefficient of the lattice, the total number of points of all previous lattices is calculated. From the equation T
  • the formulation of the global index I g is obtained by summing the number of points of the lattices of the lines going from 0 to m + n - 1 1 and points of the lattices of the line m + n ranging from 0 to m: m-1
  • I g 2 m + n + ⁇ Cm (i, m + n - ⁇ ).
  • the global index added to the local index gives the total index of the point which makes it possible to find the initial coded vector without memorizing the degree and the dimension of the trellis.
  • the bijective character of coding and decoding has a price to pay in terms of size of the generated indices and calculation time.
  • optimized versions of the following GLOBAL and LOCAL algorithms will be presented later as well as several methods for calculating the local index.
  • variable ind is equivalent to the total number of points of the trellises preceding the trellis line T m + nm and the variable acc equivalent to the summation of the binomial coefficients on the lattice line.
  • the LOCAL decoding function illustrated in FIG. 5 performs the reverse search by locating on Pascal's triangle the line preceding the lattice and then isolating the lattice on its line.
  • FIG. 6 illustrates the recursive calls of the functions corresponding to the equations with r ⁇ ⁇
  • the binomial coefficients corresponding to each node of the tree provides the number of terminal leaves of their respective subtrees.
  • the different algorithms for reading and traversing trees thus provide algorithms for indexing the terminal leaves.
  • By establishing a correspondence between the production of the terminal leaves and points of the lattice it is possible to obtain a scheduling of the latter.
  • deep tree courses consist of treating the root of the tree and recursively traversing the left and right subtrees of the root. In the prefix or lexicographic depth course, the root is processed before recursive calls on the left subtrees, then right.
  • N this number
  • a the symbol
  • b the numbering base
  • N 3 ⁇ 4> 'with0 a, ⁇ b -l.
  • the numbering base m + 1 is used where m is the degree of the lattice of dimension n, and a, is the homogeneous coordinate of rank.
  • the positional index I p of the coordinate point [x 0 : ...: x n ] of the lattice T mn is:
  • Figure 7 shows the example of the indexation of the 2-dimensional cubic curve of Figure 2.
  • the indices are calculated in quaternary base. For example, the point [2: 0: 1] has
  • the figure shows a hollow indexation ie with holes in the numbering.
  • the person skilled in the art will appreciate that the hollow indexing phenomenon is one of the disadvantages of positional coding. Indeed, for a lattice T mnt the growth of the ratio p mn between the maximum index (m + 1) "of the positional coding and the corresponding maximum index of a combinatorial coding is:
  • Figure 8 illustrates the representative curves of p as a function of the growth of m and n. These make it possible to visualize the expansion of the number of digits necessary for the
  • the definition of numerical order suggests a simple algorithm for calculating the index of a projective point, based on the column-by-column count of the coordinate position of that point.
  • the index of the point [1: 2: 1: 0] of the lattice 43 of FIG. 11 15 zeros before the 1 of the first column will be counted, 4 zeros and 3 ones before 2 of the second column and 1 zero before the 1 in the third column.
  • the lattices T mn are recursively decomposed into sub-lattices T mn, T m _ X n _ x , ⁇ * *, ⁇ o , « -i ' this amounts to breaking down the representative polynomial of a hypersurface into polynomials hypersurfaces of decreasing degrees in the lower dimension.
  • exponent vectors are grouped in m + 1 tables corresponding to the monomials of the polynomials of the hypersurfaces of decreasing degree.
  • Figure 11 shows the breakdown by arrays of a lattice (4.3). The last three columns of exponents represent lattice exponent vectors (4,2), (3,2), (2,2), (1,2) and (0,2).
  • the generated arrays are in turn decomposed into lower-order arrays in dimension n-2 and so on.
  • the last two columns of the exponent vectors in the figure therefore represent the monomials of homogeneous polynomials in dimension 1.
  • the NUMORD algorithm shown in Figure 10, corresponds to the previous equation contracted.
  • the second loop allowing the iterative accumulation of the degree of the vector of exponents is indeed absorbed inside the first loop by the instruction 4.
  • the projective dimension equal to the length of the vector minus one is provided as an argument.
  • Figure 1 1 allows through an example to visualize the step by step of the function NUMORD.
  • the index ⁇ 210 ⁇ ⁇ um is the result of the summation of the pyramidal numbers carried out at lines 1 to 6 of the algorithm of FIG.
  • the decoding algorithm is based on inverting the indexing process between lines 1 to 6 of the NUMORD function.
  • the objective for calculating the numerical signature vm of the exponents is to first find the successive pyramidal numbers which made it possible to calculate the numerical index. To find the largest pyramidal number in the composition of 7 m TM, look for the largest pyramidal number is less than or equal to it in column m of Pascal's triangle. Once this number has been found and its rank in the column, the first exponent of the desired signature is obtained and this is done from column to column by decrementing each time the starting index. These steps are illustrated by the preceding table, with the calculation of the digital signature of ⁇ 210 ⁇ 5 . The last exponent of the signature is calculated simply by subtracting the sum of the exponents found from the degree of the index.
  • the lattice T mn is decomposed into sub-lattices T m _ f _ T m _ X n _ 2 i ..., T m _ l 0 , which amounts to to break down the polynomial representative of a hypersurface in hypersurfaces polynomials of a lower degree in smaller dimensions.
  • Figure 13 shows the decomposition by arrays of a lattice 43 .
  • the 4 tables correspond respectively to the lattices 33> T i2i 31 and 30 , cubic in the dimensions
  • Figure 13 illustrates the block decomposition of a lattice (4, 3).
  • the signatures of length 4 beginning either with ⁇ , ⁇ , x 2 , or x 3 form four blocks of respective sizes
  • the summation of the variations between the consecutive codes produced for the digital coding is not constant.
  • the summation of the variations between the codes 34 and 33 of the lattice ⁇ 4 3 is equal to (0,0,0,4) - (0,0,1,3) ⁇ 0 and equal to (0,0, 4.0) - (0,1,0,3) - 1 between codes 30 and 29.
  • Projective Gray coding eliminates these differences of variation and generally jumps between non-consecutive points of a mesh. These points actually have a distance on the lattice greater than one.
  • the principle of Gray Projective coding presented is essentially a replacement in the recursive tree, subtrees of odd indexing, by their symmetrical.
  • Figure 16 illustrates a Projective Gray (4.3) coding.
  • the algorithm shown in Figure 17 is a modified version of the algorithm shown in Figure 10.
  • Line 4 tests the parity of each exponent of the input signature (function type Q).
  • the indicium is inverted on line 7 and the variable s changes sign. Its value equal to 1 or -1 makes it possible to take into account the even or odd number of the exponents already treated and thus to identify the subtrees having an even number of odd successive parents who do not then have to be modified.
  • FIG. 18 illustrates the path of the points of the lattice T 4 J in projective Gray.
  • the different sections show a succession of boustrophedonic Cantorian courses.
  • the projective gray doting of the point 10 for the lattice ⁇ 64 and for the lattice T 2 4 is obtained in the following way:
  • transcoding from one coding system to another may be performed by going back and forth from one coding to the other by simple conversion between the exponent vector Vn and the vector of coordinates Vm, or by a direct equivalence between the indexing functions.
  • VN2VM and VMIVN we will speak of dual transcoding performed by the two functions VN2VM and VMIVN and we will have the following equivalences formed from the lexicographic and numerical signatures:
  • Figure 21 shows the recursive structure of.
  • the nodes a (i, j) are
  • the recursive production of an order therefore amounts to associating with a binomial coefficient a triplet composed of a reading order of the recursive tree, a function of indexing the nodes of this tree and a choice of the type combinations with or without repetitions.
  • indexing Functions of Recursive Trees The numeric, numeric and combinatorial indexing functions can be deduced sequentially from one another. The resulting geometric interpretation uses the passages between projective, affine and Euclidean spaces.
  • the numerical indexing algorithm consists in incrementing from scratch the indexes of nodes of the same level as long as they have the same parent.
  • the path of the tree is from left to right and from bottom to top.
  • the index of the last level is obtained by deducing the sum of the indices of the previous levels of the degree of the tree, which guarantees the homogeneity of the digital points produced.
  • To pass from the numerical coding space to the numeric coding space passing matrices N2X n which associate at the vertices of simplexes of digital projective spaces the vertices of projective subspaces with increasing co-ordinates. For example, the top [1: 0: 0: 0] projective simplex in 3 dimensions will be associated with the vertex [1,1,1,1].
  • the projective numerical point [ 0 will be transformed into a point numlex [cc Q , 0 + ⁇ , ⁇ ⁇ + ⁇ + 2 , 0 + or, + a 2 + a 3 ] by the matrix product with matrix N2X ⁇ .
  • the point [5: 2: 0: 4] will be transformed into a numlex point [5: 7: 7: 1 1 and its lexicographic index will be calculated from its coordinates as
  • FIG. 24 illustrates the presence of the combinatorial subspace of the 3-combinations in the reference simplex of the 3-dimensional projective space.
  • This subspace is represented by the vertices of its reference simplex obtained by projective linear transformation of the vertices of the reference simplex of the initial projective space (the simplex unit). The following linear transformation is obtained:
  • the projective points belonging to the combinatorial space and obtained by any combination of two of the vertices of the simplex therefore have strictly increasing coordinates. It is possible to establish the following equivalence theorem:
  • the indexation of a k-combination of an r-alphabet ⁇ 0, ⁇ ⁇ ⁇ , ⁇ - 1 ⁇ is equivalent by projective transformation to the numerical indexation of the trellis T r _ kk .
  • FIG. 25 illustrates the numerical indexing of a lattice T 2Ji equivalent to the indexation of
  • the 2172 digital point coordinated [2,4,1,2,0,3] T l2 mesh belonging to 5 is converted into dot numlex [2,6,7,9,9,12] by matrix multiplication with the matrix N2X 5 , then is added with the point [0,1,2,3,4] to give the combinatorial point [2,7,9,12,13,17].
  • the position of the combination [2,7,9,12,13] for the alphabet ⁇ 0,1, ⁇ ⁇ ⁇ , 17 - 1> is:
  • ORDNUM numerical coding algorithms as fast algorithms for generations of combinations. These involve in particular enumerative algorithms type HAKMEM m (R. Schroeppel, Mr. Beeler, RW Gosper. Hakmem. Technical report, Massachusetts Institute of Technology, 1972), generating combinations from the previous combination represented in binary form. As this type of algorithm, to generate the combinations, increasingly lists the numbers having the same number of bits 1 in their binary representation, it follows that the algorithm Optimized ORDNUM can also be used for this purpose.
  • Figure 26 illustrates the enumerative generation of the projective points of a lattice ⁇ 2 3 corresponding to a quadric in 3 dimensions.
  • the relation with the binary representation of the combinations calculated by the HAKMEM algorithm follows with a transposition of the indices of the combinations enumerated decreasingly in the direction of the reading.
  • the Euclidean point obtained by eliminating the last coordinate equal to 1, [ ⁇ ⁇ : a x : ⁇ : n _ x ] is then the Cantorian point in n - 1 dimensions.
  • An equivalence is thus established between the Cantorian coding of the inverse list K (x k , ..., x x ) and the numerical coding.
  • the recursive Cantorian tree is obtained by eliminating the last level of the digital recursive tree, ie the level allowing the homogenization of the numerical point.
  • Figure 28 presents the numerical and combinatorial orders as special cases of numerical order, the Cantorian order being itself a special case of the combinatorial order. It is possible to extend this classification by introducing a Hamiltonian order which will also include the projective Gray order, itself considered as a generalization of the Burstrophedonic cantorian order. New orders based on spiral curves filling the space will be described below. Search for Hamiltonian chains on lattices
  • the spiral coupling function shown in FIG. 29 makes it possible to index the relative integers two by two.
  • the Cartesian plane is traversed in a spiral according to FIG. 29.
  • the indexing polynomials of the coordinate pairs of the Cartesian plane are searched. It will be appreciated that the generation of the spiral is performed iteratively using an isosceles rectangle square rotated by ⁇ / 2, then scaled and then translated by one unit so as to ensure the continuity of the curve.
  • Figure 32 depicts an implementation of a Cartesian coding algorithm SPIORDc and Cartesian spiral decoding ORDSPIc.
  • Figure 33 depicts an implementation of an SPIORDa spiral affine encoding algorithm and ORDSPIa spiral affine decoding. Projective function of spiral coupling
  • Figure 34 shows a spiral order for a lattice (6,4) of sexics in 3 dimensions. The junctions between the stacked two-dimensional spirals are alternated, sometimes between the beginnings, sometimes between the ends of the spirals.
  • To obtain spiral chains in 4 dimensions it is necessary to chain spiral meshes in 3 dimensions to each other starting with a point, lattice (0,4) then a lattice (1,4), a lattice (2,4) etc. Optimizations of the computation of the binomial coefficients
  • posing s k in the formula the intermediate recursive form
  • the line formulation is mainly used to calculate the expansion of Newton's binomials:
  • Figure 38 illustrates an implementation of an algorithm for calculating binomials by XENUME line and YENUME column.
  • Figure 39 illustrates an embodiment of a product calculation algorithm of differences of squares.
  • the necessary operations are the addition and the assignment and the number of passages required to compute a binomial coefficient is mn + ⁇ (m (m + 3)) + n + ⁇ .
  • the principle is that a schema of computation of the binomial coefficients is established and is based on a rectangular rectangular representation of Pascal's triangle. The binomial coefficients are then evaluated column by column instead of line by line. The algorithm therefore consists of going through the boxes of a single rectangle as illustrated by FIG. 40.
  • the binomial coefficient sought is located at the tip of the rectangle and calculated from the binomial coefficients of the preceding columns.
  • the matrix product of two matrices for any powers simplifies itself in the form of the function MATPRT (see figure 42) which uses for the calculations only two vectors VnO and Vn ⁇ corresponding to the first columns of the two matrices, and stores the result in the vector Wn.
  • the matrix product of the 3 rd and 31 th columns of Pascal's triangle will be represented in rectangular form.
  • the last number of the resulting vector Wn will therefore be evaluated from the matrix product between two powers of the matrix M.
  • the number 8436 will therefore be evaluated from the powers 4 and 32 of the initial matrix having [1,1,1,1] for representative vector.
  • the naive method therefore consists in calculating all the successive powers of M up to the desired power according to the following sequence:
  • the exponent e is decomposed into a sequence of integers by means of different numbering bases or other decomposition techniques such as Zeckendorf based on Fibonacci numbers.
  • Figures 43a and 43b illustrate this principle for the matrix calculation of binomial coefficients with a binary decomposition of the exponent ( Figure 43a) or a Zeckendorf decomposition ( Figure 43b).
  • Figure 43a For a binary decomposition of the power, only columns 2, 2, 2, ⁇ - ⁇ , 2 will be used to perform the matrix products.
  • the index of the column counted from is then represented in binary form which makes it possible to show the powers of used in the binary decomposition:
  • M 87 M M x M 16 x 4 x M 2 x 1 to finally provide the matrix to the desired power showing the binomial coefficient sought as the last element of the first column of the matrix:
  • M 87 M 55 x M 2i x 8 x 3 .
  • Figure 44 illustrates the search for the position of the number 20 in the fourth column of the Pascal triangle with a graph of the function this time without translation.
  • the graphical result shows that the abscissa of the intersection of the ordinate line 20 with the curve is situated between the values 2 and 3. The number 20 is therefore
  • V 4 JV 4 J Naive method V 4 JV 4 J Naive method
  • Diophantine equations have the common characteristic of having a single root greater than one, and of being derivable continuously.
  • the principle is to improve the na ⁇ ve method described above by first searching for the number of digits of the positive root of the Diophantine equation, then calculating one by one the missing digits.
  • the search for the number of digits is done by calculating the sign of the function for successive powers of 10 of the variable x. The order of convergence therefore adapts automatically to the degree of the function.
  • the missing digits require at most 10 times the number of digits of the root, evaluations of the function.
  • Figure 45 illustrates an implementation of an algorithm of the dropper method ENCDEC.
  • Cantor + y which makes it possible to determine the coordinates of a point
  • Figure 47 illustrates an implementation of a recursive calculation algorithm of the k-th derivative DRVREC.
  • Figure 48 illustrates an implementation of a Raphson-Newton algorithm of degree n.
  • DRVSYM (4) ⁇ x - ((x + 1) (* + 2) (x + 3) (* + 4) -24 ⁇ 0 )
  • Equipped with calculation functions to position any integer in a given column of the Pascal triangle it is possible to perform the general function of decoding an integer in Pascal representation.
  • the decoding of a number in quaternary representation being a frequent operation and which we will see essential in the process of compression of the general lists of integers, a decoding of purely analytical nature will be described first, using the presented principles. previously. In this case, a sequential decoding is obtained where the successive binomial coefficients ⁇ 3 ... 0 are calculated from the positive integer roots of
  • these integer values represent the index of the hyperplane, plane, line and diagonal point preceding the point sought.
  • the vector [(4 + 1), (6 + 1), (6 + 1), (10 + 1)] is then multiplied by the matrix X2N ⁇ to restore the original code [5: 2: 0: 4].
  • the BINRP function shown in Figure 49, which searches for the position of any integer in column 4, then decrements that number of the found index in order to find the position of this new number in column 3, this process being continued to the very first column.
  • the clues found are equivalent to the 4-dimensional Cantorian affine coordinates.
  • BINRPA ⁇ 1 18) ⁇ ⁇ 5,7,7,1 1 ⁇ corresponding to the vector previously obtained by the analytical method.
  • Figure 49 illustrates an implementation of a BINRPA quaternary combinatorial decomposition algorithm of a number. It will then be possible to extend the BINRPA function to the n-ary decomposition of a number to obtain the general function BINRPN and its inverse function RPNBIN which recompose a number, given in Pascalian form, in decimal number.
  • Figure 50 illustrates an implementation of an N-ary pyramidal representation algorithm (BINRPNi).
  • Figure 51 illustrates an implementation of a global (GLOBALo) and local (LOCALo) coding optimization algorithm.
  • Figure 52 illustrates an implementation of a digital decoding algorithm (ORDNUMo and ORINUMo).
  • Figure 53 illustrates an implementation of a compressed coding and decoding algorithm (INDCOM).
  • Alphanumeric sorts The numerical order allows to create dictionaries by alphanumeric tris. For this, the principle will consist in bringing all the words of the dictionary to identical lengths and weights. The words to be sorted will be associated with projective points of the same lattice. It will be taken for length, that of the largest word, and for weight, that of the heaviest word. To sort, for example, the words ART, ARA, ARMS, ARABIC, ARABICA, coded with an alphabet of 26 letters, the index of each letter corresponding to its position in the alphabet, the following points that correspond to them on the lattice T 4 o, 7 will be scheduled. The maximum length will be inherited from the word ARABICA and the maximum weight of the word BRAS:
  • H (x) ( 0 .B k + x .B k'x + - + a k .B °) mod N.
  • B will be taken commonly equal to a power of 2, for example 256 and N equal to a prime number.
  • a character-by-character elementary encoding can therefore be made from a reduced alphabet of type ⁇ 0,1, 2,3,4,5,6,7,8,9, x, +, -, V, (,), # ⁇ This is made up of digits, arithmetic operators, parentheses, the variable x, and the pound sign used as a separator.
  • the alphabet will be extended to the letters of the alphabet if the polynomial is for symbolic processing.
  • a numerical code being assigned to each symbol of the alphabet, the equivalence table of the alphabet with n characters will simply be the list of n + 1 natural numbers. The maximum weight of this list will therefore be (n + ⁇ ) 2 .
  • ⁇ " ⁇ 40,120,48,94,50,43,120,49,94,50,43,120,50,94,50,45,40,98,94,50, 45,97,94,50,41, 42, 120.51, 94.50, 41, 94, 50, 45, 52, 42, 97, 94, 50, 42, 40, 120, 48, 94,
  • Algorithmic performance problems are closely related to selected representations, and memory problems are partly caused by losses due to hollow polynomials.
  • This separately stored information can therefore be the signed numerical values of the coefficients, but also pointers on symbolic calculation functions of the coefficients or relational database indices to establish geometrical constraints between different polynomials (variational CADCAM).
  • T 0 [k 0 , 0, k 2 , 0, k,, 0,0,0,0, k 9 , 0, *,,, 0,0, k u , 0,0,0,0,0 ,0 , 0,0,0,0, k 25 , 0, k 21 , 0, 0, k 30 , 0,0,0, k M ]
  • the encoding of the hollow vectors can be realized in several different ways.
  • the most common method is the so-called rank-and-value method described by Lehmer (DH Lehmer, The Machine Tools of Combinatorics, in EF Beckenbach, Editor, Applied Combinatorial Mathematics, pp. 5-31, Wiley, New York. 1964).
  • Lehmer DH Lehmer, The Machine Tools of Combinatorics, in EF Beckenbach, Editor, Applied Combinatorial Mathematics, pp. 5-31, Wiley, New York. 1964.
  • the coding is performed by a sequence of integer pairs formed of the position of each integer in the hollow list, and then of its value. A zero is put at the end of the list to signify the end of the message.
  • the previous table To To is thus coded as follows:
  • the positions of the non-zero values can also be encoded separately using, for example, the combinatorial compression technique. Then there will be the following compressed code to store the locations of the non-zero values of To:
  • the fast indexing functions of monomials which make it possible to produce the product of two multivariable polynomials in a vectorial way by direct indexing must then be used.
  • the MPLNUM algorithm illustrated in FIG. 54 uses indexing in numerical order by multiplying each monomial of the first polynomial by each polynomial of the second, which is known as the naive multiplication algorithm of two polynomials.
  • One of the advantages of the algorithm presented is that it can be easily extended to the multiplications of hollow vectors.
  • the symbolic multiplication algorithm of two multivariate polynomials is based on the elementary operation of the product of two monomials, the indexation of the resulting monomial and the summation of the monomials of the same rank.
  • the MPLNUM function realizes the symbolic product of two polynomials in a given dimension.
  • the degree of the resulting polynomial dgr calculated in line 1 and the numbers of the monomials of the two multiplied polynomials and the resulting polynomial are calculated from line 2 to line 9.
  • the initialization of all the terms of the resulting vector to zero is carried out at the line 10.
  • a loop is made on the number Iga of the monomials of the polynomial a in line 1 1 and on the number Igb of the monomials of the polynomial b in line 12.
  • the signatures in numerical order of the two polynomials a and b are obtained on lines 13 and 14.
  • the multiplication of the monomials is carried out by the addition of the signatures siga and sigb to the line 15.
  • the index of the resulting monomial is calculated in line 16.
  • the resulting monomials of the same rank are summed and accumulated in the vector associated with the resulting polynomials at line 17.
  • MPLNUM [ ⁇ , ⁇ 1a, ⁇ 1, ⁇ 4, ⁇ 5], [ ⁇ 1, bbl, b1], 2, 1, 2) ⁇ [aO * bO, aO * b1 + al * b0, al * bl + al * bO, ⁇ 1 * bl, ⁇ 0 * bl + ⁇ 3 * b0, ⁇ 1 * bl + ⁇ 3 * bl + ⁇ 4 * b0, ⁇ 1 * bl + ⁇ 4 * bl, ⁇ 3 * bl + ⁇ 5 * b0, ⁇ 4 * bl + ⁇ 5 * bl, a5 * bl].
  • the computer 300 will comprise, for example, a processor 310, a data bus 312, a data storage unit 314, a port communication unit 316, a display unit 318 and a keyboard 320.
  • the processor 310 is adapted to process instructions.
  • the person skilled in the art will appreciate that various types of processors can be used to perform the instruction processing.
  • the data storage unit 314 is adapted to store data.
  • the person skilled in the art will appreciate that various types of data storage units may be used to perform such storage.
  • the communication port 316 is used to exchange information between the computer 300 and another processing unit not shown in FIG. 30. The person skilled in the art will appreciate that the communication port 316 depends on the type of connection used. between the computer 300 and the other processing unit.
  • the display unit 318 is used to display data to a user. The person skilled in the art will appreciate that various types of display units may be used.
  • the keyboard 320 is used to allow a user to provide data to the computer 300. Again, the person skilled in the art will appreciate that various types of keyboards may be used.
  • processor 310 the data storage unit 314, the communication port 316, the display unit 318 and the keyboard 320 are operatively connected together by means of the data bus 312.
  • the data storage unit 314 includes an operating system 322.
  • the operating system 322 may be of different types.
  • the data storage unit 314 furthermore comprises a program 324 that can be executed by the processor 310 and whose execution makes it possible to encode information. It will be appreciated by the person skilled in the art that a program whose execution will decode information may also be stored in the data storage unit 314.
  • the program for encoding information includes instructions for obtaining a list of integers to code. It will be appreciated that the list of integers to be encoded can be obtained in various ways. In one embodiment, the list of integers will be entered by a user using the keyboard 320. In another embodiment the list of integers will be obtained from a file located in the data storage unit 314 or received by the user. intermediate of the communication port 316.
  • the program for encoding information further includes instructions for determining a hyperspace pyramid sized to code the list. of integers, the hyperspace pyramid having a plurality of vertices whose number is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers of the integer list and by the dimension of the hyperspace pyramid which is equal to number of integers in the list of integers minus one.
  • the program for encoding information includes instructions for indexing the list of integers in this pyramid by means of an indexing system. As mentioned above, various indexing systems may be used.
  • the program for encoding information includes instructions for providing an indication of the indexing of the integer list in the hyperspace pyramid to thereby encode said list of integers to be encoded.
  • the indication of the indexing of the list of integers in the hyperspace pyramid can be provided in various ways.
  • the indication of the indexing of the list of integers may be displayed on the display unit 318 (for example a screen).
  • the indication of the indexing of the list of integers may be stored in a file located in the data storage unit 314 or it may be transmitted via the communication port 316 to another unit of data. treatment.
  • an information storage device may be provided for storing executable instructions by a processor.
  • This information executable by a processor will cause the processor to execute a method including obtaining a list of integers to code; determining a hyperspatial pyramid having a size suitable for encoding the list of integers, the hyperspace pyramid having a plurality of vertices the number of which is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers of the integer list and by the dimension of the hyperspatial pyramid which is equal to the number of integers in the list of integers minus one; index the list of integers in this pyramid by means of an indexing system; and providing an indication of indexing the list of integers in the hyperspace pyramid to thereby encode said list of integers to be encoded.
  • a method for encoding information comprising:
  • a hyperspatial pyramid having a size suitable for encoding the list of integers, the hyperspace pyramid having a plurality of vertices the number of which is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers of the integer list and by the dimension of the hyperspatial pyramid which is equal to the number of integers in the list of integers minus one;
  • Clause 3 The method claimed in clause 1, in which the indexing system indexes each of the plurality of vertices of said hyperspace pyramid.
  • Clause 4 The method claimed in clause 1, in which the indication of the indexation of the list of integers in the hyperspace pyramid includes an integer representing the index of the projective point in the indexing system, m the degree total of said list of integers and n the number of integers in the list of integers.
  • Clause 5 The method claimed in clause 4, further comprising transforming the integer representing the index of the projective point by mx and nx combinatorial coordinates.
  • Clause 6 The method claimed in clause 4, further comprising the transformation of m the total degree of the list of integers and n the number of integers in the list of integers by an integer Y representing a global index.
  • Clause 7 The method claimed in clause 6, further comprising summing the integer Y representing a global index to the integer representing the index of the projective point to provide a total index Z, the indication of the indexation in the hyperspace pyramid including the total index Z.
  • Clause 8 The method claimed in one of clauses 1 to 7, in which the list of integers is obtained from a file.
  • Clause 9 The method claimed in one of clauses 1 to 8, wherein the step of providing indexing indication in the hyperspace pyramid includes storing said indexing indication in a file.
  • Clause 10 The method claimed in one of clauses 1 to 8, wherein the step of providing indication of the indexation of the integer list in the hyperspace pyramid includes transmitting the indexing of the list of to a processing unit via a network.
  • Clause 11 The method claimed in one of clauses 1 to 10 for encoding a list of integers, the method comprising providing the list of integers and generating the list of integers by means of the list of integers.
  • Clause 12 The method claimed in one of clauses 1 to 8, wherein the step of providing indication of the indexing of the integer list in the hyperspace pyramid includes displaying said indication of the indexation of the list of integers on a screen.
  • Clause 13 The use of the method claimed in clauses 1 to 3 and 4 to 7 to compress a string in which the string is associated with said list of integers.
  • Clause 14 A method for encoding a list of lists, the method comprising the iterative use of the method claimed in one of clauses 1 to 3 and 4 to 7 for encoding a list of lists.
  • Clause 15 The use of the method claimed in clause 1 to encrypt a list of integers, in which the indexing of the list of integers corresponds to the encryption of the list of integers.
  • Clause 16 A method for decoding information encoded by the method for encoding information claimed in any of clauses 1 to 7, the method comprising:
  • a computer comprising:
  • a data storage unit comprising a program configured to be executed by the processor, the program for encoding information, the program comprising:
  • a hyperspatial pyramid having a size suitable for encoding the integer list, the hyperspace pyramid having a plurality of vertices the number of which is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers in the list of integers and by the dimension of the hyperspatial pyramid which is equal to the number of integers in the list of integers minus one;
  • An information storage device for storing executable instructions by a processor, which when executed will cause the processor to execute a method of encoding information, the method comprising obtaining a list of integers to code; determine a hyperspatial pyramid with a suitable size to encode the list of integers, the hyperspace pyramid having a plurality of vertices whose number is determined by the degree of the hyperspace pyramid which is equal to the sum of the integers of the integer list and the dimension of the hyperspace pyramid which is equal to the number of integers in the list of integers minus one; index the list of integers in this pyramid by means of an indexing system; and providing an indication of indexing the list of integers in the hyperspace pyramid to thereby encode said list of integers to be encoded.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Data Mining & Analysis (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Computing Systems (AREA)
  • Algebra (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

Une méthode et un appareil sont décrits pour coder de l'information, la méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation dans la pyramide hyperspatiale.

Description

MÉTHODE ET SYSTÈME POUR CODER DE L'INFORMATION Référence croisées à des demandes correspondantes
Cette demande de brevet revendique la date de priorité créé par le dépôt de la demande canadienne n° 2,758,243, dont le titre est "Méthode et appareil pour coder de / 'information" qui a été déposée le 10 novembre 201 1.
Domaine d'application
Cette invention a trait au domaine du codage. Plus précisément, cette innovation a trait à une méthode et à un système pour coder de l'information au moyen d'une pyramide hyperspatiale. Art antérieur
Soit x0,..., n des nombres entiers d'une liste de nombre entiers et X le nombre entier généré; coder une liste d'entiers naturels en un seul entier et son inverse reviennent à trouver des fonctions de codage et décodage assurant la correspondance suivante :
Code (x0,..., n)→X Décode (X)→ x0,..., n Un système de codage consiste à établir une loi de correspondance appelée code entre les informations à représenter et les nombres obtenus, de telle sorte qu'à chaque information corresponde un et généralement un seul nombre à partir duquel il sera possible de retrouver les informations initiales. Certaines stratégies de codage reposent sur des mécanismes bijectifs fonctionnels contenus par exemple dans le théorème fondamental de l'arithmétique ou dans des méthodes de génération polynomiale des nombres. Dans le premier cas, l'unicité de la décomposition d'un nombre en un produit de facteurs premiers est la clé du mécanisme bijectif. Dans le second cas, l'unicité de la décomposition d'un nombre en une somme de nombres élémentaires doit être préalablement établie.
Par exemple, le codage de Fibonacci permet de concaténer une liste d'entiers en un nombre binaire tel que les séparateurs entre les nombres entiers soient représentés par le pattern binaire 1 1. Fibonacci([\ , 2,3,9,8,7])→ {1 101 1001110001 10000110101 }2→ {57088107}
Figure imgf000004_0001
n^o^ io^ Tîo^ô^oïoîi
La personne versée dans le domaine appréciera que de manière générale, au delà, du choix théorique de la méthode de codage, la longueur de la liste à coder et la taille des nombres entiers à traiter doivent être considérées comme un problème essentiel du point de vue pratique et applicatif. La personne versée dans le domaine appréciera aussi qu'en dehors du problème de compression de la liste d'entiers, la taille du code généré, c'est à dire son nombre de digits représentatifs, est un élément fondamental dans le choix des méthodes de codage. Compte tenu de la taille des données à traiter et des niveaux de complexité algorithmique rencontrés, les phénomènes d'écroulement des performances, particulièrement lors des phases de décodage, sont pratiquement immédiats et disqualifient certaines méthodes théoriquement intéressantes en ce qui concerne la phase initiale de codage.
Les différentes familles de codage abordant un certain nombre de problématiques reliées par exemple aux thématiques de compression, de transmission, de structuration, ou de cryptage des données, les propriétés des codes générés peuvent être dans ce cas très différentes. Dans les systèmes de codage à indexation, la loi de correspondance est une relation d'ordre qui calcule le rang d'une liste ou séquence de nombres entiers, et qui permet de classer ou de trier cette liste à partir d'un nombre entier unique qui pourra à son tour être décodé pour restituer la liste.
La personne versée dans le domaine appréciera qu'il y ait de nombreuses applications possibles au codage. En particulier, l'ordonnancement de certaines séquences d'entiers est généralement le premier objectif des méthodes de codage par indexation. Les séquences à ordonner relèvent essentiellement de la combinatoire et sont par exemple des combinaisons ou des permutations qui doivent être ordonnées. Les applications sont vastes allant de l'algèbre linéaire, géométrie algébrique, théorie des graphes au classement lexicographique et alphabétique de dictionnaires ou à l'énumération et au positionnement de combinaisons en théorie des jeux. L'indexation des treillis est particulièrement importante dans les problèmes de routage et d'algorithmique parallèle. Ainsi le routage peut être défini comme un mécanisme logiciel ou matériel qui achemine les informations entre la source et la destination lors d'une communication dans un réseau incomplètement connecté de type statique ou dynamique : il effectue le choix des chemins lorsqu'il y en a plusieurs, il gère les conflits, enfin il assure que les messages arrivent bien et dans le bon ordre.
L'adressage des données et de leurs zones de mémorisation dans des bases ou des structures de données est à la base de l'accès à l'information numérique et à sa structuration. L'intérêt du codage par indexation de l'information est de se libérer de toute organisation physique de la mémoire, préalable à la manipulation des données. Cette organisation physique est typiquement articulée autour des notions de tableaux ou de listes dont la structure, la taille et la localisation mémoire doivent être explicitement déclarées. A l'opposé, le codage par indexation privilégie une description implicite de l'information au travers des propriétés du nombre encodé. Par exemple, la représentation de l'information dans des tableurs utilise des formats standards de description qui spécifient les conventions d'organisation des fichiers. Ces formats, comme par exemple le Comma Separated Value, décrivent de manière explicite de quelle manière l'information doit être enregistrée.
La personne versée dans le domaine appréciera de plus que les fonctions d'indexation des treillis peuvent être utilisées comme de puissantes fonctions de hachage. Afin d'optimiser l'accès à l'information, les techniques de hachage permettent à partir de fonctions mathématiques dîtes de hachage de calculer directement l'indice d'une table à partir d'une chaîne alphanumérique appelée la clé. La zone mémoire directement indexée contient alors les informations associées à la clé ou un nouveau jeu d'adresses permettant d'accéder indirectement à ces adresses.
La personne versée dans le domaine appréciera aussi que l'identification électronique est de plus en plus utilisée pour assurer la traçabilité des objets, des aliments ou des êtres vivants. Les différentes typologies d'identifiants sont les identifiants pour l'immatriculation, pour l'indexation de l'information : la clé primaire, ou alors pour la connexion. Les systèmes de codage par indexation sont particulièrement bien adaptés à W ces types de problème car ils facilitent entre autres les tris alphanumériques et permettent une identification rapide dans les bases de données.
Enfin, les fonctions d'encodage ou de couplage mathématique sont souvent à la base des systèmes de cryptage et peuvent être à la base de la relation biunivoque entre l'opération de codage et de décodage. L'utilisation des propriétés des nombres codés, comme par exemple la décomposition en produit de nombres premiers, peut également servir d'approche indépendante ou complémentaire.
Dans le codage positionnel, les systèmes de numération positionnelle sont utilisés pour coder et décoder des vecteurs de nombres entiers à partir d'une base de numération supérieure au cardinal k - 1 de l'alphabet de codage. Le codage d'un vecteur (α0, · · · ακ) en base k sera alors
IB = ccQ.Bk + avBk-l + - - - + ak .B°
Si par exemple les entiers (1 , 2, 3, 4, 5, 6, 7, 8, 9) sont associés aux lettres de l'alphabet (A, B, C, D, E, F, G, H, I), le code suivant sera obtenu 2.106 +1.105 + 2.104 + 2.103 + 1.102 + 7.101 + 5.10°→ {2122175}10 correspondant au mot
BABBAGE codé en base 10. Dans ce cas, l'alphabet ne dépassant pas le nombre de digits disponible, le code obtenu correspond à une simple substitution des lettres du mot par les digits associés. En enrichissant l'alphabet, le calcul polynomial devient nécessaire, les lettres pouvant être codées sur plus de un digit, par exemple en numération hexadécimale avec A = 10, 5 = 1 1 · · · .
La personne versée dans le domaine appréciera que le codage d'une liste d'entiers puisse être effectué à partir du système de représentation modulaire des nombres entiers ou Residue Number System (RNS). Le système RNS est défini à partir d'un ensemble de nombres premiers deux à deux nommés modules et noté {nto, m;, · · ·, m„} . Par conséquent PGCD(mi,mj) = 1, avec i≠ j. Un nombre entier X peut être alors représenté par un ensemble d'entiers appelés résidus {r0, rlt · · ·, rn,} tel que x = X mod rrij avec < Xi < mi. Cette représentation est d'autre part unique pour X < M - 1 avec M ·
Figure imgf000006_0001
Le principe de codage est donc de considérer la liste des nombres entiers à coder comme une liste de résidus et de trouver la représentation décimale associée. On peut pour trouver des modules supérieurs aux entiers respectifs de la liste, utiliser une séquence de nombres premiers successifs tous supérieurs à leurs résidus respectifs ou débutant par le nombre premier immédiatement supérieur au nombre entier maximum de la liste à coder. L'exemple ci-après permet de coder le point projectif [69, 78, 73, 71 , 77, 65] en dimension 5 à partir du module 73. La fonction Chinois de codage est essentiellement une fonction permettant de résoudre un système de congruences à partir d'une liste d'entiers résidus.
Chinois ([69, 78, 73, 71 , 77, 65], [73, 79, 83, 89, 97, 101])→ {252617134512} 252617134512 mo^ 73 = 69 » » ' 252617134512 moi 101 = 65
Le décodage du nombre décimal n'étant pas unique, il en résulte qu'il faut connaître le triplet (Code, module initial, longueur de la liste) pour effectuer le décodage. Le triplet nécessaire sera donc noté {252617134512}(73j5). La liste pourrait être codée avec une infinité d'autres triplets comme par exemple {412251249819} (79,5), 79 étant dans ce cas le premier nombre entier supérieur à 78.
Le codage de Cantor est associé à la notion de fonction de couplage développée pour répondre au problème d'énumérabilité des entiers naturels. La fonction de couplage de Cantor se ramène à un polynôme du second degré ayant les abscisses et les ordonnées du plan cartésien comme variable. La figure 1 présente l'ordre dans lequel le polynôme associe les couples de coordonnées aux indices selon la formule suivante. Par exemple IK (1 ,2) ^ 8. Il est possible d'obtenir un second polynôme de couplage en substituant x à y et dans ce cas IK (1 ,2)— >· 7 .
_ (x + y) * (x + y + l) t ^
2 + y
La variante illustrée à la figure lb présente une variante boustrophédonique.
La fonction de couplage de Cantor permettant le codage et le décodage d'une paire d'entiers naturels a été étendue à un nombre quelconque d'entiers de deux manières différentes. La première revient à regrouper les entiers en constituant de manière successive des paires de paires d'entiers. Cette méthode a l'avantage de la simplicité de la fonction de codage initiale de Cantor : un polynôme de degré 2 mais génère des polynômes de degré n2. Cette croissance exponentielle affecte en particulier la taille des indices calculés. Une alternative à cette approche est l'extension à n-dimensions de la fonction de couplage. Une expression à base de coefficients binomiaux est présentée par Cegielski et Richard sous la forme suivante :
( x, + ... + X. + k -\ x, + ... + xk , + k - 2
K(x ,...,xk) = + + ·
k - l
Figure imgf000008_0001
Malheureusement le codage hyperspatial de Cantor n'est pas bijectif. Des vecteurs de dimensions différentes peuvent générer le même code. Ce problème est aussi existant avec le couplage successif par paires. Dans ce cas, on peut par convention ajouter l'arité du vecteur à coder comme coordonnée supplémentaire.
Dans le codage d'Ernesto Pascal, un entier N peut être représenté d'une manière unique pour un certain degré n de la manière suivante :
N = ,x„ >■·■> x2 > Xj > 0 .
Figure imgf000008_0002
Le nombre 1000 sera par exemple représenté par la séquence { 12,9,8,7,6,5,3} Cm correspondant aux sept premières colonnes du triangle de Pascal ou alors par la séquence { 19,8,3 }C 3 ns correspondant aux trois premières colonnes. Le codage s'applique donc à des séquences d'entiers strictement décroissantes et est utilisé pour solutionner le problème d'ordonnancement lexicographique des r-combinaisons de Cl ^2 de { 1,2,· · · , r) . La formule peut être légèrement modifiée pour calculer l'indice d'une combinaison donnée sous la forme d'une séquence d'entiers croissante et il est obtenu :
Figure imgf000009_0001
Il y a donc un besoin pour une méthode de codage de l'information qui résout au moins un problème de l'art antérieur.
Liste des figures La figure la illustre l'ordre cantorien alors que figure lb illustre l'ordre cantorien boustrophédonique .
La figure 2 illustre le triangle de De Gua de Malves et son extension projective.
La figure 3 illustre un treillis pyramidal et l'étiquetage des coordonnées projectives.
La figure 4 illustre une réalisation du système de codage et de décodage. La figure 5 illustre une implémentation de l'algorithme GLOBAL et une implémentation de l'algorithme LOCAL.
La figure 6 illustre des arbres récursifs pour
Figure imgf000009_0002
La figure 7 illustre l'indexation positionnelle pour T3 2 en base quaternaire.
La figure 8 illustre l'expansion des grands entiers. La figure 9 illustre l'ordre numérique pour le treillis T4,3.
La figure 10 illustre une implémentation de l'algorithme NUMORD.
La figure 1 1 illustre une décomposition pyramidale d'un nombre. La figure 12 illustre une implémentation de l'algorithme ORDNUM.
La figure 13 illustre le codage lexicographique du treillis T4,3. La figure 14 illustre une implémentation de l'algorithme LEXORD. La figure 15 illustre une implémentation de l'algorithme ORDLEX.
La figure 16 illustre le codage de Gray projectif (4,3).
La figure 17 illustre une implémentation de l'algorithme GRAORD.
La figure 18 illustre le parcours de T4,3 en Gray projectif. La figure 19 illustre une implémentation de l'algorithme ORDGRA.
La figure 20 illustre une implémentation de l'algorithme VN2VM et de l'algorithme VM2VN.
La figure 21 illustre l'arbre combinatoire
Figure imgf000010_0001
(6
La figure 22 illustre l'arbre et les étiquettes numériques.
v4 La figure 23 illustre l'arbre et les étiquettes lexicographiques.
Figure imgf000010_0002
La figure 24 illustre un exemple de sous-espace projectif combinatoire. La figure 25 illustre un exemple de bijection entre points projectifs et combinaisons. La figure 26 illustre un exemple de génération projective et binaire des combinaisons. La figure 27 illustre les coordonnées euclidiennes et affines d'un point cantorien. La figure 28 illustre la taxonomie des ordres. La figure 29 illustre des chemins cantoriens.
La figure 30 illustre une implémentation possible de la méthode pour coder de l'information.
La figure 31 illustre des chemins en spirale. La figure 32 illustre une implémentation de l'algorithme SPIORDc et de l'algorithme ORDSPIc.
La figure 33 illustre une implémentation de l'algorithme SPIORDa et de l'algorithme ORDSPIa. La figure 34 illustre une chaîne en spirale pour T63 . La figure 35 illustre un mécanisme de convolution.
La figure 36 illustre des convolutions de Vandermonde pour
Figure imgf000011_0001
La figure 37 illustre une implémentation de l'algorithme CRKREC.
La figure 38 illustre une implémentation de l'algorithme XENUME et de l'algorithme YENUME.
La figure 39 illustre une implémentation de l'algorithme COMBO.
La figure 40 illustre le calcul optimisé du coefficient binomial.
La figure 41 illustre une implémentation de l'algorithme PRODYN.
La figure 42 illustre une implémentation de l'algorithme MATPRT. Les figures 43a et 43b illustrent une multiplication matricielle entre colonnes.
La figure 44 illustre une courbe qui représente pour une dimension donnée les valeurs des coefficients binomiaux.
La figure 45 illustre une implémentation de l'algorithme ENCDEC et de l'algorithme DIGBIN. La figure 46 illustre une implémentation de l'algorithme NUMFCT. La figure 47 illustre une implémentation de l'algorithme DRVREC. La figure 48 illustre une implémentation de l'algorithme DRVSYM.
La figure 49 illustre une implémentation de l'algorithme BINRP4.
La figure 50 illustre une implémentation de l'algorithme BINRPNi et de l'algorithme RPNBINi. La figure 51 illustre une implémentation de l'algorithme GLOBALo et de l'algorithme LOCALo.
La figure 52 illustre une implémentation de l'algorithme ORDNUMo et de l'algorithme ORINUMo.
La figure 53 illustre une implémentation de l'algorithme INDCOM et de l'algorithme COMIND.
La figure 54 illustre une implémentation de l'algorithme MPLNUM. Sommaire
Selon un aspect de l'invention, une méthode est décrite pour coder de l'information, la méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
Selon une réalisation de la méthode décrite ci-avant, la méthode comprend de plus fournir une liste de codes alphanumériques et transformer la liste de codes alphanumériques en liste d'entiers à coder. Selon une réalisation de la méthode décrite ci-avant, le système d'indexation permet d'indexer chacun de la pluralité de sommets de ladite pyramide hyperspatiale. Selon une réalisation de la méthode décrite ci-avant, l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend un entier représentant l'indice du point projectif dans le système d'indexation, m le degré total de ladite liste d'entiers et n le nombre d'entiers de la liste d'entiers. Selon une réalisation de la méthode décrite ci-avant, la méthode comprend de plus transformer l'entier représentant l'indice du point projectif par des coordonnées combinatoires mx et nx.
Selon une réalisation de la méthode décrite ci-avant, la méthode comprend de plus la transformation de m le degré total de la liste d'entiers et n le nombre d'entiers de la liste d'entiers par un entier Y représentant un indice global.
Selon une réalisation de la méthode décrite ci-avant, la méthode comprend de plus effectuer la sommation de l'entier Y représentant un indice global à l'entier représentant l'indice du point projectif pour fournir un indice total Z, l'indication de l'indexation dans la pyramide hyperspatiale comprenant l'indice total Z. Selon une réalisation de la méthode décrite ci-avant, la liste d'entiers est obtenue d'un fichier.
Selon une réalisation de la méthode décrite ci-avant, l'étape de fournir indication de l'indexation dans la pyramide hyperspatiale comprend le stockage de ladite indication de l'indexation dans un fichier. Selon une réalisation de la méthode décrite ci-avant, l'étape de fournir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend la transmission de ladite indication de l'indexation de la liste d'entiers à une unité de traitement par l'intermédiaire d'un réseau.
Selon une réalisation de la méthode décrite ci-avant, la méthode est utilisée pour coder une liste d'entiers relatifs, la méthode comprenant fournir la liste d'entiers relatifs et générer la liste d'entiers au moyen de la liste d'entiers relatifs. Selon une réalisation de la méthode décrite ci-avant, l'étape de fournir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend l'affichage de ladite indication de l'indexation de la liste d'entiers sur un écran.
Selon une autre réalisation, la méthode décrite ci-avant est utilisée pour compresser une chaîne de caractères dans laquelle la chaîne de caractères est associée à ladite liste d'entiers.
Selon une autre réalisation, la méthode décrite ci-avant est utilisée pour coder une liste de listes, la méthode comprenant l'utilisation itérative de la méthode décrite ci-avant pour coder une liste de listes. Selon une autre réalisation, la méthode décrite ci-avant est utilisée pour crypter une liste d'entiers, dans laquelle l'indexation de la liste d'entiers correspond au cryptage de la liste d'entiers.
Selon un aspect large de l'invention une méthode est décrite pour décoder de l'information codée au moyen de la méthode pour coder de l'information décrite ci-avant, la méthode comprenant obtenir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale; obtenir une indication d'un système d'indexation utilisé pour générer ladite indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale et déterminer au moyen de l'indexation et de l'indication d'un système d'indexation utilisé ladite liste d'entiers. Selon un aspect large de l'invention, un dispositif de stockage d'information est décrit pour stocker des instructions exécutables par un processeur, qui quand elles sont exécutées vont causer l'exécution par le processeur d'une méthode pour coder de l'information, la méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
Selon un aspect large de l'invention, un ordinateur est décrit, l'ordinateur comprenant une unité d'affichage; un processeur; une unité de stockage des données comprenant un programme configuré pour être exécuté par le processeur, le programme permettant de coder de l'information, le programme comprenant des instructions pour obtenir une liste d'entiers à coder; des instructions pour déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; des instructions pour indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; des instructions pour fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder. Un avantage du système décrit est qu'il s'agit d'un système polymorphe "plusieurs en un" car il s'agit d'un système combiné de codage et d'indexation mais également de transcodage entre systèmes de codage combinatoire utilisant les coefficients binomiaux.
Un avantage du système décrit est qu'il s'adresse au codage/indexati on/transcodage de listes d'entiers quelconques sans structures combinatoires prédéfinies aussi bien qu'à des listes particulières avec structures combinatoires prédéfinies comme les listes de coefficients de polynômes ou les listes de combinaisons sans répétitions.
Un autre avantage du système décrit est qu'il permet de travailler en mode codage bijectif Code (X)→ Y et Décode (Y)→ X ou en mode cryptage Code (X)→ Y Décode (Y, clé 1 , clé 2)→X. Un autre avantage du système décrit est qu'il peut apporter une solution à différents problèmes tels la nature et la taille des données, la taille du programme de codage/décodage, la taille du code généré et les propriétés du code généré. Ainsi pour ce qui est de la nature et la taille des données, la méthode décrite peut permettre l'utilisation de données structurées ou non de taille quelconque.
Pour ce qui est de la taille du programme de codage/décodage, il est possiblement implémentable au moyen de quelques dizaines d'instructions et d'une librairie standard de traitement des entiers à multiprécisions, comme par exemple GMP.
Pour ce qui est de la taille du code généré, il n'y a pas d'explosion de la taille que ce soit en mode compressé ou non du fait qu'il n'y a pas de factorisation par nombres premiers ou de calculs utilisant les exponentielles.
Pour ce qui est des performances du codage et du décodage, il peut être possible d'utiliser des algorithmes optimisés en utilisant des algorithmes de nouvelle génération pour le calcul et la recherche des coefficients binomiaux dans le triangle de Pascal.
Pour ce qui est des propriétés du code généré, le code généré peut être indexé multi-usage pour par exemple au moins un parmi l'ordonnancement des listes d'entier, les architectures de routage, l'adressage et le hachage de données, l'identification électronique et la cryptographie.
Description détaillée
La personne versée dans le domaine appréciera que le triangle de Pascal possède de nombreuses propriétés. En particulier, pour le dénombrement des monômes d'un polynôme homogène de degré m en dimension n :
Figure imgf000016_0001
Il est aussi à noter que Cr(m,n)=Cr(n,m) et conséquemment l'écriture du coefficient binomial central de la ligne r, Cr(r,r). Par ailleurs, la somme des coefficients binomiaux de cette ligne a pour valeur :
Figure imgf000016_0002
Le calcul d'un coefficient binomial à partir des coefficients binomiaux situés dans la colonne adjacente de gauche ou alors dans la diagonale juste supérieure est respectivement :
Figure imgf000017_0001
De plus, la formule par récurrence calculant un coefficient binomial à partir de ses deux voisins supérieurs permet de construire de manière naïve le triangle de Pascal et s'exprime : avec r≥l .
Figure imgf000017_0002
Les nombres pyramidaux sont des nombres figurés, c'est à dire des nombres décomposés et visualisés à partir de points répartis sur des polytopes réguliers. Le triangle de Pascal est formé à partir de nombres triangulaires, tétraédriques et généralement hypertétraédriques.
Le système divulgué est conçu à partir de l'idée d'utiliser les propriétés combinatoires du triangle de Pascal et les propriétés algébriques des extensions projectives hyperspatiales du triangle de De Gua de Malves comme système général d'indexation et de codage des listes d'entiers naturels. Pour cela, la correspondance biunivoque entre les monômes d'un polynôme Pm n et les points d'un treillis Tm n va être utilisée. L'ordonnancement des monômes de ce polynôme sera par conséquent équivalent à l'ordonnancement des points de ce treillis. La figure 2 montre la transition entre le triangle original décrit par De Gua et son extension projective en deux dimensions pour une courbe du troisième degré.
Définition et propriétés des treillis pyramidaux
Il sera apprécié par la personne versée dans le domaine que directement lié à la notion de nombre pyramidal, un treillis pyramidal est autant une structure combinatoire qu'une structure géométrique hyperspatiale dont l'étude relève de la géométrie algébrique. Les treillis se présentent sous forme de pyramides hyperspatiales, comme par exemple le tétraèdre de la figure 3 ou le triangle de la figure 2. Un treillis pyramidal tétraédrique, noté Tm n correspondant à la ligne m + n et à la colonne m du triangle de Pascal, est associé à chaque coefficient binomial donc une configuration projective hypertétraédrique de dimension n po points homogènes, linéairement
Figure imgf000018_0001
dépendants. Les points du treillis sont organisés de manière combinatoire, en sous-treillis de dimension n - \ et de degré allant de 0 à m - \ (règle de la sommation de la diagonale). Chaque treillis est localisé dans le triangle de Pascal par le couple (m,n) ou par la sommation de tous les points de tous les treillis précédents, ce que nous nommerons l'indice global. Le nombre de points, le nombre pyramidal associé, est égal par définition au nombre de monômes d'un polynôme homogène de degré m en n dimensions. Les coordonnées homogènes projectives des points d'un treillis Tm n peuvent donc être interprétées comme les exposants des monômes d'un polynôme associé de degré m et de dimension n .
Chaque case du triangle de Pascal correspond à une pyramide hyperspatiale dont le nombre de sommets est égal au nombre indiqué dans la case.
Ordre des monômes des polynômes homogènes
Un monôme x« en *o > *i »-» ** est défini comme le produit Λ" Λ"° '"Λ¾ et le degré total de est défini comme \™\=™» +™x+,...,+mk ή vm = (m^ m^ m,) ? représente le vecteur des exposants, et x °' l "' k / , représente le vecteur des indices des variables avec no≤ni-≤nk _
Les définitions euclidiennes des ordres des monômes des polynômes non homogènes sont basées sur la notion d'ordre lexicographique et de degré total des monômes, c'est à dire la somme des exposants des variables des monômes. En combinant ces deux notions, on obtient en particulier, l'ordre lexicographique pur, l'ordre total puis lexicographique, l'ordre total puis lexicographique inverse. Dans le cas des polynômes homogènes, tous les monômes ont par définition le même degré total et l'ordonnancement des monômes peut être réalisé à partir de deux ordres projectifs lexicographiques duals, l'un sur les exposants et l'autre sur les indices, les monômes étant représentés en notation tensorielle. Les ordres lexicographiques inverses sont dans ce cas de simples variantes ascendantes ou descendantes des ordres lexicographiques.
Sera nommé ordre numérique l'ordre lexicographique sur les exposants tel que vma ^mm vmfi sj et §j seuiement la valeur la plus à gauche non nulle de Vm" νϊΗβ est négative.
Sera nommé ordre numlex l'ordre numérique sur les exposants tel que vm = (mk, mk_ ..., m0) ayec m0≥mx...≥mk
Sera nommé ordre combinatoire l'ordre numérique sur les exposants tel que vm = (mk, mk^,..., m0) m0 > ml ... > mi
Sera nommé ordre lexicographique l'ordre lexicographique sur les indices des variables tel que Vfla k ν β si et si seulement la valeur la plus à gauche non nulle de vn" νΗβ est négative.
Si le polynôme de De Gua de Malves de la figure 2 correspondant à une courbe euclidienne du troisième degré est ordonné dans l'ordre lexicographique de ses coefficients, il est obtenu : a, b.y, ex, e.y2 , f.x.y, g.x2 , h.y3, i.x.y2 , k.x2.y, 2.x3. Après avoir substitué x par x0/x2 et y par xl/x2 , ramené l'ensemble des termes au même dénominateur et finalement conservé les numérateurs, la représentation homogène du polynôme est obtenue :
Figure imgf000019_0001
I.XQ .
En notant vma = (3,0,0) , vmb = (2,1,0) ... vm, = (0,0,3) , il est possible d'obtenir en ordre numérique inverse et en ordre numérique les séquences de monômes suivants : (a,b,c,e,f, g,h,i,k,l)
(l, k,i,h,g,f,e,c,b,e) .
En notant ν«α = <2,2,2> , vnb = (1,2,2) ... vn/ = <0,0,0> , il est obtenu en ordre lexicographique : (l, k, g,i, f,c, h,e,b,a) . Principes de codage combinatoire
En utilisant les propriétés combinatoires et projectives des treillis, il est possible de définir un système général d'indexation des monômes des polynômes et simultanément l'utiliser comme système de codage de listes d'entiers naturels : les coordonnées. Il sera apprécié par la personne versée dans le domaine que par transposition des entiers en codes alphanumériques quelconques, le système de codage pourra être étendu à l'encodage de texte et de chaînes de caractères alphanumériques.
Le système divulgué se base donc sur les principes suivants :
1. A chaque point d'un treillis (m, n) , aussi appelé sommet d'une pyramide hyperspatiale, est associé un vecteur de coordonnées homogènes de type [a0 : al : ... : an] . La somme des coordonnées est égale à m . La position d'une case dans le triangle de Pascal et par conséquent de la pyramide hyperspatiale et de l'hypersurface associée est donnée par la ligne et la colonne du triangle de Pascal. Les lignes et les colonnes associées à une case du triangle de Pascal correspondent aux degrés et aux dimensions algébriques des polynômes associés. Chaque sommet d'une même pyramide : sa pyramide de support, possède une signature formée d'un nombre égal de coordonnées dont la somme représente le degré et la longueur la dimension moins un. Cette signature peut être interprétée en théorie combinatoire soit comme les coordonnées projectives du point sommet appartenant à la pyramide, soit comme les puissances des monômes du polynôme représentant l'hypersurface associée, soit encore comme les indices des variables composant les monômes de ce même polynôme. 2. Le vecteur de coordonnées homogènes de type [at) : ax : ... : an\ est considéré comme le vecteur des exposants d'un monôme de degré total m , appartenant à un polynôme de degré m en n dimensions.
3. A chaque treillis est associé un ordre de parcours, aussi appelé indication de l'indexation, des points sur des chemins hamiltoniens particuliers passant par tous les points du treillis selon une réalisation de l'invention.
4. L'indice local de tout monôme est considéré comme l'indice du point homogène associé, c'est à dire le numéro du point dans l'ordre de parcours du chemin choisi.
5. Selon une réalisation de l'invention, tout vecteur de coordonnées est codé ou décodé en mode local grâce au triplet (indice local, degré total du vecteur, dimension
(" + !) )■
6. Selon une réalisation de l'invention, tout vecteur de coordonnées est codé ou décodé, en mode global, grâce à l'indice total obtenu en additionnant l'indice local et l'indice global. 7. Selon une réalisation de l'invention, la notion de vecteur de coordonnées est étendue à tout ensemble de nombres entiers naturels représentant des codes alphanumériques quelconques.
8. Le codage revient à trouver des systèmes bijectifs de numérotation ou d'indexation des messages en effectuant une double numérotation d'abord dans le triangle de Pascal, de la pyramide hyperspatiale associée au message donné : la pyramide de support, puis ensuite du point-sommet de la pyramide dont la signature représente le message. Le nombre entier ou le n-uplet, généralement le triplet de nombres entiers, résultant de cette double numérotation représente le message codé sous forme indexée. Le codage peut être basé sur différentes méthodes de numérotation et de parcours des points-sommets sur une même pyramide de support et le code résultant diffère alors d'une méthode à l'autre. 9. L e décodage revient à retrouver à partir du code la pyramide de support du message puis la signature du point-sommet appartenant à la pyramide. Cette double localisation ne peut s'effectuer qu'en connaissant à priori la méthode de parcours choisie pour la numérotation des points-sommets sur la pyramide de support. Ainsi et tel qu'expliqué ci-après il est possible de définir une méthode pour coder de l'information, la méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets tel que le degré de la pyramide hyperspatiale est égal à la somme des entiers de la liste d'entiers et la dimension de la pyramide hyperspatiale est égale au nombre d'entier de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation dans la pyramide hyperspatiale.
Dans une réalisation, la liste d'entiers est obtenue d'un fichier. La personne versée dans le domaine appréciera que divers types de fichiers peuvent être utilisés pour stocker la liste d'entiers.
Il sera aussi apprécié que l'étape de fournir l'indexation de la liste d'entiers dans la pyramide hyperspatiale pourra comprendre dans une réalisation le stockage de indexation dans un fichier. La personne versée dans le domaine appréciera que divers types de fichiers pourront être utilisés pour ce stockage. Alternativement, il sera apprécié par la personne versée dans le domaine que l'étape de fournir l'indexation de la liste d'entiers dans la pyramide hyperspatiale pourra comprendre dans une réalisation la transmission de la liste d'entiers à une unité de traitement par l'intermédiaire d'un réseau. La personne versée dans le domaine appréciera que divers types de réseaux pourront être utilisés. En fait, le réseau pourra comprendre au moins un d'un réseau local, d'un réseau de type MAN et d'un réseau de type WAN. Dans une réalisation, la transmission aura lieu à travers le réseau Internet.
Il sera aussi apprécié que dans une réalisation, une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprendra l'affichage de ladite indication de l'indexation de la liste d'entiers sur un écran. Il sera apprécié par la personne versée dans le domaine qu'une méthode est décrite pour décoder de l'information codée au moyen de la méthode pour coder de l'information décrite ci-avant. Dans ce cas, la méthode comprendra les étapes d'obtenir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale. La méthode comprendra de plus l'étape d'obtenir une indication d'un système d'indexation utilisé pour générer ladite indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale. La méthode comprendra de plus l'étape de déterminer au moyen de l'indexation et de l'indication d'un système d'indexation utilisé ladite liste d'entiers, et enfin, l'étape de fournir ladite liste d'entiers. Le diagramme de la figure 4 illustre une réalisation permettant de fournir plusieurs options de codage et décodage pour une liste d'entiers < > .
En particulier la fonction CODE est une famille de fonctions de codage qui indexent la liste d'entiers < > par rapport au treillis Tm n où m est le degré total de la liste et n - 1 sa longueur. Le résultat est un triplet < X,m, n > , X , représentant le nombre entier correspondant à l'indice du point projectif ayant la liste initiale d'entiers en entrée comme vecteur de coordonnées homogènes.
La personne versée dans le domaine appréciera que l'indice calculé est différent selon la méthode de codage adoptée. Selon les cas de figure, ce triplet pourra être fourni à la fonction DECODE qui restituera la liste initiale ou alors séparée en deux parties afin de constituer un seul entier Z qui pourra être décodé de manière bijective sans aucune autre information.
La partie de gauche du diagramme de la figure 4 fait apparaître un autre moyen de constituer un seul entier W , permettant un décodage bijectif. Il s'agit d'une famille de fonctions notées K2 , qui couplent le triplet deux à deux, m et n produisant un nombre entier, lui-même couple à X . Des fonctions de décodage en deux dimensions appliquées successivement permettent alors de restituer le code initial.
La partie droite du diagramme de la figure 4 correspond quant à elle à un schéma d'encodage-décodage bijectif couplé à un mécanisme de compression combinatoire. Dans ce cas, le triplet < X,m, n > est d'abord transformé en quadruplet, l'entier X étant remplacé par des coordonnées combinatoires particulières mx et nx . Le quadruplet (mx, nx, m, ri) est ensuite codé par un schéma de codage en quatre dimensions pour produire un code C . Ce type de code bijectif, peut être décodé par un schéma de décodage inverse en quatre dimensions. Le principe de compression réside dans la diminution importante du degré du quadruplet par rapport au degré du triplet qui compense très largement l'augmentation d'un caractère supplémentaire entre le triplet et le quadruplet.
L'indexation d'un treillis permet de coder avec un seul entier le degré et la dimension du treillis. L'indexation d'un treillis Tm„ peut être réalisée en dénombrant le nombre de cases du triangle de Pascal précédant la case de coordonnées x = m et y = m + n correspondant au coefficient binomial On effectue donc la somme du nombre de cases
Figure imgf000024_0001
triangle précédant la m, ligne du treillis à laquelle on ajoute le degré du treillis correspondant à sa colonne. La formule trouvée correspond à l'indexation de Cantor des entiers naturels dans le plan cartésien.
(m + n) * (m + n + \)
I = - — - + m
2
Indexation globale et totale
L'indexation globale permet d'assurer la bijection entre les points d'un treillis et leur indexation dans un espace à n-dimensions. Au lieu de calculer le nombre de cases précédant le coefficient binomial du treillis, le nombre total de points de tous les treillis précédents est calculé. À partir de l'équation T| 2r , et en notant que
2 + · · · + 2r = 2r+1 , la formulation de l'indice global Ig est obtenue en sommant le nombre des points des treillis des lignes allant de 0 à m + n - 1 1 et des points des treillis de la ligne m + n allant de 0 à m : m-1
Ig = 2m+n +∑Cm(i, m + n - \) .
=0
Le nombre total plus un, de points précédant le treillis Τ 5 sera obtenu de la manière suivante :
7^(5,2)→(128 -l) + (l + 7 + 21 + 35 + 35) + (l) = 227 .
L'indice global ajouté à l'indice local, le numéro du point sur le treillis, donne l'indice total du point qui permet de retrouver le vecteur initial codé sans mémoriser le degré et la dimension du treillis. Il est à noter que le caractère bijectif du codage et du décodage a un prix à payer en termes de taille des indices générés et de temps de calcul. Sur ce dernier point, des versions optimisées des algorithmes GLOBAL et LOCAL qui suivent seront présentées plus loin de même que plusieurs méthodes de calcul de l'indice local.
Il sera appréciée par la personne versée dans le domaine que dans l'algorithme GLOBAL illustré à la figure 5, la variable ind est équivalente au nombre total de points des treillis précédant la ligne du treillis Tm+n m et la variable acc équivalente à la sommation des coefficients binomiaux sur la ligne du treillis. La fonction de décodage LOCAL illustrée à la figure 5 effectue la recherche inverse en localisant sur le triangle de Pascal, la ligne précédant le treillis puis en isolant le treillis sur sa ligne.
Les différentes formulations récursives des coefficients binomiaux permettent de considérer les arbres récursifs d'appel des fonctions comme des systèmes d'ordonnancement des points d'un treillis. Dans tous les cas, les conditions d'arrêt de la
Figure imgf000025_0001
recursivité seront soit l, k = r , soit = 1, k = 0 , et dans ce cas, le nombre de feuilles terminales toutes égales à un sera nécessairement égal au coefficient binomial recherché. La figure 6 illustre les appels récursifs des fonctions correspondant aux équations avec r≥\
Figure imgf000025_0003
pour le calcul du coefficient binomial Les coefficients binomiaux correspondant à
Figure imgf000025_0002
chaque nœud de l'arbre fournissent le nombre de feuilles terminales de leurs sous-arbres respectifs. Les différents algorithmes de lecture et parcours des arbres fournissent donc des algorithmes d'indexation des feuilles terminales. En établissant une correspondance entre la production des feuilles terminales et des points du treillis, il est possible d'obtenir un ordonnancement de ces derniers. En particulier, les parcours d'arbres en profondeur consistent à traiter la racine de l'arbre et à parcourir récursivement les sous-arbres gauche et droit de la racine. Dans le parcours en profondeur préfixe ou lexicographique, la racine est traitée avant les appels récursifs sur les sous-arbres gauche, puis droit.
Codage projectif positionnel La représentation des nombres sous forme positionnelle est utilisée pour coder la séquence des coordonnées d'un point homogène. Soit N ce nombre, a, le symbole et b la base de numération, par définition : n
N = ¾ >'avec0 a, < b -l .
La base de numération m + 1 est utilisée où m est le degré du treillis de dimension n , et a, est la coordonnée homogène de rang .
L'indice positionnel Ip du point de coordonnées [x0 : ... : xn] du treillis Tm n est :
Figure imgf000026_0001
La figure 7 reprend l'exemple de l'indexation de la courbe cubique en 2 dimensions de la figure 2. Les indices sont calculés en base quaternaire. Par exemple, le point [2 : 0 : 1] a
2.(4)2 + 0.Ç4)1 + 1.(4)'
pour indice 1 1 . L'indice maximum du treillis étant égal à 16 pour
3
un nombre total de 10 points, la figure fait apparaître une indexation creuse c'est à dire présentant des trous dans la numérotation. La personne versée dans le domaine appréciera que le phénomène d'indexation creuse est l'un des désavantages du codage positionnel. En effet, pour un treillis Tm n t la croissance du rapport pm n entre l'indice maximum (m + l)" du codage positionnel et l'indice maximum correspondant d'un codage combinatoire est :
Figure imgf000027_0001
La figure 8 illustre les courbes représentatives de p en fonction de la croissance de m et n . Celles-ci permettent de visualiser l'expansion du nombre de digits nécessaires pour le
28531167061 1 codage positionnel. On obtient par exemple une valeur de plQ 10 égale à
184756
La structure algébrique en anneau des polynômes permet immédiatement de montrer l'homomorphisme additif du codage positionnel avec Ip(A + B) = Ip(A) + Ip (B) . Soient en effet les points A de coordonnées [aQ : ... : n] et B de coordonnées [bQ : ... : bn] , grâce aux propriétés d'associativité et de distributivité, il est alors possible de vérifier la relation :
/ (A + B) = ∑a,(m + iy + = ±-∑(a + b)t (m + iy . Ces propriétés d'homomorphisme additif s'étendent de la même manière à des combinaisons linéaires de type A + λ^Β . Le codage du point 1 1 de la figure 7 à partir de la combinaison linéaire des points 1 et 16, avec des poids respectifs de 1 et 2 donnera ainsi :
1.1 + 2.16 „
..10 : 0 : 3] + 2.[3 : 0 : 0]
1 + 2 J Codage en ordre numérique
La définition de l'ordre numérique suggère un algorithme simple de calcul de l'indice d'un point projectif, basé sur le décompte colonne après colonne de la position des coordonnées de ce point. La différence la plus à gauche et non nulle des vecteurs d'exposants de deux points projectifs, vma -ν?ηβ étant négative, il suffit de compter de gauche à droite, colonne après colonne, l'indice de chaque coordonnée et d'en faire la sommation pour trouver l'indice final du point. Pour calculer par exemple l'indice du point [1 : 2 : 1 : 0] du treillis 4 3 de la figure 11, 15 zéros avant le 1 de la première colonne seront comptés, 4 zéros et 3 uns avant le 2 de la seconde colonne et 1 zéro avant le 1 de la troisième colonne. L'indice 23 ou 11 = (34 - 23) sera obtenu selon la convention d'indexation choisie, ascendante ou descendante.
Il sera apprécié que les treillis Tm n sont décomposés récursivement en sous-treillis Tm n , Tm_X n_x , · * * , ^o,«-i ' ce revient à décomposer le polynôme représentatif d'une hypersurface en polynômes d'hypersurfaces de degrés décroissants dans la dimension inférieure.
De plus, les vecteurs d'exposants sont regroupés en m + 1 tableaux correspondant aux monômes des polynômes des hypersurfaces de degré décroissant. La figure 11 présente la décomposition par tableaux, d'un treillis (4,3). Les trois dernières colonnes d'exposants représentent les vecteurs d'exposants de treillis (4,2), (3,2), (2,2), (1,2) et (0,2).
Enfin, les tableaux générés sont à leur tour décomposés en tableaux de degrés inférieurs en dimension n - 2 et ainsi de suite. Les deux dernières colonnes des vecteurs d'exposants de la figure représentent donc les monômes de polynômes homogènes en dimension 1. n i
h =∑Cm(m - 1 -∑vn[ j], n + \ - i) .
L'algorithme NUMORD , illustré à la figure 10, correspond à l'équation précédente contractée. La seconde boucle permettant l'accumulation itérative du degré du vecteur d'exposants est en effet absorbée à l'intérieur de la première boucle par l'instruction 4. Afin d'alléger la présentation du code, la dimension projective égale à la longueur du vecteur moins un est fournie en argument. La figure 1 1 permet au travers d'un exemple de visualiser le déroulement pas à pas de la fonction NUMORD .
NUMORD{[\ ,\ ,\ M5)→{2\Q}num
L'indice {210}^um est le résultat de la sommation des nombres pyramidaux effectuée au niveau des lignes 1 à 6 de l'algorithme de la figure 10.
< )
Figure imgf000029_0001
Cette séquence fait apparaître la notion de composition pyramidale de l'indice numérique, illustrée à partir du tableau et du triangle de Pascal de la figure 11. Le décodage des indices calculés, présenté plus en avant, sera donc essentiellement basé sur le principe de décomposition pyramidale du nombre proposé, c'est à dire de la recherche de la séquence en cascade des nombres pyramidaux le composant.
Les exemples d'indexation qui suivent pour des points appartenant à des treillis T4 3 , T6 4 , 55 9 ι Γ549 illustrent en particulier le caractère non bijectif du codage numérique
NUMORD([\,2,l,0l3)→{ U }„um
NUMORD([4,0,\,0,l]A)→{ U }num
N(7 O/?Z)([1,2,3,4,5,6,7,8,9,10],9)→ {22724037001 }num / ΟΛΖ)([0,2,3,4,5,6,7,8,9,10],9)→ {22724037001 } i x[i] ind m
1 1 84 6 5
2 0 14 5 4
3 2 4 5 3
4 1 1 3 2
5 1 0 2 1
Décodage en ordre numérique
L'algorithme de décodage est basé sur l'inversion du processus d'indexation figurant entre les lignes 1 à 6 de la fonction NUMORD . L'objectif pour calculer la signature numérique vm des exposants est de retrouver tout d'abord les nombres pyramidaux successifs qui ont permis de calculer l'indice numérique. Pour retrouver le plus grand nombre pyramidal entrant dans la composition de 7™m , il faut chercher le plus grand nombre pyramidal qui lui est inférieur ou égal dans la colonne m du triangle de Pascal. Une fois ce nombre trouvé et son rang dans la colonne, le premier exposant de la signature recherchée est obtenu et on procède ainsi de colonne en colonne en décrémentant à chaque fois l'indice de départ. Ces étapes sont illustrées par le tableau précédent, avec le calcul de la signature numérique de {210}5. Le dernier exposant de la signature est calculé simplement en soustrayant la somme des exposants trouvés du degré de l'indice.
Les exemples suivants illustrent l'énumération des points du treillis T4 3 de la figure 11 indexés de 0 à 34 = Cr(4,3) -1 puis l'énumération des points du treillis Γ3 2 de la figure 2 indexés de 0 à 9 = Cr (3,2) - 1.
ORDNUM([34 - £,4,3])→ [0,0,0,4], [0,0, 1 ,3],· · · [4,0,0,0], k = 0,· · · ,34
ORDNUM([9 - £,3,2])→ [0,0,3], [0, 1 ,2], · · · [3,0,0], k = 0, · · · ,9
Codage en ordre lexicographique Afin d'effectuer un codage en ordre lexicographique, le treillis Tm n est décomposé en sous-treillis Tm_ fl_ Tm_X n_2 i ..., Tm_l 0, ce qui revient à décomposer le polynôme représentatif d'une hypersurface en polynômes d'hypersurfaces d'un degré inférieur en dimensions inférieures.
Ensuite, les vecteurs vm d'indices sont regroupés en n tableaux correspondant aux monômes des polynômes des hypersurfaces de degré décroissant. La figure 13 présente la décomposition par tableaux, d'un treillis 43. Les 4 tableaux correspondent respectivement aux treillis 33> Ti2i 31 et 30, de cubiques dans les dimensions
A = 3, ···,().
Enfin, les tableaux générés sont à leur tour décomposés en tableaux d'un degré inférieur dans des dimension qui décroissent. m-l
/, = Cn(m - i,n -1 -vm[i + 1])
La figure 13 illustre la décomposition par blocs d'un treillis (4, 3). Les signatures de longueur 4 commençant soit par χο,χχ , x2,ou x3 forment quatre blocs de tailles respectives
= 1. La signature
Figure imgf000031_0001
vm = (1,1,2,3) a pour indice :
C(4,(3-l)-l) + C(3,(3-l)-l) + C(2,(3-l)-2) + C(l,(3-l)-3) = {10}to.
Le déroulement de la fonction Z£LYO?D([0,l,l,2],4,3) -> {23}lex est illustré sur le tableau suivant :
Figure imgf000032_0001
L'algorithme LEXORD est décrit à la figure 14. Décodage en ordre lexicographique
L'algorithme ORDLEX qui permet d'effectuer un décodage en ordre lexicographique est décrit à la figure 15.
Les exemples suivants illustrent rénumération des points du treillis T4 3 de la figure 13 indexes de 0 à 34 = 0(4,3) - l puis l'énumération des points du treillis T3 2 de la figure 2 indexes de 0 à 9 = 0(3,2) - 1.
ORDLEX ([34 - k, 4,3])→ [0,0,0,0],[0,0,0,1],· · · [3,3,3,3],* = 0,· · · ,34. ORDLEX ([9 - k, ,2])→ [0,0,0] , [0,0, 1 ] , · · · [2,2,2] , k = 0, · · · ,9. Codage de Gray projectif
La sommation des variations entre les codes consécutifs produits pour le codage numérique n'est pas constante. Par exemple, la sommation des variations entre les codes 34 et 33 du treillis Γ4 3 est égale à (0,0,0,4) - (0,0,1,3)→0 et égale à (0,0,4,0) - (0,1,0,3) - 1 entre les codes 30 et 29. Le codage de Gray projectif permet d'éliminer ces différences de variations et de manière générale les sauts entre des points non consécutifs d'un treillis. Ces points ont en fait une distance sur le treillis supérieure à un. Le principe du codage de Gray projectif présenté est essentiellement un remplacement dans l'arbre récursif, des sous-arbres d'indexation impaire, par leurs symétriques. Ce remplacement étant récursif, l'opération se répétera pour chaque feuille autant de fois qu'elle possédera des parents successifs ayant des indexations impaires. Par conséquent, les sous-arbres possédant un nombre pair de parents successifs impairs n'auront pas à être modifiés, des symétries en nombre pair s'annulant.
Il sera apprécié que dans un codage de Gray projectif, la sommation des exposants du vecteur VnM - Vni obtenue à partir de deux points consécutifs est nulle et la distance de Hamming entre deux vecteurs consécutifs d'exposants, est égale à 2.
La figure 16 illustre un codage de Gray projectif (4,3).
L'algorithme illustré à la figure 17 est une version modifiée de l'algorithme illustré à la figure 10. La ligne 4 teste la parité de chaque exposant de la signature fournie en entrée (fonction typeQ). Dans le cas d'un exposant impair l'indiçage est inversé à la ligne 7 et la variable s change de signe. Sa valeur égale à 1 ou -1 permet de prendre en compte le nombre pair ou impair des exposants déjà traités et identifier ainsi les sous-arbres possédant un nombre pair de parents successifs impairs et qui n'ont pas alors à être modifiés.
La figure 18 illustre le parcours des points du treillis T4 J en Gray projectif. Les différentes sections font apparaître une succession de parcours de type cantorien boustrophédonique.
L'indiçage en Gray projectif du point 10 pour le treillis Γ64 et pour le treillis T2 4 est obtenu de la manière suivante :
Gj^OJ?D([4,0,l,0,l],4)→{ 10Î ;
GRAORD([0,0,\,0,l],4)→ { 10} Décodage de Gray projectif
Une implémentation de l'algorithme de décodage de Gray projectif est illustrée à la figure 19 par la fonction ORDGRA .
L'exemple suivant illustre l'énumération des points du treillis Γ4 3 de la figure 16 indexés de O à 34 = Cr(4,3) - l :
ORDGRA([34 - £,4,3])→ [0,0,0,4], · · -[3,0,0, 1 ], [4,0,0,0], k = 0,· ·■ ,34 . Transcodage dual et direct
Il sera apprécié que le transcodage d'un système de codage à l'autre peut être réalisé en repassant d'un codage à l'autre par simple conversion entre le vecteur des exposants Vn et le vecteur des coordonnées Vm , soit par une équivalence directe entre les fonctions d'indexation. Dans le premier cas, on parlera de transcodage dual réalisé par les deux fonctions 20 VN2VM et VMIVN et nous aurons les équivalences suivantes formées à partir des signatures lexicographiques et numériques :
Snum [Cm(m, n) - i] = Vm Vn(Slex [i - 1 ]) ; Slex[Cm(m,n) - i] = VnVm{Smm[i -1]) .
Par exemple si :
Snum[Cm(7,4) - 68] = [1 ,1,4,1,0] et 5ta[168 -l] = [0,1,2,2,2,2,3] , il sera obtenu : [ 1 , 1 ,4, 1 ,0] <- VM2VN([0, 1 ,2,2,2,2,3]) Le transcodage entre vecteur est illustré à la figure 20. Production récursive d'un ordre
Compte tenu de la relation de symétrie du triangle de Pascal ( r et des équivalences entre les décompositions récursives par colonne et diagonale, un arbre récursif est associé à deux coefficients binomiaux symétriques. La figure 21 permet de visualiser la structure récursive de . Les nœuds a(i,j) sont
Figure imgf000035_0001
indicés en largeur Î et en profondeur j et les nombres de feuilles des sous-arbres correspondants sont directement calculés à partir de i et j . Toute fonction /( , j) permet alors d'étiqueter les nœuds de l'arbre et produit un certain type d'ordonnancement des feuilles terminales de l'arbre. Si l'on opte pour un même parcours lexicographique préfixe de l'arbre, on obtie ors l'indexation en ordre numérique d'une courbe quartique en deux dimensions tion en ordre lexicographique d'une hyperquadrique en ou finalement l'indexation en ordre
Figure imgf000035_0002
lexicographique des 4-combinaisons sans répétition pour 6 objets. La production récursive d'un ordre revient par conséquent à associer à un coefficient binomial un triplet composé d'un ordre de lecture de l'arbre récursif, d'une fonction d'indexation des nœuds de cet arbre et d'un choix du type de combinaisons avec ou sans répétitions.
Fonctions d'indexation des arbres récursifs Les fonctions d'indexation numérique, Numlex et combinatoire peuvent être déduites séquentiellement l'une de l'autre. L'interprétation géométrique qui en découle utilise les passages entre espaces projectif, affine puis euclidien.
Ordres numérique et numlex
L'algorithme d'indexation numérique consiste à incrémenter à partir de zéro, les indices des nœuds de même niveau tant qu'ils possèdent le même parent. Le parcours de l'arbre se fait donc de gauche à droite et de bas en haut. L'indice du dernier niveau est obtenu en déduisant la somme des indices des niveaux précédents du degré de l'arbre, ce qui garantit l'homogénéité des points numériques produits. Pour passer de l'espace de codage numérique à l'espace de codage numlex, des matrices de passage N2Xn qui associent aux sommets de simplexes d'espaces projectifs numériques les sommets de sous-espaces projectifs aux coordonnées croissantes au sens large. Par exemple, le sommet [1 : 0 : 0 : 0] du simplexe projectif en 3 dimensions sera associé au sommet [1,1,1,1] . Le produit matriciel d'un point projectif n-dimensionnel avec la matrice N2Xn_x générera dans tous les cas un point aux coordonnées croissantes. En notant X2Nn , la matrice de passage inverse permettant de passer de l'espace numlex à numérique, les matrices de passage suivantes vont être obtenues.
1 1 1 1 0
1 1 0 1
N2X 0 1 X2N = 0 0
0 0 0 1 0 0 0 1
A titre d'exemple, le point numérique projectif [ 0
Figure imgf000036_0001
sera donc transformé en point numlex [ccQ, 0 + λ,αϋ + λ + 2, 0 + or, + a2 + a3] par le produit matriciel avec la matrice N2X^ . Le point [5 : 2 : 0 : 4] sera quant à lui transformé en point numlex [5 : 7 : 7 : 1 1 et son indice lexicographique sera calculé à partir de ses coordonnés comme
- suit : = 1001 + 84 + 28 + 5 = 1 1 18
Figure imgf000036_0002
Ordres numérique et combinatoire
On passe de l'ordre numérique à combinatoire en effectuant une combinaison linéaire entre les points numlex et le point [0, 1, 2,■· ·, « - 2, M - 1] . Cette opération revient à additionner chaque coordonnée du point numlex avec son rang, équivalent à son niveau dans l'arbre récursif. La figure 24 illustre la présence du sous-espace combinatoire des 3 -combinaisons dans le simplexe de référence de l'espace projectif en 3 dimensions. Ce sous-espace est représenté par les sommets de son simplexe de référence obtenus par transformation linéaire projective des sommets du simplexe de référence de l'espace projectif initial (le simplexe unité). La transformation linéaire suivante est obtenue :
Figure imgf000037_0001
Les points projectifs appartenant à l'espace combinatoire et obtenus par combinaison quelconque de deux des sommets du simplexe ont donc des coordonnées strictement croissantes. Il est possible d'établir le théorème d'équivalence suivant : L'indexation d'une k-combinaison d'un r-alphabet {0,· · · ,Γ - 1 } est équivalente par transformation projective à l'indexation numérique du treillis Tr_k k .
La figure 25 illustre l'indexation numérique d'un treillis T2Ji équivalent à l'indexation des
3 -combinaisons à partir du 5-alphabet 0,· · · ,4. En dimension supérieure, par
Figure imgf000037_0002
exemple, le point numérique 2172, de coordonnés [2,4,1,2,0,3] appartenant au treillis Tl2 5 est transformé en point numlex [2,6,7,9,9,12] par multiplication matricielle avec la matrice N2X5 , puis est additionné avec le point [0,1,2,3,4] pour donner le point combinatoire [2,7,9,12,13,17] . On vérifie alors que la position de la combinaison [2,7,9,12,13] pour l'alphabet <0,1,· · · ,17 - 1> est bien :
2172
Figure imgf000037_0003
L'équivalence entre l'ordre numérique et combinatoire permet d'utiliser les algorithmes de codage numérique ORDNUM comme algorithmes rapides de générations de combinaisons. Ceux-ci font appel en particulier à des algorithmes énumératifs du type HAKMEMm (R. Schroeppel, M. Beeler, R.W. Gosper. Hakmem. Technical report, Massachusetts Institute of Technology, 1972), générant les combinaisons à partir de la combinaison précédente représentée sous forme binaire. Comme ce type d'algorithme, pour générer les combinaisons, énumère de manière croissante les nombres ayant le même nombre de bits 1 dans leur représentation binaire, il en résulte que l'algorithme ORDNUM optimisé peut être également utilisé pour cet usage. La figure 26 illustre la génération énumérative des points projectifs d'un treillis Γ2 3 correspondant à une quadrique en 3 dimensions. Les 10 points, par transformation projective dans le sous- espace combinatoire, forment les 3 -combinaisons prises parmi 5 à partir du 5 -alphabet 0,...,4. La relation avec la représentation binaire des combinaisons calculées par l'algorithme HAKMEM s'en suit avec une transposition des indices des combinaisons énumérées de manière décroissante dans le sens de la lecture.
Ordres numérique et cantorien
Il est possible à l'aide des résultats précédents, de transcoder le codage cantorien à partir du codage numérique en effectuant des changements d'espaces projectifs à euclidiens. En utilisant le formalisme matriciel, le passage d'un point numérique [ 0 : x : ... : an] de l'espace projectif à l'espace euclidien est en effet réalisé par le produit de ce point par la matrice de passage P2E où \ a \ est le degré du point. La matrice E2P permettra l'opération inverse pour passer de l'espace euclidien à l'espace projectif :
Figure imgf000038_0001
Le résultat est donc le point homogène suivant :
(a0 + ûf, + · · · + «„)
\ a \
Le point euclidien obtenu en éliminant la dernière coordonnée égale à 1 , [αϋ : ax :■■■ : n_x ] est alors le point cantorien en n - 1 dimensions. Une équivalence est donc établie entre le codage cantorien de la liste inverse K(xk,...,xx) et le codage numérique. Pour se faire, il sera noté que l'arbre récursif cantorien est obtenu en éliminant le dernier niveau de l'arbre récursif numérique, c'est à dire le niveau permettant l'homogénéisation du point numérique.
Figure imgf000039_0001
En reprenant l'exemp
Figure imgf000039_0002
Figure imgf000039_0004
10 + 4 -1
il est possible de bien vérifier que /, = 782 . Il est à noter que le premier terme de l'équation :
£(1,3,2,4)→
Figure imgf000039_0005
doit être soustrait pour obtenir une indexation des points du treillis comprise entre 0 et le nombre total de points.
L'équation permet d'autre part d'obtenir la seconde
Figure imgf000039_0003
équivalence, K(xn,...,x2) - Ιηνη(χ ...,χη) qui fait correspondre au codage de Cantor d'une liste, le codage numérique de la liste inverse précédée d'un entier quelconque. Cette équivalence est illustrée par l'exemple suivant qui permet de déterminer le codage de Cantor K3 à partir de la fonction NUMORD([xO, x\, x2,x ],3) utilisée en mode symbolique :
_ mQ , m,{m + 1) _ m2 (m2 + l)(m2 + 2)
avec m0 = x3, ml = m0 + x2, m2 = mx + x\ . Taxinomie et ordre hamiltonien
Les équivalences précédentes permettent d'établir une taxinomie des systèmes de codage correspondants à différents ordres d'indexation. La figure 28 présente les ordres numlex, et combinatoire comme des cas particuliers de l'ordre numérique, l'ordre cantorien, étant lui-même un cas particulier de l'ordre combinatoire. Il est possible d'étendre cette classification en introduisant un ordre hamiltonien qui englobera également l'ordre de Gray projectif, lui-même considéré comme une généralisation de l'ordre cantorien boustrophédonique. De nouveaux ordres basés sur des courbes spirales remplissant l'espace seront décrits ci-après. Recherche de chaînes hamiltoniennes sur les treillis
La personne versée dans le domaine appréciera que l'indiçage local pour un treillis est tributaire du type de parcours de l'ensemble de ses points. Parmi les méthodes disponibles, figurent en particulier celles attachées à la théorie des courbes remplissant l'espace (Space Filling Curves). Fonction cartésienne de couplage en spirale
La fonction de couplage spiralée présentée à la figure 29 permet d'indexer les entiers relatifs deux à deux. Le plan cartésien est parcouru en spirale selon la figure 29. Dans ce cas les polynômes d'indexation des paires de coordonnées du plan cartésien sont recherchés. II sera apprécié que la génération de la spirale s'effectue de manière itérative à l'aide d'une équerre rectangle isocèle, tournée de π/2, puis changée d'échelle puis translatée de une unité de manière à assurer la continuité de la courbe.
4x - x + y si x > 0 et \ y \ <= \ x
4y2 - y - x si y > 0 et \ x \ <= \ y
4x2 - x - y si x < 0 et \ y \ <= | x
4y2 - 3y + x si y < 0 et | x | <= | y Le point 44 a pour racine carrée entière 6, ce qui correspond à la sixième équerre de la spirale ayant le point 36 = 6.6 comme sommet. Le point 44, est situé entre le sommet 36 (carré pair) et le sommet suivant 49 (carré impair). Étant supérieur au point angulaire intermédiaire 42 = 7.6, il est donc situé sur la section horizontale basse de la spirale. Les variables / et j sont alors calculées à partir du point angulaire intermédiaire 42, /' étant donc calculé à partir de la formule de l'indice du coin inférieur gauche de la spirale IB = 2/(2/ + 1) = 42 , soit i = 3 et j à partir de la différence entre le nombre donné et l'indice inférieur gauche, soit j = 44 - 42 = 2 . Le calcul du couple [x, y] est complété en portant les valeurs de et j dans les formules précédentes c'est à dire j = x + i puis i = -y . Le résultat final est donc [x,y] = [j - ,-/] = [-1,-3] . L'exemple suivant illustre l'utilisation des deux fonctions de codage et décodage cartésien en spirale SPIORDc et ORDSPIc .
SPIORDc([-\ 509123456789,82739987654321])→
{27383622228148684752295686632}se O^DS /c(27383622228148684752295686632)→ [-1509123456789,82739987654321]
La figure 32 décrit une implémentation d'un algorithme de codage cartésien SPIORDc et de décodage cartésien en spirale ORDSPIc .
Fonction affine de couplage en spirale y(9y - 7)
+ x si y < 0 et x <= 2y
2
x(9x- 7)
si x > 0 et y <= 2x
Z(x, y) = + y
2
(9(x - y)2 - x - y)
autrement
La figure 33 décrit une implémentation d'un algorithme de codage affine en spirale SPIORDa et de décodage affine en spirale ORDSPIa . Fonction projective de couplage en spirale
Il est possible de construire un ordre spiralé en «-dimensions en définissant récursivement des chaînes de chaînes de spirales, les premières spirales étant unidimensionnelles, puis bidimensionnelles et ainsi de suite. La figure 34 présente un ordre spiralé pour un treillis (6,4) de sextique en 3 dimensions. Les jonctions entre les spirales bidimensionnelles empilées sont alternées, tantôt entre les débuts, tantôt entre les fins des spirales. Pour obtenir des chaînes spiralées en 4 dimensions, il faut chaîner des treillis spiralés en 3 dimensions les uns aux autres en commençant par un point, treillis (0,4) puis un treillis (1,4) , un treillis (2,4) , etc. Optimisations du calcul des coefficients binomiaux
La personne versée dans le domaine appréciera que le calcul rapide des coefficients binomiaux est essentiel dans toutes les fonctions de codage et décodage présentées ci-avant. Les fonctions itératives ou récursives basées sur les relations simples attachées au triangle de Pascal sont d'excellentes candidates pour le calcul rapide des coefficients binomiaux de petite taille. Elles ne sont plus suffisantes pour des calculs faisant intervenir des grands entiers et doivent être améliorées ou remplacées. Aussi des variantes et des améliorations algorithmiques indispensables à la réduction des temps de calcul seront présentées ci-après.
Formulation récursive
La formulation récursive avec r≥ 1 de type additif, est à la base
Figure imgf000042_0001
de la construction du triangle de Pascal. Dans ce cas, l'arbre récursif binaire associé possède de nombreuses branches redondantes et a d'autre part une profondeur maximale de r -1 . Ces propriétés confèrent l'algorithme de calcul une complexité temporelle dans l'ordre du coefficient binomial lui-même. En conséquence les temps de calcul
Figure imgf000042_0002
deviennent immédiatement prohibitifs et ne peuvent être contrôlés informatiquement qu'en utilisant des tables d'appel qui mémorisent les fonctions appelées, leurs arguments et leurs résultats. Ce mécanisme emprunté à des optimisations en théorie de la compilation figure en particulier dans le langage Maple et peut casser la complexité algorithmique en supprimant les appels redondants présents dans le calcul récursif des coefficients binomiaux ou également dans celui des nombres de Fibonacci. En passant à une formulation de type additif-multiplicatif généralisant la formule , une nouvelle formulation récursive de profondeur
Figure imgf000043_0005
Figure imgf000043_0001
maximale r - k minimisant les redondances va être présentée. Il sera montré que cette approche peut-être considérée comme une variante récursive optimisée de la convolution de Vandermonde. En appliquant la formule de
Figure imgf000043_0002
Figure imgf000043_0006
manière répétitive sur les coefficients binomiaux d'un triangle rectangle isocèle à d côtés, la relation suivante est obtenue :
Figure imgf000043_0003
Celle-ci est obtenue en remarquant, comme l'illustre la figure 34, que le coefficient binomial à la pointe inférieure du triangle peut être calculé à partir des coefficients binomiaux de n'importe laquelle des lignes au dessus. Il suffit pour cela d'affecter les coefficients binomiaux de cette ligne d'un facteur multiplicatif approprié, par exemple a0 = l .t/0 + 3.c/l + 3.i/2 + l .d3. Ces facteurs multiplicatifs dus aux redondances de la formule récursive binaire 8 appliquée ligne après ligne et coefficient binomial après coefficient binomial sont simplement les coefficients binomiaux du développement (x + y)d . La figure 34 présente l'arbre binaire d'application de la formule avec r≥l sur un triangle à 4 côtés. Les duplications
Figure imgf000043_0004
successives des coefficients binomiaux fournissent les suites de facteurs multiplicatifs suivants { 1 } , { 1,1 } , { 1 ,2,1 } , { 1,3,3,1 } et les égalités suivantes α0 = 1.α0 , α0 = 1.Ζ>0 + 1.Μ , a0 = l .c0 + 2.cl + l .c2 , a0 = l .ùf0 + 3.c/l + 3.^2 + 1.^3. En posant s = k dans la formule la forme récursive intermédiaire
Figure imgf000044_0001
suivante est obtenue :
Figure imgf000044_0002
Afin de garantir l'existence d'un triangle rectangle associé à chaque coefficient binomial du triangle de Pascal, le coefficient symétrique le plus à gauche sur une ligne doit être conservé en utilisant la propriété de symétrie des coefficients binomiaux
Figure imgf000044_0003
L'équation suivante est alors obtenue pour k≤r :
(A r - k
\ k) i=0 min(k - i, r - k ~ (k - )) min(i, k - i)
Cette dernière peut être finalement considérée comme une variante récursive optimisée de la convolution de Vandermonde qui s'exprime en effet par :
Figure imgf000044_0004
L'algorithme de la figure 37, utilise trois conditions d'arrêt selon les valeurs de k . Elles ont été desimbriquées pour une lecture plus facile du code. Du point de vue de la programmation purement théorique, l'algorithme fonctionne également sans avoir recours à la fonction min() , inutile dans la formulation classique de Vandermonde, mais utile dans la réduction des appels récursifs.
En effectuant les substitutions successives suivantes, k
y{9y - l)
+ x si y < 0 et x <= 2y
2
x(9x - 7)
+ y si x > 0 et y <= 2x l'équivalence entre les relations Z(x,y) = et
(9(x - yy - x ~y)
autrement et ions
Figure imgf000045_0001
possibles parmi les lignes du triangle de Pascal, la récursivité commençant à partir du couple de lignes {r - k, k} soit {6,3} . Pour pouvoir utiliser dans la convolution de Vandermonde, les lignes intermédiaires entre les lignes r - k et k , il faudrait choisir un r - 2k
couple {r - k - i,k + i} satisfaisant — -— > / > 0 et par conséquent introduire une division entière par 2 dans l'algorithme de récursivité. Dans cet exemple il y aura ainsi = 1 et la possibilité de commencer la récursivité dans l'algorithme modifié avec le couple de lignes {5,4} . Formulations itératives il y a trois formulations itératives permettant de calculer les coefficients binomiaux à partir d'additions, de soustractions, de multiplications et de divisions. Il sera apprécié par la personne versée dans le domaine que la formulation par colonne se retrouve dans toutes les implémentations algorithmiques de base :
Figure imgf000045_0002
La formulation par ligne est quant à elle principalement utilisée pour le calcul de l'expansion des binômes de Newton :
Figure imgf000045_0003
Enfin la formulation par diagonale est issue de la propriété de symétrie des coefficients binomiaux à répétitions :
Cd (m, n) = Cy (n, m) = + )// .
/=1 La figure 38 illustre une réalisation d'un algorithme de calcul des binômes par ligne XENUME et par colonne YENUME .
Le coefficient binomial sera obtenu en sixième itération, par C (6,3) dans la
Figure imgf000046_0001
colonne 3, à la fin de la séquence YENUME(3,9)→ <1,4,10,20,35,56,84> ou alors en quatrième itération, par C (6,3) dans la ligne 9, à la fin de la séquence XENUME(3,9) -> (1,9,36,84) . Le temps de calcul proportionnel aux itérations conduira à effectuer de manière générale le calcul rapide au moyen de la fonction Cx dans le cas où m > n et au moyen de C si m≤n . Ce calcul pourra être finalement effectué par la fonction Cd qui nécessite le même nombre d'itérations que Cx par construction du triangle de Pascal. La séquence pour obtenir le coefficient binomial 84 sera alors
Figure imgf000046_0002
(1,7,28,84) . La généralisation de cet exemple amène donc à utiliser la propriété de symétrie pour optimiser le nombre d'itérations du calcul d'un coefficient binomial et utiliser une seule et même fonction de calcul dans les deux cas de figure :
\ Cy(m, n) si m >
\ Cy (n, m) si m≤n ' Cette première optimisation sur le nombre d'itérations étant faite, il est possible de réduire à nouveau ce nombre de moitié en mettant l'équation C^(w, «) = ]~[ (m + ï) /i sous la forme d'un produit de différences de carrés. Soit le produit suivant ayant un nombre impair 2k + 1 de termes,
(m + \) (m + 2) (m + 2k) (m + 2k + \) ,
— 7. Γ7— :— a rès avoir eifectue le changement de variables m = M - k ~ l ,
(M - k) (M - k + l) M (M + k - l) (M + k)
1 2 * + l 2k 2k + En regroupant tous les termes à l'exception de M sous la forme de la différence de deux carrés :
( ) ( 2 - l2) ( 2 -22) (M2 - k2)
1 2.3 4.5 2k.(2k + l)
La même opération est obtenue pour un produit ayant un nombre pair de 2k termes et il est obtenu alors :
(M) (M - k) (M2 - l2) (M2 - 22) ( 2 - (Â: - 1)2)
1 1 2.3 4.5 " ' 2k.(2k + l)
En divisant à chaque itération par 2/(2/ + 1) , la fonction de l'algorithme optimisé du calcul d'un coefficient binomial est alors présentée par la figure 39.
Divisions différées
Selon les performances relatives de la multiplication et de la division, il est possible d'envisager des variantes des algorithmes précédents en différant et limitant les divisions exactes. l suffit pour cela de calculer indépendamment les dénominateurs qui sont des factorielles et de diviser par ce résultat à la toute fin des algorithmes ou de manière intermédiaire si l'on veut contrôler l'expansion des grands entiers en cours de calcul. Cette approche est également intéressante dans la conception d'algorithmes parallèles.
La figure 39 illustre une réalisation d'un algorithme de calcul par produit de différences de carrés.
Calcul par programmation dynamique
Le calcul des coefficients binomiaux peut être effectué sans multiplications et divisions
Figure imgf000047_0001
en u san e sc ma e r currence + et en faisant appel à de la
Figure imgf000047_0002
mémoire de stockage. Les opérations nécessaires sont l'addition et l'affectation et le nombre de passages requis pour calculer un coefficient binomial est mn + ^(m(m + 3)) + n + \ . Le principe est qu'un schéma de calcul des coefficients binomiaux soit établi et soit basé sur une représentation rectangulaire horizontale du triangle de Pascal. L'évaluation des coefficients binomiaux s'effectue alors colonne par colonne au lieu de ligne par ligne. L'algorithme consiste donc à parcourir les cases d'un seul rectangle comme illustré par la figure 40. Le coefficient binomial recherché est situé à la pointe du rectangle et calculé à partir des coefficients binomiaux des colonnes précédentes.
Une implémentation de l'algorithme de programmation dynamique est illustrée à la figure 34.
Méthode additive et multiplicative En utilisant l'opérateur de multiplication, il est possible à partir de la représentation rectangulaire du triangle de Pascal, de développer des méthodologies de calcul des coefficients binomiaux basées sur l'exponentiation rapide de matrices triangulaires particulières. Il est fait pour cela appel à la formule du binôme de Newton étendu aux matrices carrées commutables en l'occurrence (M + I)r où / est la matrice identité. L'application de la formule permet d'exprimer les puissances de matrices triangulaires formées exclusivement de 1 , à partir de matrices exprimées à partir des coefficients binomiaux et il est alors obtenu :
Figure imgf000048_0001
Compte tenu de la structure symétrique de la matrice M par rapport à sa diagonale, le produit matriciel de deux matrices pour des puissances quelconques se simplifie sous la forme de la fonction MATPRT (voir figure 42) qui n'utilise pour les calculs que deux vecteurs VnO et Vn\ correspondant aux premières colonnes des deux matrices, et stocke le résultat dans le vecteur Wn . Ainsi, par exemple, le produit matriciel de la 3 ième et de la 31 ième colonne du triangle de Pascal sera représenté sous forme rectangulaire. Le dernier nombre du vecteur résultant Wn sera donc évalué à partir du produit matriciel entre deux puissances de la matrice M . Dans ce cas, le nombre 8436 sera donc évalué à partir des puissances 4 et 32 de la matrice initiale ayant [1,1,1,1] pour vecteur représentatif.
MATPRT{[\,A, 10,20], [ 1 ,32,528,5984],3)→ [1 ,36,666,8436]
La méthode naïve consiste donc à calculer toutes les puissances successives de M jusqu'à la puissance recherchée selon la séquence suivante :
MATPRT( \,\,\M[\,\,\M?>)→WM 2 - [1 ,2,3,4] ; Μ47 ΛΓ([1,1,1,1],[1 ,2,3,4],3) - ¾ = [1,3,6,10] ; TPRT([l,l,l,\ \,r,- - - ,- - -],3)→W^ [l,\ + r,- - - ,- - -] .
Minimiser le nombre de produits matriciels pour obtenir le coefficient binomial cherché revient à trouver la meilleure décomposition de la puissance correspondante en une séquence de nombres entiers. La stratégie algorithmique est alors de calculer un coefficient binomial quelconque par un nombre minimum de multiplications matricielles entre les colonnes. Diverses méthodes pour choisir les colonnes peuvent être utilisées dont certaines empruntées aux techniques d'exponentiation rapide. Celles ci reposent en effet sur la relation suivante applicable aux nombres entiers mais également aux matrices carrées : a 0 * = a ° a k .
L'exposant e est décomposé en une séquence de nombres entiers par l'intermédiaire de différentes bases de numération ou d'autres techniques de décomposition comme celle de Zeckendorf à base de nombres de Fibonacci . Les figures 43a et 43b illustrent ce principe pour le calcul matriciel des coefficients binomiaux avec une décomposition binaire de l'exposant (figure 43a) ou une décomposition de Zeckendorf (figure 43b). Pour une décomposition binaire de la puissance, seules les colonnes 2 ,2 ,2 ,· - · ,2 vont être utilisées pour effectuer les produits matriciels. Le coefficient binomial 2555190
Figure imgf000050_0001
sera ainsi calculé selon les étapes suivantes :
- Le coefficient binomial est tout d'abord exprimé dans le triangle de Pascal représenté sous forme rectangulaire :
Figure imgf000050_0002
- L'indice de la colonne compté à partir de est ensuite représenté sous forme binaire ce qui permet de faire apparaître les puissances de utilisées dans la décomposition binaire :
86 + 1 = 87→ { 10101 1 1 }2→ {26,0,24,0,22,21 ,20} ;
Les produits matriciels successifs des puissances de matrices correspondantes sont effectués :
M87 = MM x M16 x 4 x M2 x 1 pour finalement fournir la matrice à la puissance recherchée faisant apparaître le coefficient binomial recherché comme dernier élément de la première colonne de la matrice :
1 0 0 0 0
87 1 0 0 0
^64+16+4+2+1 = 87 =
3828 87 1 0 0
1 13564 3828 87 1 0
2555190 1 13564 3828 87 1
L'exercice peut se répéter en utilisant cette fois une décomposition de Zeckendorf :
87→ {55,21, 8,3 }Zk avec le gain d'une multiplication matricielle par rapport à la décomposition binaire :
M87 = M55 x M2i x 8 x 3 .
Dans les deux cas de figure, l'efficacité et la minimisation des calculs requièrent un schéma itératif simple de calcul des puissances de matrice intermédiaires. De manière générale, chaque matrice utilisée dans le produit matriciel résultant sera obtenue à partir de la matrice ou des matrices calculées précédemment. Un schéma itératif de type
Mt , x M, permettra ainsi de calculer le produit matriciel à la volée pour une décomposition binaire alors qu'un schéma itératif de type , = M, x (_, sera utilisé pour une décomposition de Zeckendorf avec des puissances égales aux nombres successifs de Fibonacci.
Une implémentation de l'algorithme de produit matriciel simplifié est illustrée à la figure 42.
Calcul par factorisation
Il sera apprécié par la personne versée dans le domaine que les critères de divisibilité des coefficients binomiaux peuvent être exploités pour trouver des factorisations rapides permettant d'obtenir le coefficient binomial par multiplication des facteurs trouvés. Pour le calcul des larges coefficients binomiaux, l'algorithme le plus connu est celui de Goetgheluck (P. Goetgheluck. Computing binomial coefficients. The American Mathematical Monthly, 94(4) :360-365, 1987.), basé sur un théorème de Lucas concernant la factorisation des coefficients binomiaux en nombres premiers.
Position d'un nombre dans le triangle de Pascal
La recherche de la position d'un nombre donné, c'est à dire l'identification des deux coefficients binomiaux adjacents de ce nombre dans une ligne ou dans une colonne donnée, est à la base des techniques de décodage présentées. Ce problème est indéterminé lorsque la ligne ou la colonne d'appartenance n'est pas spécifiée car il peut y avoir plusieurs entrées identiques dans le triangle de Pascal. Dans le cas où la colonne n est connue, cela revient à rechercher pour une certaine valeur yo et y = 0 la racine positive de la fonction polynomiale et équation suivante :
(m + \)(m + 2)- - - (m + n)
y = y0 ; ·
ni
Sous cette forme le graphe de la fonction est translaté pour obtenir la racine cherchée sur l'axe des y. La figure 44 illustre la recherche de la position du nombre 20 dans la quatrième colonne du triangle de Pascal avec un graphe de la fonction cette fois sans translation. Le résultat graphique montre que l'abscisse de l'intersection de la droite d'ordonnée 20 avec la courbe est située entre les valeurs 2 et 3. Le nombre 20 est donc
(4 + 2) (4 + 3)
compris entre les coefficients binomiaux = 15 et = 35 .
V 4 J V 4 J Méthode naïve La méthode naïve est l'
Figure imgf000052_0001
avec un test d'arrêt lorsque la valeur du coefficient binomial calculé dépasse la valeur y0 fournie en entrée. Une colonne est donc parcourue de manière itérative depuis son origine jusqu'à la découverte d'un coefficient binomial supérieur au nombre donné. Si la complexité théorique est linéaire, l'estimation des coûts réels de calcul doit prendre en compte les opérations d'addition, de multiplication et de division exacte pour des grands nombres entiers.
Méthode compte-gouttes
Certains types d'équations diophantiennes possèdent la caractéristique commune de posséder une seule racine supérieure à un, et d'être dérivables de manière continue. Un algorithme de recherche de cette racine est proposé pour toute équation diophantienne de forme y = P(x) où P(x) est un polynôme à coefficients entiers positifs ou nuls et qui possède une seule racine positive. Parmi les équations particulières répondant à ces critères, figurent, notamment les équations suivantes : Pm(x) = x(x + k. \)- - -(x + k(m -\), Sm (x) = \m + 2m + - - - + (x - \
Pm ( ) lorsque k = 1 se retrouve dans de nombreux problèmes liés à l'existence de puissances exactes égales à une suite d'entiers consécutifs et au coeur du théorème de Erdôs et Selfridge (P. Kirschenhofer, À. Pintér, R. F. Tichy Yu, F. Bilu, B. Brindza and A. Schinzel. Diophantine équations and bernoulli polynomials. Compositio Mathematica, 131(2) : 173-188, 2002.). Lorsque k = Q , Pm(x) se ramène à l'équation exponentielle classique et à la recherche des racines mêmes entières, Sm (x) est relative aux nombres de Bernouilli.
Principes Le principe consiste à améliorer la méthode naïve décrite précédemment en recherchant tout d'abord de manière rapide le nombre de digits de la racine positive de l'équation diophantienne, puis en calculant l'un après l'autre les digits manquants. La recherche du nombre de digits se fait en calculant le signe de la fonction pour des puissances successives de 10 de la variable x. L'ordre de convergence s'adapte donc automatiquement au degré de la fonction. Les digits manquant nécessitent au plus 10 fois le nombre de digits de la racine, évaluations de la fonction.
La figure 45 illustre une implémentation d'un algorithme de la méthode compte-goutte ENCDEC .
En notant que l'indice renvoyé par ENCDEC{\,x) est 0, il est obtenu par exemple ENCDEC(496,5)→ 6 , et de manière générale il est vérifié que la position du coefficient binomial central respecte bien l'identité :
ENCDEC(Comb(x, x),x)→ x .
En remplaçant d'autre part la fonction Comb par la fonction NUMFCT(x, n,0) (algorithme présente à la figure 46) dans les fonctions ENCDEC et DIGBIN , et en considérant NUMFCT(x,n,0) , il est possible de réaliser l'extraction de la racine même entière de x, utilisant la généralisation de la fonction ENCDEC à la recherche des solutions de certaines familles d'équations diophantiennes.
Méthodes analytiques
Les méthodes analytiques pour « = 1,2,3,4 peuvent être intéressantes, selon la performance de l'extraction de racines carrées et cubiques entières. C'est le cas par exemple en deux dimensions pour la fonction inverse de la fonction de couplage de
Cantor + y qui permet de déterminer les coordonnées d'un point
Figure imgf000054_0001
(m + l) * (m + 2)
identifié par son indice. Soit l'équation y0 - - ~ - = 0 , nous recherchons tout d'abord la valeur réelle positive de m0 = ^ + ^ + qui indique entre quelles diagonales du schéma de Cantor le point recherché se trouve. La partie entière de m0 qui est égale à l'indice de la diagonale précédant le point recherché, permet alors d'établir les
(χ + y) * (χ + y + 1 )
correspondances suivantes avec l'équation IK^ = ■— + y et de déterminer les coordonnées du point donné : y = ya (Lm0 SJ + l) J_*±(_LmJ0>_] + 2) >_ .
Figure imgf000054_0002
Le point d'indice 1 1 donnera ainsi une valeur de Lw0J = 3 pour les coordonnées [3,1] . Les formules analytiques pour les valeurs « = 3,4 seront illustrées ci-après dans les méthodes de décomposition binomiale d'un nombre.
Méthode numérique
La convergence du calcul de la position d'un point peut être accélérée de manière significative en recherchant les racines de la fonction binomiale avec un schéma itératif utilisant les dérivées successives de la fonction. Un algorithme de type Raphson-Newton dont les principes pourraient être étendus à des algorithmes de type Householder possédant des ordres de convergence supérieurs est présenté ci-après. Quel que soit l'algorithme choisi, celui-ci doit être conçu pour le calcul en nombres entiers et s'adapter à une fonction de degré quelconque. Pour cela un algorithme récursif de calcul de la dérivée A;-ième de la fonction est déterminé qui calcule la valeur de la dérivée sans avoir à recourir à une fonction de dérivation symbolique précalculée.
La formulation récursive de la dérivée k-ième de la fonction binomiale est
Figure imgf000055_0001
0 si n < 0 ou k < 0
nlf( ([«k)) 1 si n = 1 et k - 1
./¾ (m + n) + kffcj autrement
La figure 47 illustre une implémentation d'un algorithme de calcul récursif de la dérivée k-ième DRVREC .
!/(m) = (m + l)(m + 2) - - -(m + 7)
DRVREC(7,3)→2\0m4 + 3360m3 + 19320m2 + 47040m + 40614
La figure 48 illustre une implémentation d'un algorithme de type Raphson-Newton de degré n. DRVSYM(4)→x - ((x + l)(* + 2)(x + 3)(* + 4) -24^0)
(((2x + 3)(x + 3) + (x + 1 )(x + 2))(x + 4) + (x + 1 )(x + 2)(x + 3))
Représentation pyramidale des nombres entiers
Munis de fonctions de calcul pour positionner un nombre entier quelconque dans une colonne donnée du triangle de Pascal, il est possible de réaliser la fonction générale de décodage d'un nombre entier en représentation pascalienne. Le décodage d'un nombre en représentation quaternaire, étant une opération fréquente et que nous verrons essentielle dans le processus de compression des listes générales d'entiers, un décodage de nature purement analytique sera décrit en premier lieu, utilisant les principes présentés précédemment. Dans ce cas, un décodage séquentiel est obtenu où les coefficients binomiaux successifs β3...0 sont calculés à partir des racines entières positives de
„, . (m + l)(m + 2)---(m + n) , , , . . . . ... lequation y = y0-- — - pour les degrés 4,···,1 de la variable m.
n\
Conformément en deux dimensions à l'indice de la diagonale précédant le point correspondant au nombre donné, ces valeurs entières représentent l'indice de l'hyperplan, plan, droite et point diagonal précédant le point recherché.
Figure imgf000056_0001
En reprenant l'exemple précédent où le code combinatoire était 1118, le décodage s'effectuera selon la séquence suivante :
= 1001
Α0>) = β(ΐιΐ8-ιοοΐ) = = 84
Figure imgf000056_0002
¾Ο = Α(1118-1001 = 28 /?oO) = A,(1 118 -1001 - 84 - 28)
Figure imgf000057_0001
Le vecteur [(4 + 1),(6 + 1),(6 + 1),(10 + 1)] étant alors multiplié par la matrice X2N} pour restituer le code original [5 : 2 : 0 : 4] .
Si à présent la méthode compte-gouttes est utilisée, la fonction BINRP , illustrée à la figure 49, sera définie qui recherche la position d'un nombre entier quelconque dans la colonne 4, puis décrémente ce nombre de l'indice trouvé afin de rechercher la position de ce nouveau nombre dans la colonne 3, ce processus étant poursuivi jusqu'à la toute première colonne. Les indices trouvés sont équivalents aux coordonnées affines cantoriennes en 4 dimensions. Pour l'exemple précédent, BINRPA \ 1 18)→ {5,7,7,1 1 } correspondant au vecteur précédemment obtenu par la méthode analytique. De la même manière la représentation binomiale quaternaire du nombre 100 sera { 100}^M = {0,4,4,5} et sa décomposition quaternaire sera soit { 100} „ = {0,10,20,70} .
Figure imgf000057_0002
La figure 49 illustre une implémentation d'un algorithme de décomposition combinatoire quaternaire BINRPA d'un nombre. II sera alors possible d'étendre la fonction BINRPA à la décomposition n-aire d'un nombre pour obtenir la fonction générale BINRPN et sa fonction inverse RPNBIN qui recompose un nombre, donné sous forme pascalienne, en nombre décimal.
La figure 50 illustre une implémentation d'un algorithme (BINRPNi) de représentation pyramidale n-aire. Par exemple BINRPNi(l25,5)→ {4,4,4,4,4} soit { 125}^ = {4,4,4,4,4} , et inversement RPNBINi([A,A,A,4,A],S)→ 125 .
D'autre part, compte-tenu des équivalences démontrées précédemment, il est possible de remplacer la fonctionnalité de décodage lexicographique ORDLEXQ par : ORDLEX([x, m, n])≡[n,- - - ,n] - BINRPNi(x, m) .
Enfin, il est possible d'obtenir les fonctions de codage et décodage du système de numération combinatoire du paragraphe 4.4.1, en remplaçant a par a + ind dans les deux lignes de BINRPNi et Comb(vn[n - i + \] -\,i) par Comb(n -vn[m + \ -i] - i,i) dans RPNBINi .
Optimisations algorithmiques
La personne versée dans le domaine appréciera que l'élimination de certaines boucles soit le premier niveau d'optimisation algorithmique. Le principe de base est de remplacer une double boucle l'appel aux fonctions de calcul d'un coefficient binomial dans une boucle par une simple boucle calculant le coefficient de manière itérative.
Application aux listes générales d'entiers
Principe de compression combinatoire
Différents types de codage sont présentés qui, conformément au diagramme divulgué ci-avant, permettent d'encoder toute liste d'entiers par l'intermédiaire d'un nombre entier unique, l'indice total ou par un triplet constitué de l'indice local de la liste, de son degré total et de sa longueur. L'indice total correspond à la numérotation absolue d'un point projectif représentant la liste à coder dans l'espace projectif hyperspatial. La personne versée dans le domaine appréciera qu'il est algorithmiquement pur mais génère très rapidement de très grands entiers. Suite aux équivalences démontrées entre le codage numérique et le codage cantorien, il est également possible d'opter pour une autre stratégie et d'encoder le triplet {Χ, πι, η} en un seul nombre entier assurant le caractère bijectif du codage décodage. Il sera possible pour ce faire utiliser par exemple un codage cantorien tridimensionnel, ou un codage cantorien bidimensionnel en deux itérations successives. La connaissance implicite de la méthode de codage choisie permettra de réaliser le décodage. Une autre méthode consiste à remplacer le nombre X par ses coordonnées cantoriennes bidimensionnelles mx ,nx puis de coder le quadruplet {mx, nx,m, n} avec un codage cantorien en quatre dimensions. En remplaçant le triplet par un quadruplet il y aura un effet d'expansion limité de la taille du code généré : la longueur de la liste à coder étant simplement incrémentée de un, mais un effet de compression significatif dû à l'abaissement du degré total de la liste à coder. Soit en effet,
(γγΐ - - f\ Λ * ( YYl Yl -f- 1 \
un poids total du triplet de x x— - + mx + m + n , en exprimant X en fonction de ses coordonnées cantoriennes, le degré total du quadruplet sera abaissé à mx + ηχ + m + n .
La figure 51 illustre une implémentation d'un algorithme d'optimisation de codage global (GLOBALo) et local (LOCALo).
La figure 52 illustre une implémentation d'un algorithme de décodage numérique (ORDNUMo et ORINUMo).
La figure 53 illustre une implémentation d'un algorithme de codage et de décodage compressé (INDCOM).
En reprenant le point projectif [69,78,73,71,77,65] de degré 433 en dimension 5 de l'exemple 4.1, les indices suivants sont obtenus : /Wum = {55014101437}(433,5)
ITo, = { 1419606883389857208104148062281258856159455782592418086487285545
274686109596480318996466895925319463985864300012238628776356963859010}z et sous forme compressée,
ICom = /N CO ([69,78,73,71,77,65],5)→ {507098669008328947049}c . Représentation de listes de listes
L'application récursive de la fonction INDCOM permet de coder des listes de listes. Soit L0, L{ ,■■· ,∑„ un ensemble de listes d'entiers de dimensions respectives «„, «, ,· · · , «„, un codage de premier niveau sera défini ainsi : INDCOM([INDCOM(L0 ,n0), INDCOM{Lx , «,),·■· , INDCOM(Ln ,«„)], w) . Représentation des nombres entiers relatifs
Outre la représentation des entiers relatifs par les fonctions de couplage spiralées, il est possible de considérer la représentation théorique des entiers signés, par paire. Cette approche amène par exemple à doubler la longueur du vecteur initial en faisant précéder chaque entier par un entier signifiant son signe et par extension son type. Il est possible par exemple d'utiliser la convention du 0 pour un entier positif, du 1 pour un entier négatif, du 2 pour un irrationnel, du 3 pour un imaginaire, etc. La liste {-1,2,7,-3,5} sera ainsi codée sous forme entrelacée { 1 ,1 ,0,2,0,7,1 ,3,0,5} avec un indice compressé de {6592155939510}c .
La personne versée dans le domaine appréciera donc que des entiers relatifs pourront être codés au moyen d'une liste d'entiers. Dans un tel cas, une liste d'entiers à coder sera générée au moyen de la liste d'entiers relatifs.
Tris alphanumériques L'ordre numérique permet de créer des dictionnaires par tris alphanumériques. Pour cela, le principe consistera à ramener l'ensemble des mots du dictionnaire à des longueurs et des poids identiques. Les mots à trier seront associés à des points projectifs d'un même treillis. Il sera pris pour longueur, celle du mot le plus grand, et pour poids, celui du mot le plus lourd. Pour trier par exemple, les mots ART, ARA, BRAS, ARABE, ARABICA, codés avec un alphabet de 26 lettres, l'indice de chaque lettre correspondant à sa position dans l'alphabet, les points suivants qui leur correspondent sur le treillis T4o, 7 seront ordonnancés. La longueur maximale sera héritée du mot ARABICA et le poids maximum du mot BRAS :
ART→ [1,18,20,0,0,0,0,1]→ {45609855} , ;
num ARA→ [1,18,1 ,0,0,0,0,20]→ {45662979} , ;
num
BRAS -» [2,18,1,19,0,0,0,0] -> {38531317}, ARABE→ [1 ,18,1 ,2,5,0,0,13]→ {45658898},
ARABICA→ [1 ,18,1,2,9,3,1 ,5]→ {45658530}
En inversant le tri, pour respecter l'ordre descendant du codage numérique, la séquence triée alphabétiquement sera obtenue : (45662979,45658898,45658530,45609855,38531317)→
(ARA, ARABE, ARABICA, ART, BRAS) .
Hachage
Il sera apprécié par la personne versée dans le domaine que les fonctions d'indexation présentées précédemment peuvent avantageusement servir de fonctions de hachage de la même manière que la fonction classique de hachage polynomial bâtie à partir de l'équation :
H(x) = ( 0.Bk + x .Bk'x + - + ak .B° ) mod N .
Dans ce cas, B sera pris communément égal à une puissance de 2, par exemple 256 et N égal à un nombre premier. En couplant de la même manière les fonctions d'indexation combinatoire à l'opérateur modulo, les valeurs suivantes seront obtenues à partir de la séquence précédente. Le choix de N occasionnera un phénomène de collisions et un taux de remplissage de la table de hachage plus ou moins important.
(45662979,45658898,45658530,45609855,38531317)→ (11,12,8,5,6)
Application aux polynômes Représentation littérale
Considérer le polynôme sous forme d'une chaîne de caractères présente certains avantages, particulièrement pour préserver la représentation initiale du polynôme, sous forme factorisée par exemple ou alors en préservant son type de notation, en polonaise inversée par exemple. En contrepartie, les traitements algorithmiques ultérieurs du polynôme doivent passer par une étape de mini compilation classique de type expression arithmétique. Un codage élémentaire caractère par caractère pourra par conséquent être réalisé à partir d'un alphabet réduit de type {0,1 , 2,3,4,5,6,7,8,9, x,+,-,V,' (,),#} celui-ci étant constitué des digits, des opérateurs arithmétiques, des parenthèses, de la variable x et du caractère dièse utilisé comme séparateur. L'alphabet sera étendu aux lettres de l'alphabet si le polynôme est destiné à des traitements symboliques. Un code numérique étant affecté à chaque symbole de l'alphabet, la table d'équivalence de l'alphabet à n caractères sera simplement la liste des n + 1 entiers naturels. Le poids maximum de cette liste sera par conséquent (n + \)2 . L'exemple suivant présente l'équation homogène d'un tore de rayons a et b centré à l'origine du repère euclidien : Tore = (x0 2 + xf + x2 2 - (b2 - a2) * x2 f - 4 * a2 * (x2 + x,2) * x2.
La liste de 56 entiers et de degré total 3789, représentant l'équation du tore dans le système de codage UNICODE est la suivante :
^« = {40,120,48,94,50,43,120,49,94,50,43,120,50,94,50,45,40,98,94,50, 45,97,94,50,41 ,42, 120,51 ,94,50,41 ,94,50,45,52,42,97,94,50,42,40, 120,48,94,
50,43 , 120,49,94,50,41 ,42, 120,51 ,94,50}(£Αι(∞Λ) .
Le codage numérique de LTare , est effectué par NUMORD(LTore, 56 - 1) qui donne un indice numérique local de :
INum = {430498654249915943678023780125509627688494209313620775647407 4479473688920429540259225190355106304329193124705002316203895665}(3789 55) . Représentation structurée
Les problèmes de performances algorithmiques sont étroitement liés aux représentations choisies, et les problèmes de mémoire sont en partie occasionnés par les pertes dues aux polynômes creux. Le vecteur L représentant l'expansion numérique du polynôme du tore pour des rayons a = 2 et b =1 permet de visualiser les différents problèmes reliés à la représentation vectorielle : l'ordre des coefficients correspondant à l'ordre choisi sur les monômes, la présence des coefficients nuls propres aux polynômes creux et finalement la gestion des signes des coefficients qui échappent aux codages des entiers naturels. L = [1,0,2,0,1,0,0,0,0,2,0,2,0,0,1,0,0,0,0,0,0,0,0,0,0,-10,0,-10,0,0,6,0, 0,0,9]
Après avoir codé les valeurs négatives du vecteur L , le code numérique du nouveau vecteur entrelacé du tore est alors :
INum = { 191438651803617499325873813948513 }(46 69) . Afin de palier à ce type de problème et en considérant que les coefficients nuls n'influent que sur la dimension du vecteur à coder et non sur son degré, il est possible d'adopter la stratégie d'adressage en cascade suivante. Une table de hachage sans collisions d'une taille égale au nombre de coefficients Cm{m, ri) est créée pour un polynôme de degré m en n dimensions. Cette table contient les adresses codées à leur tour sous forme de nombres entiers sur les informations propres aux monômes. Ces informations stockées séparément peuvent être par conséquent les valeurs numériques signées des coefficients, mais également des pointeurs sur des fonctions de calcul symbolique des coefficients ou encore des indices de bases de données relationnelles pour établir des contraintes géométriques entre différents polynômes (CADCAM variationnel). T0 = [k0 ,0, k2 ,0, k, ,0,0,0,0, k9 ,0, *, , ,0,0, ku ,0,0,0,0,0,0,0,0,0,0, k25 ,0, k21 ,0, 0, k30 ,0,0,0, kM ] Codage des vecteurs et polynômes creux
Le codage des vecteurs creux peut être réalisé de plusieurs manières différentes. La méthode la plus commune est celle dite de représentation «rank-and-value» décrite par Lehmer (D.H. Lehmer. The machine tools of combinatorics. In E.F. Beckenbach, editor, Applied Combinatorial Mathemafics, pages 5-31. Wiley, New York, 1964). Dans ce cas, le codage est réalisé par une suite de paires d'entiers formées de la position de chaque entier dans la liste creuse, puis de sa valeur. Un zéro est mis en fin de liste pour signifier la fin du message. La table précédente To est donc codée de la manière suivante :
TQ0 — (0, kQ,2,k2,4, kli,9,k<),\ \,k ,l4,k^^,25,k25,27,k ,30, k-i0,34, ki ,0) . Les positions des valeurs non nulles peuvent être aussi codées séparément en utilisant par exemple la technique de compression combinatoire. Il y aura alors le code compressé suivant pour mémoriser les emplacements des valeurs non nulles de To :
(35,0,2,4,9,11,14,25,27,30,34)→ { 1836997097013699578176773581776}, II est possible également d'utiliser le codage de Pascal pour les séquences décroissantes mais en mémorisant de manière séparée la longueur du vecteur :
(34,30,27,25,14,1 1,9,4,2,0)→ { 148139661 }¾ï ■
Produit symbolique de polynômes à plusieurs variables
Les fonctions rapides d'indexation de monômes qui permettent de réaliser le produit de deux polynômes à plusieurs variables de manière vectorielle par indexation directe doivent être alors utilisées. L'algorithme MPLNUM illustré à la figure 54 utilise l'indexation par ordre numérique en multipliant chaque monôme du premier polynôme par chaque polynôme du second, ce qui est convenu d'appeler l'algorithme naïf de multiplication de deux polynômes. Un des intérêts de l'algorithme présenté est qu'il peut être facilement étendu aux multiplications de vecteurs creux.
L'algorithme de multiplication symbolique de deux polynômes multi variés est basé sur l'opération élémentaire du produit de deux monômes, de l'indexation du monôme résultant et de la sommation des monômes de même rang. La fonction MPLNUM réalise le produit symbolique de deux polynômes dans une dimension donnée. Le degré du polynôme résultant dgr calculé en ligne 1 et les nombres des monômes des deux polynômes multipliés et du polynôme résultant sont calculés de la ligne 2 à la ligne 9. L'initialisation de tous les termes du vecteur résultant à zéro est réalisée à la ligne 10. Une boucle est faite sur le nombre Iga des monômes du polynôme a en ligne 1 1 et sur le nombre Igb des monômes du polynôme b en ligne 12. Les signatures en ordre numérique des deux polynômes a et b sont obtenues aux lignes 13 et 14. La multiplication des monômes est réalisée par l'addition des signatures siga et sigb à la ligne 15. L'indice du monôme résultant est calculé à la ligne 16. Finalement, les monômes résultants de même rang sont sommés et accumulés dans le vecteur associé aux polynômes résultant à la ligne 17.
L'exemple suivant illustre la multiplication en deux dimensions d'une courbe du second degré projective (conique) par une courbe du premier degré (droite), ce qui donne une courbe du troisième degré (cubique dégénérée). Soit yla, la conique d'équation yla ~ 0χ0 2 + axx0xx + a2xx 2 + Û3X0X2 + α χ{χ2 + a5x^ et ybl , la droite d'équation ybl = b0x0 + bxxx + b2x2 , les 10 = coefficients de la cubique y3c en ordre numérique
(0,0,3), (0,1, 2),· · -,(3,0,0) sont obtenus,
MPLNUM([a0, al , al, a , a4, a5] , [bO, bl , bl] ,2, 1 ,2)→ [aO * bO, aO * b\ + al * b0, al * bl + al * bO, al * bl, aO * bl + a3 * bO, al * bl + a3 * bl +a4*b0, al*bl +a4*bl, a3*bl+ a5*b0, a4*bl +a5*bl, a5*bl].
Implémentation de la méthode divulguée
Il sera apprécié par la personne versée dans le domaine que la méthode pour coder de l'information divulguée ci-avant ainsi que la méthode pour décoder de l'information codée au moyen de la méthode divulguée ci-avant pourront être implémentées de diverses façons.
En particulier, ces méthodes pourront être implémentées par exemple dans un ordinateur 300 tel qu'illustré à la figure 30. L'ordinateur 300 comprendra par exemple un processeur 310, un bus de données 312, une unité de stockage des données 314, un port de communication 316, une unité d'affichage 318 et un clavier 320.
Dans cet exemple, le processeur 310 est adapté pour traiter des instructions. La personne versée dans le domaine appréciera que divers types de processeurs peuvent être utilisés pour effectuer le traitement des instructions.
L'unité de stockage des données 314 est adaptée pour stocker des données. La personne versée dans le domaine appréciera que divers types d'unités de stockage des données pourront être utilisés pour effectuer un tel stockage. Le port de communication 316 est utilisé pour échanger de l'information entre l'ordinateur 300 et une autre unité de traitement non illustrée sur la figure 30. La personne versée dans le domaine appréciera que le port de communication 316 dépend du type de connexion utilisé entre l'ordinateur 300 et l'autre unité de traitement. L'unité d'affichage 318 est utilisée pour afficher des données à un usager. La personne versée dans le domaine appréciera que divers types d'unité d'affichage pourront être utilisés.
Le clavier 320 est utilisé pour permettre à un usager de fournir des données à l'ordinateur 300. Là encore, la personne versée dans le domaine appréciera que divers types de claviers pourront être utilisés.
Il sera apprécié que le processeur 310, l'unité de stockage de données 314, le port de communication 316, l'unité d'affichage 318 et le clavier 320 sont opérativement connectés ensemble au moyen du bus de données 312.
En fait et dans une réalisation, l'unité de stockage des données 314 comprend un système d'exploitation 322. Le système d'exploitation 322 pourra être de différents types.
L'unité de stockage des données 314 comprend de plus un programme 324 pouvant être exécuté par le processeur 310 et dont l'exécution permet de coder de l'information. Il sera apprécié par la personne versée dans le domaine qu'un programme dont l'exécution permettra de décoder de l'information pourra aussi être stocké dans l'unité de stockage des données 314.
Le programme permettant de coder de l'information comprend des instructions pour obtenir une liste d'entiers à coder. Il sera apprécié que la liste d'entiers à coder pourra être obtenue de diverses manières. Dans une réalisation, la liste d'entiers sera entrée par un usager au moyen du clavier 320. Dans une autre réalisation la liste d'entiers sera obtenue d'un fichier localisé dans l'unité de stockage de données 314 ou reçu par l'intermédiaire du port de communication 316.
Le programme permettant de coder de l'information comprend de plus des instructions pour déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un. Le programme permettant de coder de l'information comprend des instructions pour indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation. Tel que mentionné ci-avant, divers systèmes d'indexation pourront être utilisés.
Le programme permettant de coder de l'information comprend des instructions pour fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder. Il sera apprécié que l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale pourra être fournie de diverses façons. Par exemple, l'indication de l'indexation de la liste d'entiers pourra être affichée sur l'unité d'affichage 318 (par exemple un écran). Alternativement, l'indication de l'indexation de la liste d'entiers pourra être stockée dans un fichier localisé dans l'unité de stockage de données 314 ou elle pourra être transmise par l'intermédiaire du port de communication 316 à une autre unité de traitement.
Il sera apprécié qu'un dispositif de stockage d'information pourra être fourni pour stocker des instructions exécutables par un processeur. Ces informations exécutables par un processeur vont causer le processeur d'exécuter une méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
Clause 1. Une méthode pour coder de l'information, la méthode comprenant :
obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un;
indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et
fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder. Clause 2. La méthode revendiquée à la clause 1, comprenant de plus fournir une liste de codes alphanumériques et transformer la liste de codes alphanumériques en liste d'entiers à coder.
Clause 3. La méthode revendiquée à la clause 1 , dans laquelle le système d'indexation permet d'indexer chacun de la pluralité de sommets de ladite pyramide hyperspatiale. Clause 4. La méthode revendiquée à la clause 1, dans laquelle l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend un entier représentant l'indice du point projectif dans le système d'indexation, m le degré total de ladite liste d'entiers et n le nombre d'entiers de la liste d'entiers.
Clause 5. La méthode revendiquée à la clause 4, comprenant de plus transformer l'entier représentant l'indice du point projectif par des coordonnées combinatoires mx et nx.
Clause 6. La méthode revendiquée à la clause 4, comprenant de plus la transformation de m le degré total de la liste d'entiers et n le nombre d'entiers de la liste d'entiers par un entier Y représentant un indice global.
Clause 7. La méthode revendiquée à la clause 6, comprenant de plus effectuer la sommation de l'entier Y représentant un indice global à l'entier représentant l'indice du point projectif pour fournir un indice total Z, l'indication de l'indexation dans la pyramide hyperspatiale comprenant l'indice total Z. Clause 8. La méthode revendiquée dans un des clauses 1 à 7, dans laquelle la liste d'entiers est obtenue d'un fichier.
Clause 9. La méthode revendiquée dans une des clauses 1 à 8, dans laquelle l'étape de fournir Γ indication de l'indexation dans la pyramide hyperspatiale comprend le stockage de ladite indication de l'indexation dans un fichier.
Clause 10. La méthode revendiquée dans une des clauses 1 à 8, dans laquelle l'étape de fournir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend la transmission de l'indexation de la liste d'entiers à une unité de traitement par l'intermédiaire d'un réseau. Clause 11. La méthode revendiquée dans une des clauses 1 à 10 pour coder une liste d'entiers relatifs, la méthode comprenant fournir la liste d'entiers relatifs et générer la liste d'entiers au moyen de la liste d'entiers relatifs.
Clause 12. La méthode revendiquée dans une des clauses 1 à 8, dans laquelle l'étape de fournir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend l'affichage de ladite indication de l'indexation de la liste d'entiers sur un écran.
Clause 13. L'utilisation de la méthode revendiquée dans une des clauses 1 à 3 et 4 à 7 pour compresser une chaîne de caractères dans laquelle la chaîne de caractères est associée à ladite liste d'entiers.
Clause 14. Une méthode pour coder une liste de listes, la méthode comprenant l'utilisation itérative de la méthode revendiquée dans une des clauses 1 à 3 et 4 à 7 pour coder une liste de listes.
Clause 15. L'utilisation de la méthode revendiquée à la clause 1 pour crypter une liste d'entiers, dans laquelle l'indexation de la liste d'entiers correspond au cryptage de la liste d'entiers. Clause 16. Une méthode pour décoder de l'information codée au moyen de la méthode pour coder de l'information revendiquée dans une des clauses 1 à 7, la méthode comprenant :
obtenir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale;
obtenir une indication d'un système d'indexation utilisé pour générer ladite indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale;
déterminer au moyen de l'indexation et de l'indication d'un système d'indexation utilisé ladite liste d'entiers.
fournir ladite liste d'entiers.
Clause 17. Un ordinateur comprenant :
une unité d'affichage;
un processeur;
une unité de stockage des données comprenant un programme configuré pour être exécuté par le processeur, le programme permettant de coder de l'information, le programme comprenant :
des instructions pour obtenir une liste d'entiers à coder;
des instructions pour déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un;
des instructions pour indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation;
des instructions pour fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
Clause 18. Un dispositif de stockage d'information pour stocker des instructions exécutables par un processeur, qui quand elles sont exécutées vont causer l'exécution par le processeur d'une méthode pour coder de l'information, la méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.

Claims

Revendications
1. Une méthode pour coder de l'information, la méthode comprenant :
obtenir une liste d'entiers à coder;
déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un;
indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et
fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
2. La méthode revendiquée à la revendication 1, comprenant de plus fournir une liste de codes alphanumériques et transformer la liste de codes alphanumériques en liste d'entiers à coder.
3. La méthode revendiquée à la revendication 1, dans laquelle le système d'indexation permet d'indexer chacun de la pluralité de sommets de ladite pyramide hyperspatiale.
4. La méthode revendiquée à la revendication 1, dans laquelle l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend un entier représentant l'indice du point projectif dans le système d'indexation, m le degré total de ladite liste d'entiers et n le nombre d'entiers de la liste d'entiers.
5. La méthode revendiquée à la revendication 4, comprenant de plus transformer l'entier représentant l'indice du point projectif par des coordonnées combinatoires mx et nx.
6. La méthode revendiquée à la revendication 4, comprenant de plus la transformation de m le degré total de la liste d'entiers et n le nombre d'entiers de la liste d'entiers par un entier Y représentant un indice global.
7. La méthode revendiquée à la revendication 6, comprenant de plus effectuer la sommation de l'entier Y représentant un indice global à l'entier représentant l'indice du point projectif pour fournir un indice total Z, l'indication de l'indexation dans la pyramide hyperspatiale comprenant l'indice total Z.
8. La méthode revendiquée dans une des revendications 1 à 7, dans laquelle la liste d'entiers est obtenue d'un fichier.
9. La méthode revendiquée dans une des revendications 1 à 8, dans laquelle l'étape de fournir l'indication de l'indexation dans la pyramide hyperspatiale comprend le stockage de ladite indication de l'indexation dans un fichier.
10. La méthode revendiquée dans une des revendications 1 à 8, dans laquelle l'étape de fournir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend la transmission de l'indexation de la liste d'entiers à une unité de traitement par l'intermédiaire d'un réseau.
11. La méthode revendiquée dans une des revendications 1 à 10 pour coder une liste d'entiers relatifs, la méthode comprenant fournir la liste d'entiers relatifs et générer la liste d'entiers au moyen de la liste d'entiers relatifs.
12. La méthode revendiquée dans une des revendications 1 à 8, dans laquelle l'étape de fournir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale comprend l'affichage de ladite indication de l'indexation de la liste d'entiers sur un écran.
13. L'utilisation de la méthode revendiquée dans une des revendications 1 à 3 et 4 à 7 pour compresser une chaîne de caractères dans laquelle la chaîne de caractères est associée à ladite liste d'entiers.
14. Une méthode pour coder une liste de listes, la méthode comprenant l'utilisation itérative de la méthode revendiquée dans une des revendications 1 à 3 et 4 à 7 pour coder une liste de listes.
15. L'utilisation de la méthode revendiquée à la revendication 1 pour crypter une liste d'entiers, dans laquelle l'indexation de la liste d'entiers correspond au cryptage de la liste d'entiers.
16. Une méthode pour décoder de l'information codée au moyen de la méthode pour coder de l'information revendiquée dans une des revendications 1 à 7, la méthode comprenant :
obtenir l'indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale;
obtenir une indication d'un système d'indexation utilisé pour générer ladite indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale;
déterminer au moyen de l'indexation et de l'indication d'un système d'indexation utilisé ladite liste d'entiers.
fournir ladite liste d'entiers.
17. Un ordinateur comprenant :
une unité d'affichage;
un processeur;
une unité de stockage des données comprenant un programme configuré pour être exécuté par le processeur, le programme permettant de coder de l'information, le programme comprenant :
des instructions pour obtenir une liste d'entiers à coder;
des instructions pour déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; des instructions pour indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation;
des instructions pour fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
18. Un dispositif de stockage d'information pour stocker des instructions exécutables par un processeur, qui quand elles sont exécutées vont causer l'exécution par le processeur d'une méthode pour coder de l'information, la méthode comprenant obtenir une liste d'entiers à coder; déterminer une pyramide hyperspatiale ayant une taille adaptée pour coder la liste d'entiers, la pyramide hyperspatiale ayant une pluralité de sommets dont le nombre est déterminé par le degré de la pyramide hyperspatiale qui est égal à la somme des entiers de la liste d'entiers et par la dimension de la pyramide hyperspatiale qui est égale au nombre d'entiers de la liste d'entiers moins un; indexer la liste d'entiers dans cette pyramide au moyen d'un système d'indexation; et fournir une indication de l'indexation de la liste d'entiers dans la pyramide hyperspatiale afin de coder ainsi ladite liste d'entiers à coder.
PCT/CA2012/001042 2011-11-10 2012-11-13 Méthode et système pour coder de l'information Ceased WO2013067629A1 (fr)

Priority Applications (3)

Application Number Priority Date Filing Date Title
EP12847457.4A EP2777159A4 (fr) 2011-11-10 2012-11-13 Méthode et système pour coder de l'information
US14/357,468 US9900024B2 (en) 2011-11-10 2012-11-13 Method and system for coding information
CA2855169A CA2855169C (fr) 2011-11-10 2012-11-13 Methode et systeme pour coder de l'information

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CA2758243 2011-11-10
CA2758243 2011-11-10

Publications (1)

Publication Number Publication Date
WO2013067629A1 true WO2013067629A1 (fr) 2013-05-16

Family

ID=48288401

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CA2012/001042 Ceased WO2013067629A1 (fr) 2011-11-10 2012-11-13 Méthode et système pour coder de l'information

Country Status (4)

Country Link
US (1) US9900024B2 (fr)
EP (1) EP2777159A4 (fr)
CA (1) CA2855169C (fr)
WO (1) WO2013067629A1 (fr)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE102016108018A1 (de) * 2016-03-03 2017-09-07 Cadami Ug (Haftungsbeschränkt) Kennungscodierungseinrichtung und Kennungsdecodierungseinrichtung zur Datenverteilung in Netzwerken sowie derartige Einrichtungen aufweisende Netzwerkelemente
DE102016103882A1 (de) * 2016-03-03 2017-09-07 Cadami Ug (Haftungsbeschränkt) Zuordnungsverfahren sowie Netzwerk mit einer Zuordnungsvorrichtung
US11146397B2 (en) * 2017-10-31 2021-10-12 Micro Focus Llc Encoding abelian variety-based ciphertext with metadata
CN108536651B (zh) * 2018-04-19 2022-04-05 武汉轻工大学 生成可逆模m矩阵的方法和装置
US11764940B2 (en) 2019-01-10 2023-09-19 Duality Technologies, Inc. Secure search of secret data in a semi-trusted environment using homomorphic encryption
US11115250B1 (en) * 2019-03-01 2021-09-07 Acacia Communications, Inc. MPPM encoder and decoder
KR102424856B1 (ko) * 2019-05-09 2022-07-22 구글 엘엘씨 Rlwe 암호문들의 압축 및 불확정적 확장
CN114422103B (zh) * 2021-12-10 2025-02-07 广东联合电子服务股份有限公司 加密系统及其密钥配置及调用方法

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2006110002A1 (fr) * 2005-04-13 2006-10-19 Electronics And Telecommunications Research Intitute Procede et dispositif destines au codage/decodage d'informations relatives a un maillage 3d

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5392036A (en) * 1993-10-28 1995-02-21 Mitan Software International (1989) Ltd. Efficient optimal data recopression method and apparatus

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2006110002A1 (fr) * 2005-04-13 2006-10-19 Electronics And Telecommunications Research Intitute Procede et dispositif destines au codage/decodage d'informations relatives a un maillage 3d

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
CRAIG, J.W.: "Multidimensional trellis coding for MPSK", MILITARY COMMUNICATIONS CONFERENCE, 1990. MILCOM'90, CONFERENCE RECORD, A NEW ERA. 1990 IEEE, vol. 1, 30 September 1990 (1990-09-30), pages 369 - 374, XP000221809 *
See also references of EP2777159A4 *

Also Published As

Publication number Publication date
EP2777159A4 (fr) 2016-07-13
US20150318865A1 (en) 2015-11-05
CA2855169C (fr) 2016-01-19
CA2855169A1 (fr) 2013-05-16
US9900024B2 (en) 2018-02-20
EP2777159A1 (fr) 2014-09-17

Similar Documents

Publication Publication Date Title
CA2855169C (fr) Methode et systeme pour coder de l&#39;information
Raissi et al. Optimal quantum error correcting codes from absolutely maximally entangled states
US20140236907A1 (en) Selecting candidate rows for deduplication
Hivert et al. Commutative combinatorial Hopf algebras
WO2016094687A1 (fr) Appareil et procédé de représentations et de fonctions relatives à des données reposant sur des hypercartes combinatoires
Prezza Optimal rank and select queries on dictionary-compressed text
US12253970B2 (en) Compression and search process on a data set based on multiple strategies
Brown et al. RLBWT tricks
Wang et al. Decoding nonbinary LDPC codes via proximal-ADMM approach
Iliopoulos The Quicksort algorithm and related topics
Kokkala et al. Classification of Graeco‐Latin Cubes
Constantinescu et al. Generic and special constructions of pure O-sequences
Marcus et al. 2D Lyndon words and applications
Kulkarni et al. Combinatorial properties of Fibonacci arrays
Chee et al. A generalization of the blackburn-etzion construction for private information retrieval array codes
Chee et al. Efficient encoding/decoding of irreducible words for codes correcting tandem duplications
He et al. Heterotic bundles on Calabi-Yau manifolds with small Picard number
Formenti et al. An enumeration algorithm for binary coprime polynomials with nonzero constant term
Hang et al. U-match factorization: sparse homological algebra, lazy cycle representatives, and dualities in persistent (co) homology
Álvarez et al. Determinants of $(-1, 1) $-matrices of the skew-symmetric type: a cocyclic approach
Diallo et al. New free distance bounds and design techniques for joint source-channel variable-length codes
Afshar et al. Adaptive exact learning in a mixed-up world: Dealing with periodicity, errors and jumbled-index queries in string reconstruction
Byrapuram et al. EvenQuads Game and Error-Correcting Codes
Chakrabarti Multivariate polynomials modulo prime powers: their roots, zeta-function and applications
Bastos et al. Linearity of Z 2 L-linear codes via Schur product: GT Bastos et al.

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 12847457

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2855169

Country of ref document: CA

NENP Non-entry into the national phase

Ref country code: DE

REEP Request for entry into the european phase

Ref document number: 2012847457

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 2012847457

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 14357468

Country of ref document: US