METHOD AND SYSTEM FOR DATA COMPRESSION

Technical Field

The present invention relates to compression of data for storing in a node and reducing data traffic between two nodes comprised in a data communications network.

Background

A backbone network is a part of computer network infrastructure that interconnects various pieces of network, providing a path for the exchange of data between different Local Area Networks, LANs, or sub-networks, which may be wired or wireless. A backbone network may tie together networks within a limited area or over a wide area. Normally, the backbone's capacity is greater than those of the networks connected to it. The capacity of a backbone network is determined by the technology on which it is based and the capacity of the transmission equipment installed on the network.

The Internet is a conglomeration of multiple, redundant backbone networks, each owned by a separate party. It is typically a fiber optic trunk line consisting of many fiber optic cables bundled together to increase the capacity.

Even so, limited capacity in the network backbone is increasingly becoming a problem, especially in parts of the world where development or rollout of backbone technology is lagging, due to for instance infrastructural or topological challenges, or lack of financial means. Limited backbone capacity e.g. may create a bottleneck in the rollout of high-bandwidth services and in the upgrading of cellular networks to provide value-added services.

Another problem is related to limited storage space available on a computer hard drive. Even the largest data storage has its limitations.

In order to send data from one computer to another over a network, such as the Internet, the nodes comprised in the network must be able to communicate. This is enabled through a set of rules that regulate how the communication should be performed. One example is how the TCP/IP protocols provide such rules for the Internet.

Below follows an example of the present art applied in a Wide Area Network, WAN. A first user is connected via a first computer to a first Local Area Network, LAN. The first LAN is interconnected with a second LAN via the WAN. The second user is connected to the second LAN via a second computer. If a first user wants to send a data file to the second user, the first user's computer retrieves the data file from some local storage, transforms it into streamable data destined for the second computer, labeled with an address. The data stream is then sent out on the first LAN. When the data stream reaches the first WAN router, in the backbone network, the first WAN router performs a routing procedure in order to find out how to send the data stream on its way to the intended destination. Ideally, the WAN Router should select the fastest and most efficient route through the WAN. When the routing procedure has been performed, the data stream will have received additional addressing instructions/labels, most likely including the address to an intermittent router in the path to the second WAN router.

When the data stream has reached the second WAN router, the data stream is routed into and through the second Local Area Network until it reaches the second computer, the destination computer. At the destination, the data stream is being converted to the format of the original data file using the same protocol that it was initially fragmented with, upon which it can be presented to the second user, as the first user intended.

The known compression methods usually operate on the frames, compressing addresses and the like, but usually leave the payload intact, since the data representation must appear at the destination in its original content and sequence in order for it to be presented to the second user as intended.

It would be advantageous to be able to provide a solution to the limited transmission capacity in the backbone network, and further, it would be advantageous to provide a solution to the problem of limited storage space on hard drives of computers, such as e.g. user terminals or network routers or servers that are part of the backbone network, or a sub network connected to the backbone network.

Summary

It is the object of the present invention to obviate at least some of the above advantages and provide improved methods, apparatuses and computer media products avoiding the above mentioned drawbacks.

A first aspect of the invention is a method for compression of data. The compression of data is performed within a common context C providing a mapping of each index ik of a sequence of indexes to an index value Vk. The method of the first aspect comprises decomposing a data set D into a sequence of chunks d, wherein each chunk d is associated with a bit pattern p and an index i unique within the sequence. The method of the first aspect further comprises creating, for a certain bit pattern px, a value sum Sx of all index values mapped to each index of every chunk associated with the bit pattern p _x , wherein the value sum Sx is a component of a compressed representation of the data set D.

Each chunk d is of a predetermined bit length I. According to the method of the first aspect, the creating step is repeated for each bit pattern p of a set of bit patterns. The set of bit patterns may either comprise all bit patterns that may potentially occur in a chunk of bit length I. Alternatively, the set of bit patterns may comprise only the bit patterns actually featured in the sequence of chunks.

The method of the first aspect may further comprise reducing a value sum by using a table of numbers and pre-defined calculations such that every combination of X - Y = Z is unique, wherein:

X is a value sum

Y is a randomly chosen number that is unique for the combination, and

Z is a number key,

by using the steps of subtracting a corresponding value Y from an initial value sum X and repeating that step until a pre-defined reduction has been achieved.

