Abstract

Data compression has been widely applied in many data processing areas. Compression methods use variable-length codes with the shorter codes assigned to symbols or groups of symbols that appear in the data frequently. Fibonacci code, as a representative of these codes, is often utilized for the compression of small numbers. Time consumption of encoding as well as decoding algorithms is important for some applications in the data processing area. In this case, efficiency of these algorithms is extremely important. There are some works related to the fast decoding of variable-length codes. In this paper, we introduce the Fast Fibonacci encoding algorithm; our approach is up-to 4.6× more efficient than the conventional bit-oriented algorithm.

-

Introduction ? Work is partially supported by Grants of GACR No. P202/10/0573 and SGS, VSˇB–

Technical University of Ostrava, No. SP/2010138.

The time consumption of decompression is more critical than the time of compression; therefore, efficient decompression algorithms were studied in many works for the decompression of data structures [ 15, 6, 16 ] or text files [ 12, 3 ]. In the case of physical implementation of database systems, retrieval of compressed data structure’s pages may be more efficient than retrieval of uncompressed pages due to the fact that the cost of decompression is lower than the cost of page accessing in the secondary storage [ 16, 2 ].

Since fast decoding algorithms have not yet been known, variable-length codes have not been used to compression of data structures, and, in generally, in the data processing area. The first effort of the fast decoding algorithm for Fibonacci codes of order ≥ 2 has been proposed in [ 7, 8 ]. We studied fast decoding algorithms of various variable-length codes in our previous work [ 17 ]. The fast encoding algorithms for the Fibonacci code yet not has been studied. In the case of data structures, pages are decompressed during every reading from the secondary storage into the main memory or items of a page are decompressed during every access to the page. If insert or update operations are considered, data compression becomes more significant.

In this article, we present Fast encoding algorithm of the Fibonacci of order 2 code. In Section 2, we describe the conventional Fibonacci of order 2 encoding algorithm. In Section 3, we provide a theoretical background of the fast encoding algorithm based on Fibonacci right shift and Encoding-Interval table. In Section 4, experimental results are presented and the proposed algorithm is compared to the conventional approach. In the last section, we conclude this paper and outline future works. 2

Fibonacci Coding In this section, the theoretical background of Fibonacci of order 2 is briefly described. This universal code introduced by Apostolico and Fraenkel in [ 1 ] is based on the Fibonacci numbers [ 10 ]. The sequence of Fibonacci numbers is defined as follows:

Fi = Fi−1 + Fi−2 , for i ≥ 1,

where F−1 = F0 = 1.

Definition 1. (Fibonacci binary encoding and computation of its value)

Let F (n) = a0a1a2 . . . ap be the Fibonacci binary encoding of a positive integer n. The value of the Fibonacci binary encoding, denoted V (F (n)), is defined as follows:

V (F (n)) = n =

p X aiFi (ai ∈ {0, 1}, 0 ≤ i ≤ p) i=0

In the Fibonacci binary encoding, each bit represents a Fibonacci number Fi. Such a number has the property of not containing any sequence of two consecutive 1-bits [ 1 ]. This property is utilized for the construction of the Fibonacci code F (n) of number n. Fibonacci code F (n) maps n onto a binary string so that the string ends with a sequence of two consecutive 1-bits. The Fibonacci codes for some integers are shown in Table 1.

In Algorithm 1, we see how the conventional bit-oriented algorithm encodes a positive integer n into a Fibonacci code. This algorithm outputs the encoded number into F n and its length into LF n. Due to the fact that bits of Fibonacci coding are encoded in the reverse order we must use the temporary Fn variable. Bits in the variable are right-shifted in each inner loop. 3

