{'fraction_non_alphanumeric': 0.03400933589612835, 'fraction_numerical': 0.01722041344682854, 'mean_word_length': 4.360386879730866, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computable Compressed Matrices

The biggest cost of computing with large matrices in any modern computer is related to memory latency and bandwidth. The average latency of modern RAM reads is 150 times greater than a clock step of the processor. Throughput is a little better but still 25 times slower than the CPU can consume. The application of bitstring compression allows for larger matrices to be moved entirely to the cache memory of the computer, which has much better latency and bandwidth (average latency of L1 cache is 3 to 4 clock steps). This allows for massive performance gains as well as the ability to simulate much larger models efficiently. In this work, we propose a methodology to compress matrices in such a way that they retain their mathematical properties. Considerable compression of the data is also achieved in the process Thus allowing for the computation of much larger linear problems within the same memory constraints when compared with the traditional representation of matrices.


Introduction
Data compression is traditionally used to reduce storage resources usage and/or transmission costs [2]. Compression techniques can be classified into lossy and lossless. Examples of lossy data compression are MP3 (audio), JPEG (image) and MPEG (video). In this paper we discuss the use of lossless compression for numerical data structures such as numerical arrays to achieve compression without losing the mathematical properties of the original data.
Lossless compression methods usually exploit redundancies present in the data in order to find a shorter form of describing the same information content. For example, a dictionary-based compression, only stores the positions in which a given word occurs in a document, thus saving the space required to store all its repetitions [3].
Any kind of compression incurs some computational cost. Such costs often have to be paid twice since the data needs to be decompressed to be used for its original purpose. Sometimes computational costs are irrelevant, but the need to decompress for usage, can signify that the space saved with compression must be available when data is decompressed for usage, thus partially negating the advantages of compression.
Most if not all existing lossless compression methods were developed under the following usage paradigm: produce → compress → store → uncompress → use. The focus of the present work is to allow a slightly different usage: produce → compress → perform mathematical manipulations and decompress (only for human reading).
With the growth of data volumes and analytical demands, creative solutions are needed to efficiently store as well as consume it on demand. This issue is present in many areas of application, ranging from business to science [4], and is being called the Big Data phenomenon. In the world of Big Data, the need to analyze data immediately after its coming into existence became the norm. And this analysis must take place, efficiently, within the confines of (RAM) memory. This kind of analyses are what is now known as streaming data analysis [5]. Given a sufficiently dense stream of data, compression an decompression costs may become prohibitive. So having a way to compress data and keeping it compressed for the entire course of the analytical pipeline, is very desirable. This paper will focus solely on numerical data which for the purpose of the applications is organized as matrices. This is a most common data structure found in computational data analysis environments. The matrices compressed according to the methodologies proposed here should be able to undergo the same mathematical operations as the original uncompressed matrices, e.g. linear algebra manipulations. This way, the cost of compression is reduced to a single event of compression and no need of decompression except when displaying the results for human reading. The idea of operating with compressed arrays is relatively new [6], and it has yet to find mainstream applications to the field of numerical computations. One application which employs a form of compression is the sparse matrix linear algebra algorithms [7], in this case there is no alteration in the standard encoding of the data, but only the non-zero elements of the matrices are stored and operated upon.
Larger than RAM data structures can render traditional analytical algorithms impracticable. Currently, the technique most commonly used when dealing with large matrices for numerical computations, is memory mapping [8,9]. In memory mapping the matrix is allocated in a virtual contiguous address space which extends from memory into disk. Thus, larger than memory data structures can be manipulated as if they were in memory. This technique has a big performance penalty due to lower access speeds of disk when compared to RAM.
In this paper we present two methods for the lossless compression of (numerical) arrays. The methods involve the encoding of the numbers as strings of bits of variable length. The methods resemble the arithmetic coding [10] algorithm, but is cheaper to compute. We describe the process of compression and decompression, and study their efficiency under different applications. We also discuss the efficiency of the compression as a function of the distribution of the elements of the matrix.

Matrix compression
To maintain mathematical equivalence with the original data for any arithmetic operations, we need to maintain the structure of the matrix, i.e., the ability to acess any element given its row i and column j and also the numeric nature of its elements. In order to achieve compression we decided to exploit inefficiencies in the conventional way matrices are allocated in memory. The examples in this paper will be restricted to matrices with positive integer elements.
The compression method is as follows. Let M r×c be a matrix, in which r is the number of rows and c the number of columns. Each element of this matrix, called m ij , is a positive integer. In digital computers, all information is stored as binary code (base 2 numbers). However the conventional way to store arrays of integers is on a memory block sequence of fixed size (power of 2 numbers of bit), one for each element. The maximum size of a block is equal to the word size of the processor, which for most current CPUs is 64 bits. Some special number such as complex number may be encoded as two blocks instead of one. The size of the chunk of memory allocated to each number will determine their maximum size (for integers) or their precision (for floating-point numbes). So for matrix M , the total memory allocated, assuming chunks of 64 bits, is given by B = r × c × 64.
The number of bits allocated B, is larger than the absolute minimum number of bits required to represent all the elements of M , since smaller integers, when converted to base 2, require less digits. From now on, when the numerical base will be explicitly notated when necessary to avoid confusion between binary and decimal integers.
Let's consider an extreme example: a matrix composed exclusively of 0s and 1s (base 10). If the matrix type is set to 64-bit integers, 63 bits will be wasted per element of the matrix, since the minimum number of bits needed to store such a matrix is b = r × c × 1. The potential economy of bits ξ can be So it is evident that for any matrix whose greatest element requires less than 64 bits (or the fixed type of the matrix) to be represented, potential memory savings will grow linearly with the size of the matrix.

Method 1: The Supreme Minimum (SM)
The SM method consists in determining the value of the greatest element of matrix M , which coincides with its supremum, maxM == sup M and determine the minimum number of bits, b(sup M )(Equation 1), required to store it. We will use capital roman letters to denote uncompressed matrices and the corresponding lower case letter for the compressed version.
The allocation of memory still happens in the usual way, i.e., in fixed size 64-bit chunks, only that now, in the space required for a single 64 bit integer, we can store for example, an entire 8 × 8 matrix of 0 10 and 1 10 .
Let's look at a concrete example: suppose that the greatest value to be stored in a matrix M is max M = 1023. Therefore, the number of bits required to represent it is 10 (1111111111 These elements of M , in binary, are shown in Table 1. It is evident that the number of bits required to represent any other element must be lower or equal to 10. From now on the minimum number of bits required to represent a base 10 integer will be refered to as its bit-length. To store matrix M it first has to be converted to base 2 (M 2 ). Then it will be unraveled by column (column major, e.g. in Fortran) or by row (row major, e.g. in C) and its elements will be written as fixed size adjacent chunks of memory. The size of each chunk is determined by the type associated with the matrix (typically 64 bits, but always a power of 2).
According to the SM method, having determined that each element will require at most 10 bits, we can divide the memory block corresponding to a single 64 bit integer into six 10-bit chunks which can each hold a single element of M . These 64-bit blocks will be called a bitstring. The remaining 4 bits will be used later. The number of bitstrings needed will be ⌊ dim Here is a step-by-step description of the application of the SM method to matrix M : 1. Element M 1,1 = 900 = m 1,1 = 1110000100 is stored in the first 10-bit chunk of the element strip bitstring [1] , which corresponds to bits 0 to 9 (read from right to left).  Thus the compressed matrix m = M 2 requires less memory than the conventional storage of M as a 64-bit integer array.

Method 2: Variable Length Blocks (VLB)
In the SM method, there is still waste of space since for elements smaller than the supremum, a number of bits remain unused.
In the VBL method, the absolute minimal number of bits are used to store each value. However, if we are going to divide the biststrings into variable length chunks, we also need to reserve some extra bits to represent the size of each chunk, otherwise the elements cannot be recovered once they are stored.
Lets use again the matrix described in Equation 2, where the largest element is number 1023. Now instead of assigning one chunk of the bitstring to each element of m, we will assign two chunks: the first will store the number of bits required to store the element and the second will store the actual element.
The first chunk will have a fixed size, in this case, 4 bits. These 4 bits are the required space to store the bit-length of sup M , in this case, 10.
Lets go through VLB compression step-by-step. The largest element of M is 1023. Its bit-length is 10 which in turn is 4 bits long in base 2 (1010). Thus the fixed size chunk is 4 bits long for every element.
1. The first element M 1,1 = 900 requires 10 bits to store, so we write 10 in the first chunk and 900 in the second. So far the VLB method is more wasteful than the SM, but when we add M 1,4 = 256 we start to save some space. We used a total of 87 bits to store matrix m with the VLB method instead of 80 bits using the SM method. However, as shall be seen later, the VLB method will be the most efficient for most matrices.

Compression Efficiency
Compression efficiency depends of the data being compressed. Below, a formula for calculating compression efficiency is derived for both methods. They will be based on the following ratio: Where bits alocated above mean total bits required for standard storage of the matrix, without compression, while bits used mean total bits requires to store the matrix after compression. From now on the efficiencies are denoted by η 1 for the SM method and by η 2 for the VLB method.

SM Method
Let M r×c be the matrix we wish to compress. In comparison with a conventional allocation (64-bit integers), we can apply Equation 4 to caluculate the efficiency of the SM method: As we see in 5, η 1 does not depend on size of the matrix, only on the bit-length of max M . If b(max M ) = 64, η 1 is 0, i.e., no compression is possible. On the other extreme, if the matrix is composed exclusively of 0s and 1s, maximal compression is achievable, η 1 = 1.

VLB Method
For the VLB method, compression depends on the value of each element of the matrix. In this method bit-lentgh variability affects the compression ratio, so the formula will have to include this information.
Let the rc elements of the matrix M r×c be divided into g groups, each with f i numbers of bit-length , the bit length of the bit-length of max M . The efficiency η 2 is shown below.
We can further simplify Equation 6 to get at shorter expression for the compression ratio.
we can simplify the equation above, obtaining (7).
Results Random Matrix Generation. In both methods, compression efficiency depends on the distribution of the bit-lengths b(m i,j ). Thus, in this section, a method to generate a variety of random bit-length distributions is proposed.
For simplicity we will model the distribution of as a mixture X of two Beta distributions, B 1 ∼ Beta(α 1 , β 1 ) and B 2 ∼ Beta(α 2 , β 2 ), whose probability function is shown in Equation 8. Since the Beta distribution is defined only in the interval [0, 1] ⊂ R , we applied a simple transformation (⌊64 × x⌋ + 1) to the mixture in order to map it to the interval of [1, 64] ⊂ Z.
The intention of using this mixture was to find a simple way to represent a large variety of bit length distributions. The first two central moments of this mixture are given in 9 and will be used later to summarize our numerical results.
In order to explore the compression efficiency of both methods, we generated samples from the mixture defined above, varying its parameters. From now on, when we mention Beta distribution we will mean the transformed version defined above.
From now on we will apply Equations 5 and 7, to determine the compression efficiency of SM and VLB methods for random matrices generated as describe above.
With w = 0, a single Beta distribution is used. In Figure 1, we show some distributions of bit-lengths for some combinations of α 1 and β 1 . From the figure it can be seen that a large variety of unimodal distributions can be generated in the interval [1,64].
As we are sampling from a large set distributions of bit-length, represented by the mixture of betas presented above, in order to make our results more general, we will base our analysis on the expected bit-length of a sample, since the efficiency of both methods depends on it. So, from Equations 5 and 7, the expected efficiencies become: where k, in (11), is set to 7 (the bit-length required to represent the largest possible bit-length: 64). In (10), k is the bit-length of the greatest element, or in the worst case, 64. We will use the difference D = E(η 1 ) − E(η 2 ) to compare the efficiency of the two methods. Thus a positive D will favor SM method while a negative D favors VLB method.
The expected compression efficiency in the following numeric experiments, will be calculated from 3 matrices of dimension 10000, generated as described, and presented in tables and figures below.
In Figure 2, we can see the distribution of efficiencies and their difference for a sample generated from a single Beta distribution of bit-lengths. Note that both methods can achieve efficiencies greater than 80% for matrices with very small numbers. Also note that the VLB method is more efficient in the majority of cases. Now let w = 0.5, i.e., matrices will have elements with bit-lengths comming from a mixture of beta distributions, B 1 ∼ Beta(α 1 , β 1 ) and B 2 ∼ Beta(α 2 , β 2 ). The expected value for this mixture is shown in Equation 12.
Bit number For bit-lengths coming from a mixture (w > 0), let the expected efficiencies for the SM and VLB methods be as given by Equations 13 and 14. So now, instead of having the efficiency be a function of greatest bit-length in the sample (denoted as k in 5 and 7), it will be a function of max{E(B 1 ), E(B 2 )}.
As before, we generate 3 matrices of dimension 10, 000 for each parameterization, calculate the average efficiencies (Equations 13 and 14) and their diference D.
Before moving on to efficiency results and analyses, let's first inspect samples from the mixture of transformed Beta distributions. Figures 3 and 4, show a few parameterizations and their resulting sample distributions. It is important to note that from the mixture we can now generate bimodal distributions as well as the unimodal types tested before. Since we are making statements about efficiency as a function of the expected bit-length, it is important to verify if these statements hold for bimodal distributions as well.
After sampling uniformly ([1, 5, 9, . . . , 64], n = 65, 536) the bit-length space and comparing efficiencies, we summarized the results on Table 3. In it we see how many parameterizations (from our sample) favor  It can be seen that for most combination of α and β, D < 0, meaning the second method is more efficent to compress a sample of numbers with bit-lengths coming from a Beta(α, β) distribution. However, there is a small region in parameter space, which is shown in white on (d), where the SM method is more efficient. This region corresponds to the dots in red in (a), where the average bit-length is higher. In panels (b) and (c), we can see the efficiencies of SM and VLB methods, respectively. each method. We can also look at the distribution of efficiencies on our samples for each method ( Figure  5), which clearly demonstrate the greater expected efficiency of method VLB ( Figure 5(b)).
As we have shown, the VLB method is more effective compressing most integer datasets up to 64 bits in size. This is due to its ability to exploit the variance in the data set and reduce the waste of bits in the representation of some numbers. In specific cases where the variance in the data null or too small, method I will be more efficient. As a matter of fact, for matrices where all elements have the same bit-length, SM method will always be better, regardless of bit-length (Figures 6(a) and 6(b)), The only exception if for bit-length 64 where neither method is able to compress the data.

Calculating Efficiencies
To determine the best compression method to apply, it's necessary to inspect the distribution of bitlengths of matrix elements. When matrix elements are small or have nearly-constant bit-length, the SM Method is best, otherwise, the VLB method should be chosen.
As an example, let M r×c be a integer matrix such that the half of its elements have bit-length 1 and  As the greatest bit-length is 64, then k = 7. Compression efficiency η 2 can be calculated using Equation 7. After plugging in our numbers, we obtain a compression of 38.29%.  The efficiency of the VLB method is influenced by the relative size of the bit-length groups. In this first example we considered only two groups, each comprised of half the matrix elements. Let's now vary the relative frequency of the groups, fi rc , while sticking to two groups. Let's also assume that fi rc is a good approximation to the probability of a given bit-length in a matrix, which we will denote by p i .
With this definition we can rewrite the Equation 7, which becomes 15. In Equation 15, the fi rc is replaced by p i , representing the probability of elements from group i in matrix M. with With the Equation 15 can analyze the influence of bit-length probability in compression efficiency. In this example, p 1 and p 2 represent the probability of elements of bit-lengths 1 and 64, respectively. Thus, efficiency is defined in Equation 17.   . Efficiency histograms of the SM and VLB methods. Note that the VLB method has a greater average efficiency than SM method .
Now, we can determine which probabilities give us the best and worst compression levels. When η 2 = 1, then the efficiency is maximal and if η 2 = 0, a efficiency is minimal. To calculate the values of p 1 and p 2 for both extreme values of η 2 , we must solve the linear systems shown in Equations 18 and 19. The first equation on both systems come from the law of total probability. The second comes from 17 after setting η 2 to 1 and 0, respectively.
Solving the system above, we find that when p 1 = 0.9047 and p 2 = 0.0953, efficiency is maximal, and in this particular case is equal to 87.5%.
Thus, when p 1 = 0.1111 and p 2 = 0.8889 the efficiency is minimal for the VLB method. For other combinations see Table 3. Looking at this table, one can see two negative efficiencies, when (p 1 ,p 2 ) assume the values (0,1) and (0.1,0.9). This correspond th cases when the method increases the memory requirements instead of decreasing it.
So far, we have examined only two groups (hence two probabilities) of bit-length for the sake of simplicity. Before we generalize to probability distributions let's take a quick look at the efficiencies for more groups, with uniform probability:     When the distribution of the group probabilities is uniform, i.e., the groups have approximately the same size, efficiency is basically the same, regardless of the number of groups. Now we can leverage the notion of bit-length probabilities, and study efficiency when bit-lengths follow some commonly used discrete probability distributions: Discrete Uniform, Binomial and Poisson. For all the experiments, we assume k = 7, that is, the maximum possible bit-length is 64 bits. Thus, efficiency obtained will not be the best possible, since for that we would need assume small values of k (Equation 15).
Theoretical Efficiency: Let the random variable B ∼ U (a = 1, b = 64) represent the bit-length of the elements of matrix M . Then Applying this result to the expected compression efficiency of VLB method (Equation 15), we have assuming all bit-lengths are possible, i.e., a = 1 and b = 64, and hence k = 7, we can calculate η 2 : This result agrees with the numerical estimates presented in Table 4.
Numerical Estimates: To calculate the VLB efficiency, we generated a matrices with 100 (M 10×10 ), 10,000 (M 100×100 ) and 1,000,000 (M 1,000×1,000 ) elements with 1, 8, 16, 32 and 64 number of bitss. The average efficiency (Table 4) is calculated from a 1,000 replicates of each matrix size. As expected the compression effiency gets better with lower expected bit-length.

Binomial Distribution
For the binomial distribution, we will use Bin(n, p), with the number of trials n representing the greatest possible bit-length in the matrix, and np giving us the expected bit-length.
Theoretical Efficiency: Let bit-length (B) be a random variable with Binomial distribution, B ∼ B(n = 64, p = 0.5), E(b i ) = i b i × p(b i ) = n × p and the eficiency becomes (with k = 7): Which again agrees with estimates in Table 5.
Numerical Estimates: For these experiments, the parameter n represents the maximum bit-length of matrix elements and takes values in {1, 8, 16, 32, 64}. In this case, we evaluate the efficiency as a function of the parameter n, and matrix size. Even though efficiency does not depend on matrix size, we tried different sizes to test the stability of the compression algorithm. Results are shown in Table 5. As expected, smaller bit-lengths lead to higher compression efficiencies.

Poisson Distribution
With bit-length derived from a Poisson(λ), the parameter λ corresponds to the expected bit-length. For the purpose of this analysis this Poisson distribution is truncated at 64.
Theoretical Efficiency: Let bit-length B ∼ P oisson(λ = 32). In this case, E(b i ) = λ, with k = 7, the efficiency becomes: This result is in accordance to Table 6.
Numerical Estimates: The results for this simulation can be seen in 6. Note that increasing the number of bits to represent numbers increases, there is a loss of efficiency in the compression process. In this case we did not simulate for λ = 64 since a large portion of the samples would fall above the maximum bit-length we are considering for this analysis. These results show that a good compression is guaranteed when bit-lengths are distributed according to the tested distributions regardless of sample size.

Conclusion
In this paper, we have focused in the compression of matrix data, since this is one of the most important application the authors foresee. However, the compression methodology presented can be applied to any numerical data structure, with gains to performance and memory footprint[citar tese Crysttian e possveis artigos derivados].
Further discussions about doing computation with such compressed data-structures will be the subject of another manuscript (in preparation) in which we will present details about the implementation of the compression algorithm, and benchmarks on classical linear algebra tasks such as those in Linpack [ref].
For the compression calculations presented in this paper we limited bit-lenght of integers to 64 bits. However the compression would work in the same way as discussed for computer architectures with larger word sizes.
Representation of floating point numbers is also possible within the proposed compression framework, but at the expense of precision in their representation. Although this may sound like a limitation, when we take into consideration that most experimental data have fewer "significant" digits than the maximal precision available in modern computers, fairly good compression may still be achievable for floats.