The method of the first aspect may further comprise a step of compiling a list of value sums comprising each created value sum.

The method of the first aspect may be performed in a first network server and may comprise the further step sending the value sum Sxto a second network server.

A second aspect of the invention is a method interrelated to the method of the first aspect. The method of the second aspect is a method for decompression within a common context C providing mapping of each index ik of a sequence of indexes to an index value Vk. The method of the second aspect comprises the steps

retrieving a value sum Sx, associated with a certain bit pattern p _x ;

selecting a set of indexes bx, such that the sum of all index values mapped to indexes comprised in the selected set of indexes bx equals the retrieved index value sum Sx; and

recomposing a sequence of chunks such that each chunk associated with a selected index of the set of indexes bx is further associated with the unique bit pattern.

The method of the second aspect may further comprise enlarging a reduced value sum by using using a table of numbers and pre-defined calculations such that every combination of X - Y = Z is unique, wherein:

X is a value sum

Y is a randomly chosen number that is unique for the combination, and

Z is a number key,

by using the steps of identifying a number Z by using the last three digits of a value sum X, then identifying a corresponding value Y by using the table of numbers and pre-defined calculations, and adding the value Y to the initial value sum X, and repeating this process until the value sum X is enlarged to the same value it had before it was reduced. The method of the second aspect may be performed in a second network server, and may comprise the further step receiving the value sum Sxfrom a first network server.

The retrieving, selecting and recomposing steps of the second aspect may be repeated for each value sum of a list of value sums.

The selecting step of the second aspect may further comprise selecting an index if its associated index value is smaller than a current value difference dV. The selecting an index step may be repeated for indexes in a bottom-to-top order.

According to the method of the second aspect, the current value difference dV may be equal to the difference between the retrieved index value sum Sx and a sum of each associated index value of each previously selected index.

In methods of the first and second aspects of the invention, the common context C provides mapping between an index i and an index value V, such that each index value Vk is larger than a sum of all index values mapped to a subset of consecutive indexes comprising the top index and the upper adjacent index Vk-i in the sequence of indexes.

Further, according to the first and second aspects of the invention, an initiation of the common context C comprises mapping indexes in increasing top-to bottom order. The common context C comprises a predefined listing order of value sums, such that the position of each value sum Sx in the list indicates the associated bit pattern p _x .

A third aspect of the invention is a network server adapted to perform the method steps of the first aspect of the invention.

A fourth aspect of the invention is an interrelated network server adapted to perform the method steps of the second aspect of the invention.

A fifth aspect of the invention is a computer program comprising program instructions for causing a computer to perform the process of the first or second aspects of the invention when said product is run on a computer. The computer program of the fifth aspect of the invention may be embodied on a record medium, stored in a computer memory, embodied in a read-only memory, or carried on an electrical carrier signal.

A sixth aspect of the invention is a computer program product comprising a computer readable medium, having thereon: computer program code means, when said program is loaded, to make the computer execute the process of the first or second aspect of the invention.

Brief description of the drawings

Embodiments of the present invention will be described in detail below with reference to the accompanying drawings, in which Figure 1 is a schematic view of a communications system in which methods according to the present invention may be performed.

Figures 2, 3 and 4 illustrate certain properties of data upon which methods according to the present invention may operate.

Figure 5 illustrates the concept of index bins according to features of the present inventions.

Figure 6 is a flow-chart illustrating methods according to the present invention.

Detailed description

The solution according to the present invention is an interrelated set of methods for data compression and decompression. In exemplary embodiments of the method according to the present invention, the data compression and decompression is performed in a Network Interface layer in a TCP/IP stack.

The compression and decompression methods according to the present invention may be performed in a single node, e.g. in order to compress data locally for reducing storing needs, or for compressing data to be sent from a first node to a second node. Methods according to the present invention may be implemented in an exemplary communication system 10 as illustrated by figure 1 . The exemplary communications system 10 comprises a wide area network 20, WAN, alternatively referred to as a backbone network 20, or backbone 20. Further comprised in the communications system 10, and interconnected with the backbone 20 through gateways (not shown in the figure), is a first local area network 30, LAN, and a second LAN 40. The first and second LANs 30, 40, may communicate via the backbone 20 to which they are both connected.