Fast Fibonacci Encoding Algorithm The main issue of the conventional encoding algorithm is handling encoded numbers in the bit-by-bit manner. To design a fast encoding algorithm, encoded numbers are separated into segments larger than one bit. Similar principles have been utilized in fast decoding algorithms [ 17, 8, 9 ]. The separation of encoded numbers utilizes the Fibonacci right shift operation introduced in [ 17, 9 ]. Individual segments are then encoded by the precomputed Encoding-Interval table. When all individual segments are encoded, they are put together into the complete code. The Fibonacci right shift and Encoding-Interval table are presented in Section 3.1. The fast algorithm is explained in Section 3.2. 3.1

Fibonacci Shift Operation and Encoding-Interval Table The Fibonacci shift operation introduced in [ 17, 9 ] is required for the bit manipulation in fast encoding and decoding algorithms. In this paper, we introduce an efficient computation of this operation. input : n, a positive integer output: Fn, encoded number by Fibonacci code of order 2 with LFn length 1 p ← 0 ; 2 while Fp ≤ n do p ←p +1; 3 p ← p − 1; 4 Fn ← 1; 5 LFn ← 1; 6 while p ≥ 0 do 7 Fn ← Fn << 1; 8 if Fp ≤ n then 9 Fn ← Fn | 1; 10 n ← n − Fp; 11 end 12 LFn ←LFn +1; 13 p ← p − 1; 14 end Algorithm 1: Conventional encoding algorithm for the Fibonacci code of order 2

Definition 2. Fibonacci shift operation

Let F (n) = a0a1a2 . . . ap be a Fibonacci binary encoding, k be an integer, k ≥ 0. The k-th Fibonacci left shift F (n) <<F k is defined as follows: k

