Lossless binary data compression

A method for lossless compression of a binary input data string (IFDS), comprising:

• partitioning said IFDS in processing strings (PS) as they serially occur in said IFDS, with every said occurring PS belonging to a set of PS, comprising:
• every PS in said set is unique and has a number of bits greater than a minimum number of bits;
• there is one or more PS having the same number of bits, and all PS of same number of bits form a class of PS;
• within a said class of PS, one or more PS are represented by a common header called root identifier (RI) with said RI having a number of bits that is smaller or equal to the number of bits of that class of PS, followed by a difference number of bits equal to the difference between the number of bits of that class of PS and the number of bits of said RI, where said difference number of bits is called remain;
• and
• all said RI of all said classes of PS form a set of RI, with every RI in said set of RI having a number of bits greater than a minimum number of bits and being unique, with one or more RI having the same number of bits, and with all RI of same number of bits forming a class of RI;
• describing said IFDS using said RI in said set of RI by making the correspondence between every said occurring PS and the corresponding RI, called occurring RI;
• dividing said IFDS as described by said occurring RI in a first number of serial groups of said occurring RI called pairing ranges, with each said pairing range having a same second number of said serially occurring RI, wherein:
• each of said first number of said pairing ranges receives a first order number in ascending order starting with one;
• within each said pairing range, each RI can be part of a higher order combination of RI such as pairs or triplets, with each RI belonging to only one such higher order combination, wherein:
• a said higher order combination of RI is also unique and has a number of bits greater than a minimum number of bits;
• and
• one or more said higher order combinations have the same number of bits, with all said higher order combinations of same number of bits forming a class of said higher order combinations, and with all classes of higher order combinations forming a set of higher order combinations;
• and
• in all said pairing ranges, either individual RI or one of said higher order combinations is engaged and called RI derivative, with said RI derivative in each said pairing range receiving a second order number in ascending order starting with one;
• creating a first data structure, comprising:
• occurrence of said first RI derivative number of said pairing ranges;
• if in a pairing range of a first order number said first RI derivative occurs multiple times, each time at a different said second order number, said first RI derivative that has a second order number value that is the closest to the second order number value of the current segment of said first data structure is considered;
• and
• said first RI derivative is selected when in all segments of said first data structure, no occurrence of said first RI derivative exists, and when at least one occurrence of said first RI derivative exists, a different first RI derivative is considered;
• creating a second data structure, comprising:
• a second RI derivative belonging to a said RI derivative class of a fourth number of bits greater or equal to said third number of bits of said first RI derivative;
• a same first maximum number of said pairing ranges;
• one or more segments, also known as legs, wherein:
• each said segment comprising of said occurring RI derivatives that have the same second order number in pairing ranges of consecutive first order numbers;
• a first said segment starts with a said occurring RI derivative having a said second order number and being located at said pairing range of first order number of value one, and ends with a said second RI derivative located at a pairing range of a first order number of value greater than one;
• every subsequent segment starts with a said occurring RI derivative having said second order number equal to a second order number at which a next occurrence of said second RI derivative has the highest probability to occur, and a said pairing range of first order number value equal to the first order number of last occurrence of said second RI derivative plus one, and ends with a said second RI derivate located at a pairing range of a first order number of value greater or equal to the first order number of last occurrence of said second RI derivative plus one, or ends with a said occurring RI derivative located at a pairing range of said first order number of value equal to said first maximum when said second RI derivative does not occur before said first maximum is reached on current said segment;
• said next occurrence of said second RI derivative has the highest probability to occur when located on a second order number on which said second RI derivative occurred last at the largest distance in term of the difference between said first order number of said second RI derivative that occurred last and current said first order number;
• if there are multiple said second RI derivatives of same highest probability each at a different second order number, the second order number of a value that is the closest to the second order number value of the current segment of said second structure is considered;
• and
• said second RI derivative is selected when in all segments of said second data structure, the number of occurrences of said second RI derivative is maximum among all other second RI derivates that can be selected;
• and
• processing said first data structure and said second data structure together, in order to generate an output file featuring compression gain, with said compression gain being expressed in term of a fifth number of bits.