A communications system 10 according to embodiments of the present invention relies on a common context C.

The context C is defined by a set of parameters comprising an index table. As a measure to initiate a system for compression, such an index table is set up.

In an exemplary embodiment of the present invention, an index table is set up as shown in the exemplary Table 1 below. Table 1 features 16 rows indexed from 0 to 15 in a first column. Indexes of the first column is mapped to, and thereby associated with, a dimensionless value, an index value Vi, in a second column.

Index, i Index value, Vi

0 2

1 4

2 8 4 32

5 64

6 128

7 256

8 512

9 1024

10 2048

11 4096

12 8192

13 16384

14 32768

15 65536

Table 1.

The significant property of the indexes i is that they are ordinal numbers denoting relative position in a sequence with two extreme ends, where one extreme end is defined as the top index and the other extreme end is defined as the bottom index.

The significant property of the index values is that the magnitude of each index value Vk is larger than the sum of upper index values, e.g. all index values mapped to indexes in the top-most part of the table immediately above of Vk. The difference, or offset Δ, between the sum of previous index values and a current index value is constant.

\/ο≡Δ , Equation 1

Vk = Δ +∑ ^k _{n= 1} Vn-1 Equation 2

In the present example, the offset Δ equals 1.

In the example in table 1 , the top index is 0. In other embodiments, the top index could be set to 1 or -1 or some other number, positive or negative. Further, though the top-to-bottom progression according to the above example moves from smaller indexes to larger indexes, in other embodiments, the top-to-bottom progression may be from larger to smaller indexes.

The properties of the indexing scheme, such as top and bottom indexes, direction of progression etc. may also be part of the common context C.

The table can be setup in various ways, as long as it is present and accessible in the common context C during performing the compression and decompression. If the compression and decompression is performed in different nodes, two identical tables should be initiated in the respective nodes. The table can be created in one place and then distributed two other nodes after creation, or it can be created locally in the different nodes, as long as the resulting index tables are identical. We will now continue to describe a compression method according to one

embodiment of the present invention, in relation to an exemplary communications system 10 comprising two nodes 50, 60 in a backbone network 20.

The two nodes are network servers in the backbone 20, and have been initiated such that they share a common context C, comprising the mapping table as described above.

The first node 50 may receive an amount of data in the form of a data stream from some other node in the communication network. For instance data may have been sent from a laptop 70 in the LAN 30. Alternatively, data may be retrieved from an internal storage, and the data is then decomposed such that further processing can be made.

With reference to figure 2, the first node 50 retrieves a predefined amount of data representing a data stream D of a bit length L. The data stream D will now be decomposed, to enable parsing and further processing of the data.

As illustrated in figure 2, the data stream D is partitioned, as indicated by the dotted lines, into a sequence of smaller data chunks d of a predetermined bit length I. Each data chunk is associated with an index that is unique to the sequence, e.g. it is indexed according to the index scheme of the index table, e.g. di. In the present example, as the index table features 16 indexes, the predetermined bit length is 4 bits.

In the general case where I is the bit length and N is the number of indexes, the following applies:

I = N , Equation 3

D= N * I Equation 4

Each chunk d features, and is therefore inherently associated to, a certain bit pattern p, as exemplified in figure 3. In the present example with a bit length l=4, a chunk may feature any one of 16 bit patterns po - pis, as exemplified in Figure 4, where the white areas could represent "zeros" and the black areas the complementary "ones". In this example, the bit patterns are direct representations of their reference numbers x in a binary representation. Any coding scheme could be used to link bit patterns p _x to reference numbers x. The scheme illustrated in Figure 4 is according to exemplary embodiments.

In a next step, a value sum Sx is created for each bit pattern px. Each created value sum Sx is a component of a compressed representation of the data set D. In order to create each value sum Sx the chunks comprised in the data stream D is parsed for recognition of bit patterns. For each unique bit pattern p _x , that the parser comes across during the parsing process, an index bin bx, will be created. The elements of the index bin bx comprise, and are limited to, the indexes of all the chunks d originating from the data stream D that features the bit pattern p _x .

In our example, as illustrated by figure 5, the pattern p4 is found at indexes 0, 1 and 7, and hence, the index bin b4 contains the indexes 0, 1 and 7. Further, the pattern ps is found at indexes 2 and 4, and therefore, after parsing, an index bin bs containing the indexes 2 and 4 will have been created.