F (n) <<F k = z00}.|. . 0{ a0a1a2 . . . ap

Fibonacci right shift is defined as is follows:

F (n) >>F k = akak+1ak+2 . . . ap

We utilize k-Fibonacci right shifts for the separation of numbers into segments. We do not need all k-Fibonacci right shifts, we only need multiplies of the segment size S. If we consider 32 bit-length integers than the length of the largest code is L(F (232)) = 46; therefore, k ∈ {0, 8, 16, 24, 32, 40} for S = 8 and k ∈ {0, 16, 32} for S = 16.

The conventional approach to the calculation of Fibonacci right shift works in the following steps: 1. Compute F (n) for the n value according to Definition 1. 2. Binary-shift the bits of F (n) by k: F (n) >> k. 3. Compute the value of the shifted number F (n) >> k according to Definition 1.

The Fibonacci right shift operation is time consuming since the Fibonacci value computation in Steps 1 and 3 requires a summarization of Fibonacci numbers for 1-bits; therefore, we utilize the Encoding-Interval table for the fast computation.

The Encoding-Interval table allows separating of numbers into segments with the k-th Fibonacci right shift and then direct translation of segments into Fibonacci codes. The size of the Encoding-Interval table depends on the size of the segment S. The segment size is usually one byte, i.e. S = 8. When we use larger segments the length of the Encoding-Interval table grows; on the other hand, the encoding becomes faster. There are FS − 1 codes which can fit into one segment; it means F8 − 1 = 54 codes which can fit into the 8 bit-length segment and F16 − 1 = 2, 583 codes for the 16 bit-length segment.

Therefore, the total size of the Encoding-Interval table is: l 2b m table length = (FS − 1) × S where b is the number of bits of the largest code.

Each line of the Encoding-Interval table is then built for all F (n) codes which can fit into one segment and for all k-th Fibonacci right shifts. Each line includes the following values (see Table 3 for some examples): – F (n) – the Fibonacci code stored in the segment. – L(F (n)) – the bit-length of the Fibonacci code – k – the parameter k of the Fibonacci right shift operation – n – the value stored in the actual segment n = V (F (n)) – hnmin, nmaxi – an interval of numbers before the shift operation; this number is formally defined as follows: ∀x ∈ hnmin, nmaxi : V (F (x) >> F k) = n.

This table can be used for the computation of the k-th Fibonacci right shift. For each x value we need to pass through the table to find the correct line where x ∈ hnmin, nmaxi. In this line we can directly read the shifted value V (F (x)) >>F k = n and also the corresponding Fibonacci code F (n). Obviously, we need to pass only lines with correct k-th Fibonacci right shift.

To be able to compute a shifted value as fast as possible, we must consider the properties of the Fibonacci code. Let Fi denote the i-th term of the Fibonacci sequence then we can express each Fibonacci number by

Fi = bφi where φ is the well-known golden ratio [ 11 ] and a is the coefficient of the domi√ nating term [ 9 ]. In the case of Fibonacci of order 2 the value φ = 1+2 5 ≈ 1.6180 and b = 3√5+5 [ 4 ]. The Fibonacci sequence calculated according to this formula 10 is shown in Table 2.

The maximum error of the estimation is 1; by experiments we found, when the estimation misses, it is overestimated; therefore, the correct value is less by 1. To check if the estimation is correct we compare the estimation with a range in the Encoding-Interval table. If the check fails, we simply subtract the 1 value and receive the correct right shift value. In other words, this estimation decreases the linear complexity of the table scan to at most two attempts. Example 1. First, let us consider V (F (n)) = n = 265; F (n) = 001010100001. We calculate the estimation of the 8-th Fibonacci right shift as follows: V (F (265) >>F 8) ≈ Table 3 shows some lines of the Encoding-Interval table for the 8-th Fibonacci right shift. After checking the 5-th line of the table we see that the value lies in the interval < 233; 287 >; therefore, V (0001) = 5 is the correct value of the 8-th Fibonacci right shift.

Second, let us consider V (F (n)) = n = 280; F (n) = 000001010001. We calculate the estimation:

V (F (280) >>F k) ≈

After checking the interval in the 6-th line of the Encoding-Interval table we see that the value not lies in the interval < 288; 321 >; therefore, the estimation is not correct and the correct value is less by 1. The correct value of the 8-th Fibonacci right shift of 280 is V (0001) = 5. The fast encoding algorithm is shown in Algorithm 2. This algorithm utilizes the previously proposed Encoding-Interval table denoted by EIT . Due to the fact that the bits of the Fibonacci code are stored in the reverse order we need to write the bits of segments in the reverse order as well. Encoded segments or their parts are stored in a specific position of the result F n by the SetV alueOf Segment function.

In Algorithm 2, n is encoded by Fibonacci coding; the result is stored in the F n, the length is stored in the LF n. Short numbers with the code lower than F8 are directly encoded by the Encoding-Interval table (see Lines 3–5). For larger numbers we first need to find the maximal k of the Fibonacci right shift (see Line 7). After the number is separated with k-Fibonacci right shift, it is encoded by the Encoding-Interval table and stored into the highest segment with position k/8 (see Lines 8–10). In Line 11, we subtract the minimal range of the encoded segment from the n. In Lines 12–20, all other segments except the lower one are separated by Fibonacci right shifts and they are encoded by the Encoding-Interval table. The length of the encoded number is increased by the segment size in Line 19. The lowest segment is encoded in Line 21. Finally, in Lines 23–24, the delimiter is put at the end of the encoded number. input : n, a positive integer output: Fn, number encoded by Fibonacci code of order 2 with the LFn length while n < Fk+8 do k ← k +8; n ← n >>F k; LFn ← 8+ EIT[k ].LFn; SetValueOfSegment(Fn,k/8,EIT[k ][n ].Fn); n ← n −EIT[k ][n ].Nmin; while k > 8 do k ← k −8; if n ≥Fk then n ← n >>F k; n ← n − EIT[k ][n ].Nmin;

SetValueOfSegment(Fn,k/8,EIT[k ][n ].Fn);

Algorithm 2: Fast encoding algorithm for the Fibonacci code of order 2 Example 2. Encoding of the number 17327 is depicted in Figure 1. The value of the Fibonacci code stored in all segments is V (F (17327)) = 17327. Encoding of the highest segment is depicted in Figure 2(a). After the 16-th Fibonacci right shift of the value F (17327), i.e. F (17327) >>F 16, we obtain the shifted Fibonacci code F (7). The value after the shift is depicted in Line 3. It represents the Segment 2 value. We directly access the line 7 of the Encoding-Interval table by the 16-th Fibonacci right shift and we directly find the code F (7) = 10 with the length L(F (7)) = 4. The result is in the range h15127; 17710i. The lower bound of the range is depicted in Line 2. The value of Segments 0 and 1 is obtained by subtracting the lower bound of the range from the V (F (17327)) number, i.e Segments 0 and 1 stores V (F (17327)) − 15127 = V (F (2200)). This encoding is carried out in Lines 8–11 of Algorithm 2.

F(17327)

F(2200) LINE 1 1 0 0 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 . . . .

Segment 0 Segment 1 Segment 2

Further encoding is depicted in Figure 2(b). The value of the Fibonacci code stored in Segments 0 and 1 is V (F (2200)) = 2200. After the 8-th Fibonacci right shift of the value F (2200), i.e. F (2200) >>F 8, we obtain the shifted Fibonacci code F (46). The value after the shift is depicted in Line 3. It represents the separated value from Segment 1. We directly access the line 46 of the Encoding-Interval table by the 8-th Fibonacci right shift and we directly find the code F (46) = 149 with the length L(F (46)) = 8. The result is in the range h2173; 2206i. The lower bound of the range is depicted in Line 2. The value of Segment 0 is obtained by subtracting the lower bound of the range from V (F (2200)) number, i.e Segment 0 includes V (F (2200)) − 2173 = V (F (27)). This encoding is carried out in Lines 12–20 of Algorithm 2.

The last Segment 0 with the value V (F (27)) is directly encoded into F (27) = 73 with the length L(F (27)) = 7 in Line 21 of Algorithm 2. We access the line 27 of the Encoding-Interval table for any shift to obtain this value, because we do not need any following subtraction.

Finally, the 1-bit delimiter is added in position 8+8+L(F (7))+1 = 8+8+4 = 12 of the encoded number (see Lines 23–24 of Algorithm 2). 4

Experimental Results The proposed Fast Fibonacci encoding algorithm has been tested and compared with the conventional algorithm. The algorithms’ performance has been tested for various test collections. The tests were performed on a PC with dual core Intel 2.4GHz, 3 GB RAM using Windows 7 32-bit.

The test collections used in experiments have the same size: 10, 000, 000 numbers. The proposed algorithm is universal and it may be applied for arbitrary numbers > 0. However, we worked with numbers ≤ 4, 294, 967, 295, it means the maximal value is the value of the 32 bit-length binary number. Tested collections are as follows: – 8-bit – a collection of random numbers ranging from 1 to 255 – 16-bit – a collection of random numbers ranging from 256 to 65,535 – 24-bit – a collection of random numbers ranging from 65,536 to 16,777,215 – 32-bit – a collection of random numbers ranging from 16,777,216 to 4,294,967,295 – ALL - a collection of random numbers ranging from 1 to 4,294,967,295

We performed tests for segment sizes S = 8 and S = 16. We ran each test 10 times and calculated average values. Results of all tests are depicted in Table 4 and Figure 2. The Fast Fibonacci encoding algorithm is approximately 2.6× faster than the conventional approach for the segment size S = 8 and 4.6× faster for the segment size S = 16. The encoding times linearly increase with the bit-length of encoded numbers but the speedup ratio is not influenced by this increasing.

Encoding Times Speedup Ratio 5,000 4,000 ] 3,000 s [m2,000 1,000 0 In this paper, the fast encoding algorithm for the Fibonacci code of order 2 is introduced. We introduced the effective implementation of Fibonacci right shift which is utilized by the encoding algorithm for separating integers into segments. The segments are directly translated into the Fibonacci code by the Encoding-Interval table. The improvement depends on the segment size used for the separation of the encoded numbers. For the segment size S = 8 (it means one byte), the Fast Fibonacci encoding is up-to 2.6× more efficient than the conventional algorithm. For the larger segment of two bytes in size (it means S = 16), the proposed algorithm is up-to 4.6× more efficient than the conventional algorithm. In our future work, we want to develop fast encoding algorithms for other universal codes like Elias-delta [ 5 ], Fibonacci code of order 3 [ 1 ], and so on.

References

1. A. Apostolico and A. Fraenkel . Robust Transmission of Unbounded Strings Using Fibonacci Representations . IEEE Transactions on Information Theory , 33 ( 2 ): 238 - 245 , 1987 .

2. R. Baˇca , J. Walder, M. Pawlas , and M. Kra´tky´. Benchmarking the Compression of XML Node Streams . In Proceedings of the BenchmarX 2010 International Workshop , DASFAA, Accepted. Springer-Verlag, 2010 .

3. T. C. Bell and I. H. Witten . Text Compression. Prentice Hall, 1990 .

4. R. A. Dunlap . The Golden Ratio and Fibonacci Numbers. World Scientific Publishing Co. Pte. Ltd. , 1997 .

5. P. Elias . Universal Codeword Sets and Representations of the Integers . IEEE Transactions on Information Theory , IT- 21 ( 2 ): 194 - 203 , 1975 .

6. J. Goldstein , R. Ramakrishnan , and U. Shaft . Compressing Relations and Indexes . In Proceedings of the 14th International Conference on Data Engineering, ICDE 1998 , page 370, Los Alamitos, CA, USA, 1998 . IEEE Computer Society.

7. S. T. Klein . Fast Decoding of Fibonacci Encoded Texts . In Proceedings of the International Data Compression Conference, DCC'07, page 388 , Washington, DC, USA, 2007 . IEEE Computer Society.

8. S. T. Klein and M. K. Ben-Nissan . Using Fibonacci Compression Codes as Alternatives to Dense Codes . In Proceedings of the International Data Compression Conference, DCC'08 , pages 472 - 481 , Washington, DC, USA, 2008 . IEEE Computer Society.

9. S. T. Klein and M. K. Ben-Nissan . On the Usefulness of Fibonacci Compression Codes . Accepted in Computer Journal , 2009 , 2009 .

10. Leonardo of Pisa (known as Fibonacci) . Liber Abaci . 1202 .

11. M. Livio . The Golden Ratio: The Story of Phi, the World's Most Astonishing Number . Broadway, January 2003 .

12. H. Plantinga . An Asymmetric, Semi-adaptive Text Compression Algorithm . In Proceedings of the International Data Compression Conference , DCC 1994 . IEEE Computer Society, 1994 .

13. D. Salomon . Data Compression The Complete Reference. Third Edition , SpringerVerlag, New York, 2004 .

14. D. Salomon . Variable-length Codes for Data Compression . Springer-Verlag, 2007 .

15. H. Samet . Data Structures for Quadtree Approximation and Compression . Communications of the ACM archive , 28 ( 9 ): 973 - 993 , September 1985 .

16. J. Walder , M. Kra´tky´, and R. Baˇca . Benchmarking Coding Algorithms for the R-tree Compression . In Proceedings of the Dateso 2009 Annual International Workshop on Databases, Texts, Specifications and Objects , pages 32 - 43 . CEUR Workshop Proceedings, Volume: 471 , 2009 .

17. J. Walder , M. Kr´atky´, R. Baˇca, J. Platoˇs, and V. Sna´ˇsel. Fast Decoding Algorithms for Variable-Lengths Codes . Submitted in Information Science, January, 2010 .

18. I. H. Witten , A. Moffat , and T. C. Bell . Managing Gigabytes, Compressing and Indexing Documents and Images, 2nd edition . Morgan Kaufmann, 1999 .