In certain embodiments of the present invention, index bins for patterns that are not featured by any of the chunks in the data stream D are not created.

The predefined index table will now be used to calculate an index value sum Sxfor each created index bin bx. For each index i, comprised in an index bin bx, the corresponding index value Vi will be retrieved from the index table. All the retrieved index values Vi are then added in an index value sum Sx.

For example, the index value sum SA resulting from the index bin D4 = [0, 1 , 7] would be calculated as follows:

S4 = Vo + Vi + V7 = 1 + 2 + 128 = 131

In embodiments where un-featured patterns are not represented by an index bin, its respective index value sum S may be set to 0.

In certain embodiments, the step of creating a bin of indexes may be omitted, and instead, for each found index, its associated index value Vi is retrieved from the index table, and added to previously retrieved index values, such that the index value sum Sx is eventually achieved, in a piecemeal manner.

In a subsequent step, a list of index value sums is compiled, wherein the comprised index value sums are listed in a predefined listing order, such that the position in the list indicates the associated bit pattern px. This predefined listing order of index value sums can also be considered as part of the common context.

The list of index value sums may now be transmitted from the first node 50 to the second node 60. In alternative embodiments, where e.g. the compression- decompression methods are performed for the purpose of reducing required storage space in a single server, the list may now be stored in a local storage in the single server.

In order for a receiving node 60 to decompress a received list of index value sums, the index table that was used to create the received list must be present. Regardless of whether the decompression is performed in the same node that performed the compression, or in a second node 60, the decompression is performed in a similar fashion.

For each index value sum Sx in the list of index value sums received, its component indexes, i.e. the contents of a corresponding index bin bx, is retrieved as follows.

The underpinning principle of the decompressing process is to compare a current value difference dV to index values in an iterative mode, and to select an index ik if its corresponding index value Vk is smaller than the current value difference dV. The current value difference dV is defined as the difference between a certain index value sum Sx and a sum of the index values associated with already selected indexes. Each time an index is selected, its associated index value is subtracted from the previously used current value sum to create a next current value sum.

To continue with the above example where S4 = 131 , initially no indexes are selected, and therefore, the initial current value difference dV=131 -0=131.

As a next step we want to search the index table for the largest index value that is smaller than the current value difference. In some embodiments, each index value in the table is compared to the current value difference dV, starting from the bottom of the table, i.e. where the largest-magnitude index value, the bottom index, is found. In other embodiments, initially the largest index value that is smaller than the current value difference is found without prior comparison with the largest index value of the list.

In certain embodiments, this is accomplished through comparison of intervals between index values rather than index values per se. In order to find the correct interval, comparison may be performed on an exponential factor of the index value or interval of index values. This improves the processing efficiency.

In our example, the largest index value of the table that is smaller than the current value difference, i.e. 131 , is V7 = 128, which corresponds to i=7. Therefore i=7 is selected as one component of the recreated index vector b4.

The next current value difference is 131 - 128 = 3. According to the table, the largest index value that is smaller than 3, is Vi = 2. Hence, i=1 is selected, and added to the index bin b4.

The next current value difference is 3 - 2 = 1 . According to the table, the largest index value that is smaller than 2 is Vo = 1 , and hence i=0 is selected as a component of the index bin b4. As 1-1 =0, the next current value difference equals zero. As no index value in the index table is smaller than the current value difference, it can be deducted that all components of the index vector has been found and selected. The complete index bin b4 = [0, 1 , 7] can now be recreated. The above procedure is repeated at least for each index value sum Sx≠ 0 in the list of index value sums.

As the recreated index bins specify the bit pattern of each chunk comprised in the data stream D, the sequence of chunks of the data stream D can now be

recomposed exactly as it was prior to partitioning in the first node.

After index sums have been created, their sizes have to be reduced by the sender and then enlarged again to the original index sum by the recipient.

In order to reduce an index sum, subtraction with a pre-defined table of numbers with p re-determined calculations is used instead of division, since division eventually leads to uneven numbers with decimals. An advantage with using pre-defined calculations is that the numbers can be controlled in such a way that no uneven numbers are used.

In order for this reduction to work, identical tables with numbers and calculations must be installed at both the sender and the recipient.

Through a unique combination, the result of a subtraction constitutes a key that can be identified in the table. It is through this key that the recipient can determine which other numbers that are part of the addition that is performed to enlarge the sum again. This means that no dynamic calculations have to be performed, instead the pre-defined table of numbers is used to know which numbers that are to be used.

The sender subtracts the index sum by using the table of numbers and the recipient adds the index sum to the original value.

The combination of X - Y = Z has to be unique for every calculation in the table, wherein:

X = The index value sum (or last digits of it)

Y = Randomly chosen number that is unique for the combination (or the last digits of it)

Z = Key (or the last digits of it)

In order for the difference between X, Y and Z to not be too large, the total length of Z can be set to for instance three digits, no matter the length L of the whole number.

This means that the result of the last three digits of a number will be in the range 000 - 999. X will then be in the range of 000 - 1998, since Z is within the range of 999 ^* 2 = 1998.

The generation of the table of numbers is based on the number X which starts with 000 and ends with 1998. Y can be bigger or smaller to give more or less

combinations with calculations. When X has been chosen, the number Y is chosen randomly with respect to X. This is done in order to create the number Z, which is located in a range that is close to X/2.

For example:

If X = 1456, a Y will be chosen that is close to 1456 / 2 = 728.

Equation: X - Y = Z

X = 1456

Y = 712

Z = 744

Calculation: 1456 - 712 = 744

By using an existing programming language the table of numbers can be created with help of a program library that randomly generates the numbers X and Y. The only criteria that must be fulfilled is that every combination X - Y = Z is unique.

Below is an example of how these calculations can be performed:

In order for the sender to perform a subtraction, the process is started by dividing the index sum X with 2.

Example:

1642408 / 2 = 821204

The next step is to identify the last digits of X that are to be used, in order to find that combination in the table of numbers.

Example:

X = 1642408

2408 > 1998

Since 2408 is larger than 1998, which is the range for X, the last three digits are the significant ones, i.e. 408 in this example.

When the significant digits have been found we determine Y and replace the last three digits of X / 2.

Example:

1642408 / 2 = 821204

1642408 - 821188 = 821220 The new index value sum is now 821220. The steps are then repeated: 821220 / 2 = 410610

821220 - 410598 = 410622

610622 * 2 = 205311

410622 - 205300 = 205322

After performing these three subtractions, the number 1642408 has been reduced to 205322. In order for the recipient to know how many times to perform addition, the number of subtractions performed must be specified in the data string that is sent.

Example:

3d 205322, where d is a separator denoting the separation between the number of additions to perform (3) and the number to start the calculation with (205322).

In this example, the recipient will know to use addition three times and to start with the value 205322.

The first step for the recipient is to identify the key Z, which is the result of the calculation X - Y.

Example:

205322

In the table, the calculation for 322 can be found and we can then enter Y into the equation by replacing the last three digits.

205322 + 205300 = 410622

410622 + 410598 = 821220

821220 + 821188 = 1642408

This means that the index value sum sent by the sender is 1642408.

Example of a table of numbers:

X Y z

408 188 220

622 300 322 1220 598 622 Before the compressed index sum is sent to the recipient, a control calculation is performed in exactly the same way the recipient will perform the addition. If the results would differ, the subtraction is iterated another time in order to compensate for the calculation error. In this case, the subtraction for the error calculation is attached in the data string. The recipient would then add the error calculation and then the addition for the index sum. These two calculations are then added together to the correct index value sum.

In some embodiments of the invention a value sum does not have to be indexed but can instead be directly translated into a numeric value which can then be reduced according to the present disclosure.

For example:

If we take a bit stream that looks like this: 0100 1001 0100 0010, it can be directly translated into its corresponding numeric value 4942.

The present methods are not limited to compressing data streams of bit length L. Larger bit streams may be divided into a multiple of bit streams D of bit length L. Each bit stream D of the multiple of data streams is then processed according to the above. This is an advantage as it enables e.g. parallel processing of multiple data streams D. The methods of aspects of the invention may be performed in a network server adapted for serving and routing in a backbone network. Such a network server comprises processing and storing means, through which specific functions necessary for aspects of the invention may be implemented. These functions include but are not limited to a decomposing function, a partitioning function, a parsing function, a comparing and computing function, a selecting function, a bin creation and managing function, and a recreation function.