Data compression

FIELD: physics; computer engineering.

SUBSTANCE: invention relates to data compression. A network system is made with possibility of setting up data compression and comprises a network, a client and a server which provides the client with a terminal service. The server can compress data and has at least one look-aside buffer. One or more parametres of the compression procedure can be set up in accordance with feedback information which indicates availability of resources for transferring data in the said look-aside buffer of compressed data over the network from the terminal service to the client, and obtained based on amount of time spent on transferring all data from the said look-aside buffer. Methods describe operation of the said system.

EFFECT: wider functional capabilities.

45 cl, 9 dwg

 

The technical field to which the invention relates

The present invention relates generally to the field of data compression and, in particular, to a system, server, method and computer-readable media for data compression.

Prior art

Users have access to ever-increasing amounts of data more and more in a variety of ways. For example, a user may access Web site and take the broadcasting of the concert, i.e. to use the services of a Web broadcast. In addition, the user can access games and other applications over the wireless network using a wireless phone. In order to provide these data to the user data may be transmitted from the server to the client in a streaming mode with the aim of presenting to the client. Further, the user can interact with the presented data, for example, watching a movie, listening to a song, etc.

Streaming provides the user with increased functionality, so the user can quickly receive the data. If it were not for streaming, then you would receive from the server the full amount of data before the client will, as a result, the user could experience delayed presentation of data on the client. Thanks to streaming data, for Erica, perceived by the user can be reduced. Streaming data can be used to represent data in real time.

When streaming data is transmitted from the server in a streaming or continuous mode, usually in the form of packets, for submission to the client upon receipt of the data, unlike data that cannot be presented until the client is not the entire file containing the data. Streaming transfer mode can be used for various types of data such as video data, audio data, multimedia data, and so the Stream of video data provides a sequence of "moving images"that are sent and visualizeus upon receipt of the images. Similarly, the audio data stream provides audio data, which is reproduced upon receipt of the audio data. The stream of multimedia data includes audio and video data.

The data stream can be compressed for efficient transmission of data flow from the server to the client over the network to enhance the usefulness of streaming data. For example, the network serves as a means of communication between the server and the client may have limited bandwidth. Limited bandwidth can limit the amount of data that can for one moment be transmitted from the server to the client,and therefore, the functionality provided by the client when streaming data over the network. For example, video data is transmitted in the streaming mode can be limited to a lower resolution due to the limited bandwidth compared to the resolution, which could take place in the case of a network with higher bandwidth. Therefore, a user wishing to receive streaming video data with a higher resolution, may be forced to spend money on a connection with a higher bandwidth. Due to compression of streaming data over networks with low bandwidth one moment can carry more data and, thus, to maximize the usefulness of streaming data.

However, when compressed streaming data, you can face additional difficulties in contrast to compression of the full set of data, such as block compression. For example, to immediately compress entire movie, the compression process can check all the data that forms the film to compress the data. The compression process can provide a representation of the total sequences, which are included in the data forming the film. However, the streaming data may be provided to represent the data in real-time. Therefore, the client can dispose of the exhaust gas is aniconism time analysis of streaming data while ensuring data representation in real-time. In addition, there may be a limited amount of data available for comparison at any given time, to ensure the views of General sequences.

Accordingly, there is a constant need for data compression.

The invention

Described data compression. In the illustrative implementation, the compression module is executed by the server to compress data for streaming to the client, for example, data sent in response to request remote access client data in the terminal services environment, etc. compression Module uses a history buffer that contains the data previously transmitted to the client in a streaming mode. During execution, the compression module compares the sequence of data to be streamed from one or more sequences in the history buffer for finding the matching sequence. To find the sequence in the history buffer is used, the lookup table having a set of cells, each of which is available in one of the aggregate indexes. Each cell indicates whether the corresponding index in the history buffer, and if so, optionally specifies one or more provisions of the relevant index in the history buffer. Therefore, the compression module may use the original sequence is in the data be streaming, as an index in the lookup table to find the matching index in the history buffer. Then the matching sequence in the data can be replaced with a view that describes the position and length of the matching sequence in the history buffer, to generate compressed data for streaming to the client.

In another implementation, the method includes receiving feedback, which indicates the availability of resources for transmission of data over the network from the terminal of the service provided by the server to the client, and configuring one or more parameters of the procedure of compression used to compress data in accordance with the feedback.

In another implementation, the method includes receiving the request at the server from the client for remote access to an application or file that is available through the server. Determine the availability of resources for data transmission in response to a request over the network. Based on certain thus the presence configure one or more parameters of the compression procedure used for data compression.

List of drawings

1 is a diagram of an illustrative implementation, which shows the environment in which you are streaming data from the server to the client over the network.

2 is a diagram of an illustrative implementation, where more detail is shown serv the R and the client, depicted in figure 1.

Figure 3 is a logical block diagram of the illustrative procedure in which the data to be streamed, configured for compression.

4 is a logical block diagram of the illustrative procedure in which the lookup table shown in figure 3, is configured for the inclusion of the references to the package, subject to streaming, is used to compress the packet.

5 is a logical block diagram of the procedure in an illustrative implementation, in which a compressed package, shown in figure 4, is recovering from compression on the client by running module recovery after compression.

6 is a diagram illustrative implementation in which a sliding window is used in the history buffer to enable data to be streamed.

7 is a logical block diagram of the procedure in an illustrative implementation, in which the compression of streaming data is additionally optimized.

Fig is a logical block diagram of the procedure in an illustrative implementation, in which the comparison of sequences is optimized to further improve data compression.

Figure 9 - diagram of the system in the illustrative implementation, in which the compression dynamically configured in accordance with feedback received from the system.

To identify similar structures and components in the considered example the x uses the same reference position.

Detailed description of the invention

Review

Described data compression. In the illustrative implementation, the compression module is executed by the server to compress data for streaming from the server to the client. The compression module uses a history buffer that contains the data previously transmitted to the client in a streaming mode. When performing the compression module compares the sequence of data to be streamed from one or more sequences in the history buffer for finding the matching sequence. To find the sequence in the history buffer, use the lookup table having a set of cells. Each of the cells is available in one of the aggregate indexes. Each cell indicates whether the corresponding index in the history buffer, and if so, optionally specifies one or more locations corresponding index in the history buffer. Therefore, the compression module may use the original sequence in the data stream, as an index in the lookup table to find the cell. Thus, the compression module can quickly find each position in the history buffer with the original sequence, without having to compare each sequence in the history buffer with each follow what eTelestia data be streaming.

If the corresponding cell with the matching index specifies a set of provisions, the comparison module may display the matching sequence, comparing the sequence at each position that have a matching index, sequence data, which include the original sequence. Then the matching sequence in the data can be presented through a presentation that describes the position and length of the matching sequence in the history buffer. Then, the compressed data can be transmitted to the client in a streaming mode. The client recovers data after compression using a history buffer that contains the data that was previously streamed from the server to the client. The client, performing the recovery module after compression, finds the matching sequence in the history buffer of the client, using the length and position specified in the view for data recovery. Thus, it provides a method of lossless data compression, which allows you to compress the data and restore them after lossless compression of data. For example, using this technique of data compression, you can compress and recover after compression video data without losing the data fragments, and, thus, to preserve the resolution of the s video.

Illustrative environment

Figure 1 shows a diagram of an illustrative implementation, which shows an environment 100 in which streaming data from the server 102 to the client 104 over the network 106. The client 104 may have a variety of configurations. For example, the client 104 may be configured as a device that is configured to communicate over the network 106, for example, a desktop computer, which is shown, mobile station, household appliance for entertainment, set-top box, cordless phone, etc. Under the client 104 can also understand the person and/or entity that/AI operates the client 104. In other words, the client 104 may describe a logical client that includes a user and/or machine. Although illustrated with one client 104, the network 106 can be connected with a possibility of connection of several clients. The network 106 is illustrated as the Internet and may also include various other network, for example, an intranet, a wired or wireless telephone network, etc.

The server 102 is configured to transmit the data stream over the network 106 to the client 104. The server 102 can provide a variety of streaming data for presentation on the client 104. In one implementation, the server 102 may provide a Web broadcast of the concert, which is streamed to the client PI view on the client 104, the user can watch and listen to Web broadcasting. In another implementation, the client 104 may receive data that includes a song, transmitted to the streaming server 102 for output to the client 104.

In another implementation, the server 102 may also provide terminal services for remote application execution. For example, the server 102 may include a set of applications 108(1),..., 108(n),..., 108(N), where "n" can be any application from 2 to "N". Each of the applications 108(1)-108(N) is executed on the server 102. The server 102 transmits streamed to the client 104 over the network 106 display information that is provided by the execution of applications 108(1)-108(N). For example, the display information may include an image on the display for a desktop computer provided by the operating system, and a window displaying the information related to the implementation of a text editor, and audio information provided by the operating system and/or a text editor.

The display information is transmitted to the streaming server 102, is rendered on the client 104 to monitor the user. The user can interact with the client 104 to provide inputs using the input device of the client 104, such as a mouse 108 and/or the keyboard 110. The inputs may correspond to present on-screen information, ka is, for example, a text input for a text editor that is provided with the use of the keyboard 110. The inputs are transmitted from the client 104 to the server 102 over the network 106. The inputs received at the server 102, may be used when executing a set of applications 108(1)-108(N). For example, a text editor can accept text inputs for inclusion in the document and to stream on-screen information to the client 104 to illustrate the document, which is included in the text. Through the execution of applications 108(1)-108(N) to the server 102 and the transmission of streaming on-screen information to the client 104, the client 104 may be available functions, which, otherwise, could not be present on the client 104.

For example, the client 104 may be configured as a thin client, which has limited resources for data processing and/or memory. On the other hand, the server 102 may have great potential, for example, to have more resources of the data processing and/or memory than the client 104. Therefore, the server 102 may execute applications that may not be executed on the client 104 and/or slower to run on the client 104. The server 102 issues the results of executing one or more applications 108(1)-108(N) to the client 104, transmitting the screen information to the client 104, and receives inputs from the client 04 over the network 106. Thus, the functionality provided by the server 102, for example, processing resources of the data memory and the applications 108(1)-108(N) may be provided to the client 104, which, otherwise, would not have access to this functionality.

For communication between the server 102 and the client 104 over the network, the server 102 and the client 104 can implement respectively the remote desktop Protocol (RDP) 112, 114. RDP 112, 114 are designed to provide remote display and input through network connections for applications 108(1)-108(N) as described above. For example, the RDP can be used to allow individual virtual channels that carry the device information and view data from the server 102 to the client 104, and the encrypted inputs, which are transmitted from the client 104 to the server 102.

RDP 112, 114 can also provide a decrease in throughput due to the inclusion of modules 116, 118 of the compression and recovery after compression on the server 102 and the client 104, respectively. Module 116 compression may be performed on the server 102 through the implementation of the RDP 112 to compress data before it is streamed over the network 106. Similarly, the module 118 recovery after compression can be executed on the client 104 through the implementation of RDP 114 for recovery after the pressing of the data which were streamed over the network 106 to the server 102.

The modules 116 and 118 of the compression and recovery after compression when performing respectively compress and recover after compression data stream over the network 106. According to the above, the compression and recovery after compression of streaming data can cause special difficulties, in contrast to compression and recovery after compression the entire dataset, i.e. block compression. For example, data may be transmitted in streaming mode "in real time", so that the delays that occur when streaming data, can reduce the usefulness of the data. The modules 116, 118 of the compression and recovery after compression allow you to resolve particular difficulties streaming data and, thus, provide a stream of compressed data over the network 106, which are described in more detail with reference to figure 3-5.

Through the use of terminal services (TS, TS), the client 104 may access one or more applications 108(1)-108(N)installed on the server 102, to execute the application on the server 102 and to display a user interface (PI, UI) application on the client 104. Because applications 108(1)-108(N) are executed on the server 102, TC allows the client 104 to access resources on the corporate it infrastructure, regardless of whether the client has 04 the appropriate hardware and software for local execution resources on the client 104.

Although the client 104 described in the terminal services environment, in which a set of applications 108(1)-108(N) is executed on the server 102, the client 104 may also perform one or more of the aggregate of the application 120(1),..., 120(m),..., 120(M). For example, one of the applications 120(1)-120(M) can provide an interface that is used in conjunction with RDP 114 to present the data for viewing by a user and for receiving inputs from a user, for example, using the mouse 108 and/or the keyboard 110. In addition, although the modules 116, 118 of the compression and recovery after compression is illustrated as part of the relevant protocols RDP 112, 114, modules 116, 118 of the compression and recovery after compression can act as Autonomous software components that run for compression and recovery after compression of streaming data, respectively.

In addition, although the following part of the review describe the use of compression in the terminal services environment, the methods described here and compression recovery after compression can also be used in various other environments. For example, compression techniques can be used to compress the data used in the environment of remote access. Remote access describes the ability to access a computer or network from a remote location. For example, a remote office of the Corporation may require network access Corporation and use the improving access to included files and applications, for example, through the telephone network, the Internet, etc. the Server 102 can be configured as a remote access server with the appropriate software, designed to customer service requesting remote access. In one implementation, the remote access server includes a server firewall (firewall protection) for security and router to forward requests remote access to other parts of the network. The remote access server can also be used as part of a virtual private network (VPN VPN).

Figure 2 shows a diagram of an illustrative implementation 200, where more detail is shown, the server 102 and the client 104, depicted in figure 1. The server 102 includes a processor 202 and memory 204. It is shown that the RDP 112 and its corresponding module 116 compression are executed on the processor 202 and stored in memory 204. Similarly, the client 104 includes a processor 206 and a memory 208. It is shown that the RDP 114 and its corresponding module 118 compression are executed on the processor 206 and stored in memory 208.

The data to be streamed from the server 102 to the client 104, may be provided from various sources, for example, by performing one or more of the applications 108(1)-108(N)received from the device 210 of the input, e.g., camera, microphone, etc. Module 116 compression is executed on the processor 202 of the server 102 for SG is ment data for streaming to the client 104. Data can be streamed from the server 102 to the client 104 in the form of packets.

For example, the module 116 compression can receive data with the uncompressed sequence of a given length, and try to compress this sequence to a smaller (compressed) length, for example, having fewer bytes, bits, etc. Module 116 compression can compress data Papageno, replacing the sequence representation, stored using less memory resources, for example, fewer bytes than the replaced sequence.

If the module 116 compression is able to compress the sequence, the compressed data is transmitted to the terminal connection point RDP, ie RDP client 114 104. Module 118 recovery after compression is executed on the client 104 to recover from compression of the compressed data to restore the data. In the case when the module 116 compression is not able to compress the data, the data can be transmitted to the client 104 stream in uncompressed form, i.e. as a sequence of literals. Then the module 116 compression may be performed on the server 102 in an attempt to shrink the following sequence.

The main operation used for data compression, provides for the negotiation template sequences in the data to be compressed, with sequences that were streamed before. This fashion is 116 compression supports buffer 212 history contains the data that were previously streamed to the client 104. Module 116 compression, when executed, will agree on the sequence in the data stream, one or more sequences that are part of the data that has already been streamed to the client 104. The sequence in the data stream that match the sequence in the history buffer can then be represented using one or more views, which indicate the matching sequence in the buffer 212 history. Views can be smaller, i.e. use less memory resources than is used to store the actual sequence to be compressed, i.e. the matching sequence. This effectively reduces the amount of data included in the stream data.

To illustrate a basic example of the matching pattern using the buffer 212 history, assume that the buffer 212 history contains the following sequence:

12745639451491

Module 116 compression is executed on the processor 202 of the server 102 and receives the following sequence:

45974563945146

During execution module 116 compression finds the longest sequence in the history buffer, which coincides with the sequence data on the underlying compression, i.e. the matching sequence. In this case, the matching sequence, which appears in the history buffer, shown below in bold. The matching sequence has a length of ten bytes and starts with three bytes from the beginning of the buffer 212 history (starting from the left and continuing with zero).

45974563945146

Thus, the module 116 compression, when executed, may generate compressed data, representing the data to be streamed, as follows:

4 5 9 (match length of 10 bytes starting with 3 bytes from the beginning of the buffer) 6.

By specifying a matching sequence in the history buffer, the server 102 does not need to retransmit the sequence that have been streamed to the client 104. Thus, the module 116 compression compresses the data to be streaming, looking for repeating patterns in the data that should be streaming, and replacing repeating patterns, i.e. matching, a view that uses less memory resources and bandwidth during transmission over the network 106.

To recover after compression, the compressed data, the client 104 includes a module 118 recovery after compression and buffer 214 history. In the buffer 214 history of the client 104, as in the buffer 212 history of the server 102, the data is stored, transferred earlier in the thread the mode. Therefore, the module 118 recovery after compression, when executed on the client 104, may recover after compression data that has been streamed to the client 104 using buffer 214 history. Continuing the previous example, suppose the client 104 receives the compressed data, which are shown as follows:

4 5 9 (match length of 10 bytes starting with 3 bytes from the beginning of the buffer) 6.

On the basis of representations, included in the compressed data, the module 118 recovery after compression, when executed, can extract the compressed sequence from the buffer 214 history, which is shown in bold as follows:

45974563945146

Thus, the module 118 recovery after compression can recover after compression, the compressed string with a buffer 214 history.

The server 102 may also include a lookup table 216 to find matching sequences in the buffer 212 history. For example, the lookup table 216 may contain a collection of cells that are one of a set of indexes. Each cell describes each position in the buffer 212 history with the appropriate index. Thus, the module 116 compression, when executing on the server 102 may use a lookup table 216 to quickly determine the position of a specific sequence in the buffer 212 history is. Further consideration of the lookup table 216 and buffer 212 history is given with reference to figure 3-4.

The server 102 may also use coding techniques to further data compression for streaming, for example, Huffman coding, arithmetic coding, prefix coding and coding for Markov. For example, the data to be streamed, can include sequences that do not match the sequence in the history buffer. These sequences will be called a sequence of "literals". Using Huffman encoding, some or all of the sequence of literals in the data can be compressed for further data compression. For example, Huffman coding can begin with a table of frequency of occurrences, which refers to the frequency of each sequence of literals, which must be further compressed. The frequency table can be generated from the data itself and/or representative (representative) data. For example, the frequency sequence of literals can be obtained by processing packets previously transmitted in the streaming mode, and then used for each subsequent packet.

For example, each sequence of literals can be assigned a variable-length string that is unique is about is a specific sequence of literals, for example, as a unique prefix. Then variable-length strings are organized in a tree for encoding and decoding each(th) sequence of literals and views respectively. To encode a sequence of literals, the sequence of literals encode placed in the tree. The branches of the tree that are used to determine the position of a leaf (terminal node), which contains a sequence of literals that are used to encode the sequence of literals, i.e. provide a view of the sequence of literals. For example, each branch of the tree is used for Huffman encoding, you can mark the character of the output alphabet, for example, bits 0 and 1, so that the coding is a listing of the labels of the branches on the path from the tree root to the encoded sequence of literals. Decoding each view is a tree traversal from the root down through the branches to a leaf of the tree at the base of each subsequent value in the string variable length until it reaches a leaf of the tree, which contains a sequence of literals.

Although described coding Huffman sequences of literals, Huffman coding can be used for additional compression of various data. For example, with p the power table 218 Huffman can be encoded as a sequence of literals 222, and back pointers 224. The above sequence of literals include sequences that are not found in the buffer 212 history. Therefore, the sequence of literals 222 can be compressed using table 218 Huffman. The back pointer 224 describes the position of a given sequence in the buffer 212 history. For example, according to the sequence described above in the data, which coincides with the sequence in the buffer 212 history, i.e. the matching sequence can be described as "match length X bytes starting with the Y bits from the beginning of the buffer. The back pointer 224 describes the position of the matching sequence in the buffer 212 history, ie 7 bytes. Table 220 Huffman can be used to compress the length 226, i.e. X bytes, matching the sequence.

To recover after compression, the compressed data is transmitted in streaming mode from the server 102 to the client 104, the module 116 recovery after compression is executed on the client 104 using tables 228, 230 Huffman, which correspond respectively to tables 218, 220 Huffman server 102. For example, table 228 Huffman can be used for recovery after compression of sequences of literals 232 and reverse pointer 234 and table 230 Huffman can be used for recovery after compression length 226 matching is posledovatelnosti. Further consideration of the Huffman tables are given with reference to Fig.7.

The server 102 and the client 107 can also include appropriate tables 236, 238 of the most ancient use (NIDS, LRU). Each of the tables 236, 238 NIDS can be used to further encode reverse directions depending on whether the back pointer one of the "most recently used" reverse pointer. For example, table 236 NIDS can be used to represent NDI, respectively, for each of the last four reverse pointer. View NDI is used as an index for determining the position in the table 236 NIDS. Thus, it is possible to additionally compress repetitive reverse pointers. Additional examination of tables NDI below with reference to Fig.7.

Although described compression data stream from the server 102 to the client 104, the client 104 may also compress the data and send them streamed back to the server 102. In addition, although the following review describes the compression of data packets streamed from the server 102 to the client 104, for data compression, you can use a variety of data sets, for example, the sequence of bytes of the subpackage, multiple packages, etc. in Addition, although in the following the m considering the described sequence of bytes you can also consider other sequence data, such as bits.

Illustrative procedures

Figure 3 shows a logical block diagram illustrative of a procedure 300 in which the data to be streaming, configure compression. At step 302, data is added to the buffer 212 history. For example, the buffer 212 history may contain a collection of packages 304(1), 304(2), streamed, and/or ready to be streamed from the server 102 to the client 104, as shown in figure 2, over the network 106. In one embodiment, the packet 304(1), 304(2) may correspond to data that were previously processed by module 116 compression.

The server 102 receives a packet 304(3)to be streamed. Module 116 compression, when executing on the server 102 adds the packet 304(3) in the buffer 212 history, so the history buffer includes packages 304(1), 304(2), which were streamed, and the packet 304(3), transferable.

At step 306, the module 116 compression, when executing on the server 102, and updates the lookup table 216 reference to the added data, i.e. the packet 304(3). The lookup table 216 may include a set of index 308(k), where "k" can be any index from "1" to "K". Each index 308(k) is used for finding the corresponding one of the set of cells in the lookup table 216. Each ACAC which indicates if the aggregate index 308(k) in the buffer 212 history, and, if so, one or more of the provisions of the relevant index 308(k) in the buffer 212 history. For example, one set of cells can specify a set of provisions in the buffer 212 history that have corresponding index 308(k). Each set of provisions is shown as described with the corresponding one of the set of chains 310(k) hash.

For example, it is shown that the index 308(k) has the sequence "4 5". Corresponding cell index 308(k), i.e. the chain 310(k) hash lookup table 216, describes each position index 308(k) "4 5" in the buffer 212 history. For example, figure 3 shows that the package 304(1) has the following sequence:

01234567

Figure 3 shows that the package 304(2) has the following sequence:

89453130

Figure 3 shows that the packet 304(3)to be streamed to the client 104 has the following sequence:

45670824

Packages 304(1)-304(3) can be sequentially arranged in the history buffer so that was observed following sequence:

012345678945313045670824

Chain 310(k) hashing describes each position index 308(k) "4 5" in the buffer 212 history. Each position can be described in different ways. For example, provisions can be described as Polo is giving the first byte of the sequence when counting from the beginning of the buffer 212 history starting with the number zero. Chain 310(k) hashing describes the first position index 308(k) "4 5" 16 bytes from the beginning of the sequence in the buffer 212 history that shown in figure 3 by the dashed line running from the "16" in the chain 310(k) hashing to the beginning of the packet 304(3). Similarly, the chain 310(k) hashing describes the second position index 308(k) "4 5" ten bytes from the beginning of the sequence in the buffer 212 history that shown in figure 3 by the dashed line running from the "10" in the chain 310(k) hashing to the third byte of the packet 304(3). Further, the chain 310(k) hash contains the third and last position index 308(k) "4 5" 4 bytes in the buffer 212 history. Thus, the lookup table 216 contains the index 308(k), for example, "4 to 5"with the appropriate cell, which indicates the chain 310(k) hashing, which describes each position, for example, 4, 10, 16 index 308(k) in the buffer 212 history. Updating a lookup table 216, the module 116 compression may, when executed, to compress the data to be streamed, in a more efficient manner that will be described in more detail with reference to figure 4.

Although figure 3 shows that each index 308(k) has a corresponding one of the set of chains 310(k) hashing, there may be cases when the index 308(k) does not have a corresponding hash chain. For example, in some cases, the buffer 212 history may not contain the substance of the index. Therefore, the cell lookup table 216, which corresponds to this index may not contain the hash chain. In other words, the hash chain for this index has a value of zero, i.e. in the buffer 212 history there is no place, where is the corresponding index. In addition, although it is shown that each set of chains 310(k) hashing included in a lookup table 216, one or more chains 310(k) hashing can be ensured in different ways. For example, each cell in the lookup table 216 may contain a pointer to the appropriate hash chain, which has the configuration array that is separate from the lookup table 216.

Figure 4 shows a logical block diagram illustrative of a procedure 400, which is shown in figure 3 the lookup table 216 configured to include references to the packet 304(3)subject to streaming, is used to compress the packet 304(3). At step 402, the module 116 compression, when executed, sets the current pointer 404 to the data that has been added, i.e. the packet 304(3), in the buffer 212 history on the stage 302 in figure 3.

At step 406, the module 116 compression is performed on the server 102 to find the index in the lookup table 216, which coincides with the initial sequence at the current pointer 404. For example, the module 116 may use the original posledovatelno the , which consists of two bytes, for example, "4 5", at the current pointer 404 to find one aggregate index 308(k), which coincide with the original sequence. In this example, the index 308(k) "4 5" lookup table 216 coincides with the initial sequence "4 5" at the current pointer in the buffer 404 212 history. Index 308(k) has a corresponding cell in the lookup table 216, which indicates the chain 310(k) hashing, which describes each position of the index "4 5" 308(k) in the buffer 212 history. So the cell describes each position in the original sequence in the buffer 212 history.

If the corresponding cell is coincident index 308(k) specifies a set of provisions sequence at each position in the buffer 212 history that have a matching index 308(k) "4 5", compared to sequence data having the original sequence at the current pointer 404. For example, the initial sequence "4 5" at the current pointer 404, i.e. the position of the "16" in the buffer 212 history, and the sequence at position "10" in the buffer 212 history has a length of "2", i.e. only the first two bytes in the byte sequence at each position coincide with each other. According to the above, the provisions in the chain 310(k) hashing this example describes atsche the ohms from the beginning of the buffer 212 history starting with the number zero. The initial sequence at the current pointer 404 and the sequence in position "4" in the buffer 212 history have a length of "4". In other words, the four bytes in the byte sequence in position "4" to coincide with the four bytes in the sequence at position "4". Thus, the calculated length of the displayed matching sequence "4 5 6 7". To find the best matching sequence, each position in the chain 310(k) hashing can be compared with the sequence of data to be compressed, i.e. the packet 304(3)until the calculated maximum length and/or will not reach the threshold, which is described in more detail below with reference to Fig.7. In order to optimize the comparison, the next byte in the sequence, for example, the byte that follows the original sequence or index in the buffer 212 history, you can compare first because of the match is known that the first two bytes are the same. An additional consideration comparing on the basis of the next byte in the sequence described with reference to Fig.

At step 408 the matching sequence are using a view that is used to generate compressed data. For example, the matching sequence "4 5 6 7 in the packet 304(3) can be represented by the Yu view which describes the length of the matching sequence and the position of the matching sequence in the buffer 212 history. The view can be formatted as a tuple, i.e. an ordered set, such as {reverse pointer, length}. The back pointer can describe the relative position of the matching sequence as the offset in the buffer 212 history. For example, the back pointer can describe relative position as the offset between the absolute position of the matching sequence and the absolute position of the current pointer in the buffer 404 212 history. In this example, the absolute position of the matching sequence is the position 4 in the buffer 212 history and the absolute position of the current pointer 404 is "16". Therefore, the relative position of the matching sequence is 12 bytes from the current pointer 404. Length describes the length of the matching sequence, for example, "4". Thus, the packet 304(3) can be compressed, representing a matching sequence "4 5 6 7" using views "{12, 4}" for the formation of the compressed data, for example, the package 410. In another implementation, the position matching can provide absolute position of the matching sequence in the history buffer, for example, position 4.

Thus, the lookup table 216 about what has each position of each index 308(k) in the buffer 212 history. Therefore, when the module is executed 116 compression, each position in the original sequence can be found in the buffer 212 history, not "watching" every single bit or byte in the buffer 212 history for finding the matching sequence. Thus, the module 116 compression can effectively compress the data to be streamed.

Figure 5 shows a logical block diagram of a procedure 500 in an illustrative implementation, in which the compressed data shown in figure 4, is recovered after compression on the client 104, through execution module 128 recovery after compression. At step 502, the client 104 receives the compressed data, for example, the package 410, which was streamed to the client 104 to server 102, as shown in figure 4.

At step 504 module 128 recovery after compression, when executed, identifies the matching sequence in the buffer 214 history of the client 104. The buffer 214 history of the client 104, as a buffer 212 history server 102 may contain data that has been streamed from the server 102 to the client 104. Thus, the buffer 214 history of the client 104 coincides with the buffer 212 history of the server 102 to the formation of the compressed data, for example, the package 410. Therefore, the module 118 recovery after compression, when executed, can find a matching sequence in the buffer 214 history of the client 104 presents from the I, which describes the length and position of the matching sequence in the buffer 212 history server. Continuing the example from above, the matching sequence "4 5 6 7" found at position "12", which is a relative position, as described above.

At step 506 module 118 recovery after compression, when executed, replaces the representation of the matching sequence for data recovery. For example, the representation "{12, 4}" replace matching byte sequence "4 5 6 7" to bundle 508, which contains the sequence "45670824", coinciding with the sequence of packet 304(3), which was compressed at step 408 in figure 4. For example, the compressed data can be generated from data to be streamed through the formation of a new dataset, which includes representation instead of the matching sequence. Thus, as shown in this example, the client 104 can recover after compression data without using a lookup table 216. Therefore, the compressed data is transmitted in streaming mode, you can recover after compression on the client 104, even if the client 104 has limited hardware and/or software resources in comparison with the server 102.

In the described illustrative procedures 300, 400, respectively, with reference to figure 3, 4, search tablica had such a configuration, each of the aggregate index 308(k) contains two bytes. Therefore, the lookup table 216 may be provided 65536 corresponding cells that describe each two-byte sequence in the buffer 212 history. This allows you to use the original sequence directly in the lookup table 216. In other words, the initial sequence is not converted for use with the lookup table 216 to find the corresponding cell. Although there have been described the index 308(k), with two bytes, you can use various other lengths of the index, for example, three-byte sequence, Quad sequence, etc.

Figure 6 shows a diagram of an illustrative implementation 600, in which a sliding window is used in the buffer 212 history to enable data to be streamed. In the implementation described with reference to figure 3, the packet 304(3) was added to the buffer 212 history. Then a lookup table 216 has updated the instructions on the packet 304(3). However, the buffer 212 history may have limited memory capacity. Therefore, to enable the newly added data in the buffer 212 history used a sliding window.

For example, the buffer 212 history may contain a sequence 602 as a result of adding packet 304(3) in step 302 in figure 3. The buffer 212 history in this example can store m is Ximum 24 bytes. Therefore, to add a sequence 604 having eight bytes, the module is executed 116 compression for removal sequence 606, having eight bytes, from the beginning of the buffer 212 history and move the remaining sequence in the beginning of the buffer 212 history. Then a new sequence 604 is added to the end of the buffer 212 history. By moving and adding sequences, the buffer 212 history is a sequence 608 with 24 bytes, which contains the newly added sequence 604.

To update a lookup table 216 to reflect the sequence 608, each position in the chain 310(k) hash lookup table 216 may have to deduct the number that corresponds to the number of bytes in which each byte has been shifted in the buffer 212 history. For example, in this example, each byte has been shifted by eight bytes to reclaim space for new sequence 604. Therefore, each position is described by a set of chains 310(1)-310(K) hash is "8", subtrahend, to reflect the new provisions of the relevant index 308(k) in the buffer 212 history. To remove provisions from each of the chains 310(k) hashing, which is no longer included in the buffer 212 history, any position having a value less than zero is removed from the chain 310(k) hash.

7 and obrazana logical flowchart of a procedure 700 in an illustrative implementation, in which compression of streaming data is additionally optimized. In the previous procedures 300, 400, discussed with reference to Fig 3,4, the lookup table 216 had a configuration that makes it possible to describe each position in the buffer 212 history of the relevant index 308(k), in order to effectively determine the position of the original sequence in the buffer 212 history. Finding a matching sequence in the buffer 212 history may be further optimized to further improve the efficiency of data compression.

At step 702 a matching sequence is found, for example, using a lookup table and applying a threshold. You can apply different thresholds. For example, a comparison to find the matching can be performed on a predetermined number of locations in the history buffer to limit the amount of comparisons. By limiting the number of locations in the history buffer, which are compared with the data to be streamed, you can limit the size (i.e. number of bytes) of the regulation. For example, as described previously, the position of the matching sequence in the buffer 212 history can be described as the relative position between the beginning and the end of the matching sequence to the beginning or end of the current criminal code of the indicator, what can be described as reverse pointer. Therefore, by limiting the number of manufactured comparisons is large, the probability that the matching sequence is "closer" to the current pointer. Thus, the position will have a smaller value, for example, to use fewer bytes into force of this "proximity". In a different implementation, you can use the threshold to provisions that have values above a predetermined threshold, were not considered, which again may serve to limit the size of the position value. Thus, it is possible to use different thresholds, for example, a number of provisions that are subject to search, the size of the value that describes each position, size, value, which describes the length of each of the identified sequences, etc.

At step 704 decision is determining whether a reverse index, which describes the position of the matching sequence in the table the most ancient use (NIDS). Table NIDS can be used to store back pointers of the most long-standing use. If the back pointer to the matching sequence included in the table NDI, the view NDI corresponding reverse pointer in the table NIDS, is used to encode a reverse yasat the La for matching sequences. For example, table NIDS can have a depth of four to the table NDI kept the last four used reverse pointer. Each of the back-pointer in the NDI has a corresponding representation of the NDI, which is shown in table NIDS. Therefore, if the back pointer included in the table NIDS, then at step 706 the back pointer can be encoded via submission NIDS table NIDS. Thus, the compression module may address additional templates that can occur in data streaming, for additional data compression. For example, image data transmitted streamed from the server to the client may contain overlapping sequences that are repeated with similar shifts in the history buffer. Therefore, the matching sequence can be compressed using a view that includes the length and position of the matching sequence, and the position can be further compressed using view NIDS.

If the back pointer not included in the table NIDS, then at step 708 the back pointer can be encoded using table 228 Huffman, shown in figure 2. The Huffman coding can begin with a table of frequency, which indicates the frequency of each reverse pointer subject to additional SG the party. Each reverse pointer is assigned to the string variable length, which uniquely represents this reverse pointer. For example, each variable-length string can have a unique prefix. Then the rows can be arranged in a tree for encoding and decoding each callback pointer and presentation respectively. To encode reverse pointer backward pointer is placed in the tree. The branches of the tree that are used to determine the position of the sheet, which contains a back-pointer is used to encode a sequence of bytes, i.e. provide a view of the reverse pointer. For example, each branch of the tree is used for Huffman encoding, you can mark the character of the output alphabet, for example, bits 0 and 1, so that the coding is a listing of the labels of the branches on the path from the root of the tree to encode reverse pointer. Decoding each view is a tree traversal from the root down through the branches to a leaf of the tree at the base of each subsequent values in the string until it reaches the leaf of a tree, which contains a back-pointer.

At step 710 the length of the matching sequences also encode using a Huffman table. For example, the Huffman table shown in figure 2, you can use DL the encoding length of the matching sequence in the history buffer for additional data compression. The length can be encoded in the same way as described for the reverse pointer.

At step 712 the matching sequence are via submission with the configuration of the tuple, which contains a back pointer that describes the position of the matching sequence in the history buffer, and the length of the matching sequence. At step 714, apply a cost function to determine whether the view is more effective, for example, does it use less memory resources for storage and/or less bandwidth when streaming this match that sequence. For example, in some cases, the matching sequence can use fewer bytes than a view that describes the position and length of the matching sequence in the history buffer. Therefore, the cost function can be used to determine what is more effective representation or matching sequence, i.e. a sequence of literals in the data. You can apply various cost functions. For example, the cost function can use the product of the size of the return pointer and length of the matching sequence.

If at step 716 decision turns out that the representation is more efficient, then at step 718, the compressed data is formed by the predstavleniya matching using views. At step 720, the current pointer and update process following the initial sequence. For example, the current index may be increased by the length of the matching sequence, then the procedure is repeated for the next sequence in the data. After increasing the current pointer in the data for streaming compressed data transmit streamed to the client.

If at step 716 decision, it appears that the view is not effective, then in step 722 the matching sequence are using a Huffman table as described above. At step 720, the current pointer is increased by the number of bytes in the matching sequence, and the procedure moves to the next sequence.

As described above, by using the Huffman table, you can optionally compress the data to be streamed. Were described three tables Huffman encoding reverse directions, lengths and sequences of literals, respectively. For example, according to figure 2, table 228 Huffman you can use to encode sequences of bytes literals 232 and reverse pointers 234. To distinguish between reverse the directions and sequence of literals inside a compressed stream, reverse the directions and sequence of literals can be provided with the appropriate unique prefixes, for example, each reverse pointer begins with the bits "0"and each sequence of literals begins with the bits "1". In one embodiment, a unified index code can be used to encode a sequence of literals and reverse directions by combining them into a single alphabet, so reverse the directions and sequence of literals have different corresponding characters.

Table encoding, for example, the above table Huffman, can be provided in different ways. For example, in one implementation, the encoding table is pre-configured for use in compression modules, and recovery after compression, so that the code tables do not need to be calculated for each data packet that is to be streamed. This can be used to speed up the encryption process. In another implementation, code tables dynamically calculate with predetermined intervals. For example, code tables, you can re-calculate each time after receiving a predetermined number of packets to update the coding tables.

On Fig shows a logical block diagram of the procedure in an illustrative implementation 800, in which the comparison of sequences optimize for additional optimization of data compression. As before, the server is 102 contains a buffer 212 history and a lookup table 216. The server 102 executes the module 116 compression to compress the packet 304(3). The offset from the beginning of the buffer 212 history to the beginning of the right sequence, in which the first two bytes are the same as can be represented in the form i1=HASH[HASH_SUM(s)]. In the example shown, the "s" is equal to "4 5", and i1=10 when counting from the beginning of the buffer 212 history and starting from scratch. Following the offset from the beginning of the buffer 212 history to following the right sequence can be represented as i2=NEXT[i1]. In the example shown in Fig, i2=NEXT[10]=4 in the chain 802(k) hashing. Similarly, each subsequent offset from the start of the buffer 212 history can be present in the chain 802(k) hashing as i3=NEXT[i2]. In the above example, i3=zero, because in the buffer 212 history is no longer the sequence, which includes "4 5".

Module 116 compression, when executed, may then initiate the procedure for compressing packet 304(3) starting with "4 5" at position 16 in the buffer 212 history. Module 116 compression may first determine in the buffer 212 the history of the position of the sequence with the original sequence "4 5" from position i1=HASH[HASH_SUM('4', '5')]=10 chain 802(k) hashing. Position save and NEXT[16] set equal to 10, and HASH[HASH_SUM('4', '5')] set equal to 16. Sequences are compared at the current position (16) and position i1 (10) with each other, first comparing the following account of bytes matching the x sequences. In this example, the third byte in the packet 304(3) is compared with the fifth byte in the packet 304(2) for a match. In the above example, the following account of bytes (i.e. the third byte in the respective sequences) are different because HISTORY[10+3]='3' and HISTORY[16+3]='6'. Therefore, the expected length of the matching sequence is equal to 2, and the expected position of the matching sequence is equal to 10.

Module 116 compression may then determine the position of the next sequence in the buffer 212 history in position i2=NEXT[i1]=4 from the lookup table 216. Since i2 is not equal to zero, i.e. there is a match, at least two bytes. The following account of the bytes following the relevant bytes "4 5"are compared, as before, which leads to the coincidence of 4 bytes. Therefore, the expected length of the matching sequence set equal to 4, and the position of the expected matching set equal to 4. Module 116 compression may then determine the position of another sequence in the buffer 212 history in the position i3=NEXT[i2]=0 chain 802(k) hashing. Since i3 is zero, this is the end of the chain 802(k) hashing, and no other provisions are not compared. Note that the module 116 compression, in one implementation, does not check especially the end of the chain 802(k) hashing. Instead, the sequence at position "i0" (16 in the example on asanam on Fig), NEXT[0] is set equal to i0. Therefore, upon reaching the end of the chain 802(k) hashing (iN=NEXT[i{N-1}]=0), it is checked, the module 116 compression is transferred to the i{N+1}=NEXT[iN]=i0.

Comparing "the following" on account of bytes after the expected length of the matching sequence, you can improve the speed comparison. In the previous example, for example, HISTORY[i0+MatchLength] compared with HISTORY[i0+MatchLength]. In the absence of other sequences in the buffer 212 history for comparison is a comparison of the complete sequences in each respective position. In other words, compare each byte, one after the other, in the respective sequences in the relevant provisions in the buffer 212 history. If the comparison of the complete sequence successfully, then remove the matching sequence. Thus, it is possible to get a sizeable increase in the speed comparison of the sequences in the buffer 212 history.

Figure 9 shows a diagram of a system 900 in an illustrative implementation, in which the compression dynamically configured in accordance with feedback received from the system. Communication between the server 102 and the client 104 over the network can vary due to many factors. For example, the client 104 may have limited software and/or hardware resources, so that the client 104, for recovery of data after compression have to spend more in the time, than the server 102 to compress them. In another example, the server 102 may output data to multiple clients, so the clients can recover after compression data faster than the server 102 may compress the data for each client. Adjusting one or more compression parameters that have been described above, it is possible to optimize the communication between the server 102 and the client 104 with regard to hardware and/or software resources of the server 102 and client 104, and network resources 106, which serves as a means of communication between them. For example, if the server 102 "expects"to send compressed data to the client 104, the server 102 may perform additional calculations compression for further data compression.

To configure the settings module 116 RDP compression 112 receive feedback. As feedback to adjust communication parameters you can use various factors, for example, the General characteristics of the network. For example, information from the network layer, which indicates the presence of a network of back pressure due to a slow link, can be used by module 116 compression to indicate the presence of additional time for further data compression. Therefore, the module 116 compression, you can dynamically configure to spend more time on data compression to reduce the final output size in the presence of protystavlena is.

In another example, the RDP 112 may use a fixed array (pool) buffers 902 904(1),..., 904(h),..., 904(H) history. The upper levels who want to send the data that you are requesting (allocating) the buffer (e.g. buffer 904(h)) of the array 902, fill the buffer 904(h) data (which includes data compression), and then transmitting the compressed data to the client 104. The buffer 904(h) only returns the array 902, meaning "exempt", after the transfer of the contents of the buffer. This technique allows RDP 112 and, in particular, the module 116 compression to get feedback, i.e. information back pressure, such as whether the network connection is fast or slow (for example, the amount of network bandwidth), whether the client is fast or slow (for example, the time necessary for the client to recover data compression), etc. on the basis of how much you want for the "liberation" of the buffer back into an array of buffers.

In another example, if not available none of the buffers 904(1)-904(H) array 902, the module 116 compression can be adapted to a more "hard work"by setting different thresholds compression so that he can spend more time on compression. After improving the network module 116 compression can also be configured to implement a smaller number of compression operations to quickly transfer data. For example, if the network 106 has a significant throughput capability is, the number of transactions compression can be reduced, since no compression is required to reduce the time required for data transfer. Thus, it is possible to use a dynamic method to change the compression settings at run time depending on the fluctuating network conditions. In another implementation, the initial measurement of the speed of the network is used to configure parameters that are then used during the session.

According to the above, the factors that are used to configure module 116 compression can also consider hardware and software resources of the server 102. For example, you can consider the load on the server 102 (e.g., how many active sessions provides the server 102, the load on the processor 202, shown in figure 2, and so on) and dynamically adjusts the compression ratio to compensate by using less resources of the Central processing unit (CPU) under compression. An example of a compression option that you can adjust is the size of the search window. For example, the size of the search window can be configured from 64K to 512K. A larger window can provide greater compression, but it can be slower. Therefore, it may be advantageous to "switch" to a large window, if the network is slow.

Another example of a factor that is used to configure the mod is I 116 compression, is the number of links in the chain hash passed to find matches that you can configure. For example, a long crawl the links of the chain may increase the probability of longer matches, but may cost additional hardware and/or software resources for the implementation of the agreement.

Another example of a factor that is used to configure the module 116 compression is a threshold that indicates the longest match is found for the end of the search. As described above, the threshold can be used to limit the scope of searches carried out for a match. The higher this threshold, the higher the probability of finding a longer match and, thus, greater data compression. However, the implementation of this search can also be used more resources of the data processing. Although considered various factors and parameters, you can also use other described factors and parameters.

Although the invention has been described with reference to structural features and/or methodological acts, it should be understood that the invention defined by the attached claims is not required to be limited to the described specific features or actions. On the contrary, the specific features and steps are disclosed for illustrative forms of " the claimed invention.

1. The method for compressing data for transmission in a terminal services environment, comprising stages, which
find the index in the lookup table, which coincides with the initial sequence in the data, while the lookup table contains a set of cells, with each cell is accessed using a particular one of the set of indexes, and each cell indicates whether the corresponding index in the history buffer, and if so, optionally specifies one or more provisions of the relevant index in the history buffer, and
if the corresponding cell is coincident index specifies a set of provisions
for each position is compared to the sequence at the position having the matching index, sequence data, and the above sequence contains the initial sequence,
get the matching sequence by comparing the results based on at least one of the length and position of the sequence at each position, and
represent the matching sequence with a representation, which includes the length and position of the matching sequence in the history buffer.

2. The method according to claim 1, additionally containing phases in which
find one index in the lookup table DL is each sequence in the data
form compressed data, which contain one or more views, and
transmit the compressed data stream.

3. The method according to claim 1, in which the cell is coincident index specifies the hash chain, which includes every position coincident index in the history buffer.

4. The method according to claim 1, in which the original sequence, and the index consists of at least two bytes.

5. The method according to claim 1, further comprising stages, which form the compressed data that contains the view and pass in the streaming mode, the compressed data over the network, and the data is formatted as one or more packages.

6. The method according to claim 1, additionally containing a stage at which encode at least one of the length and position of the view using coding techniques selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

7. The method according to claim 1, in which
if the corresponding cell is coincident index does not indicate any position encode the original sequence by Huffman encoding,
if the corresponding cell is coincident index indicates only the position,
compare the sequence in this one the second position, have a matching index, sequence data,
get the matching sequence by comparing the results based on at least one of the length and position of the sequence mentioned in only one position, and
represent the matching sequence, using a view that contains the length and mentioned only the position of the matching sequence in the history buffer, and
when each sequence of data represented or encoded transmit streaming data with the encoding or representation.

8. The method according to claim 1, in which the comparison is to retrieve the matching sequence is performed with the use of one or more thresholds, selected from the group consisting of
the number of provisions that have a matching index to be compared,
size value that describes each position that have a matching index, and
size value, which describes the length of the sequence at each position, which coincides with the sequence data, which contains the matching index.

9. The method according to claim 1, additionally containing a stage on which to apply the cost function to determine whether the representation less memory when saving than consecutive matching is required, and, if so, generate compressed data that contains the view.

10. The method according to claim 1, additionally containing phase, which determines whether the position matching with one of the set of provisions in the table the most ancient use (NDI), and
each position in the table NDI has a corresponding representation NDI,
each position in the table NDI describes one of the collectively most recently used of the provisions of the sequences in the data previously transmitted in the streaming mode, and
if the position of the matching sequence in the table NDI, the position matching sequences encode using the appropriate representation NIDS table NIDS.

11. Machine-readable media containing Mashinostroenie commands that, when performed by implementing the method according to claim 1.

12. The method for compressing data for transmission in a terminal services environment, comprising stages, which
add data to the history buffer,
updating a lookup table, which indicates the buffer prehistory, to include added data, while the lookup table contains a set of cells, with each cell is accessed using a particular one of the set of indexes, and each cell indicates whether the corresponding Indus is in the clipboard history, and if so, optionally specifies one or more provisions of the relevant index in the history buffer,
set the current pointer to the added data in the history buffer,
find one index in the lookup table, which coincides with the initial sequence at the current pointer
if the corresponding cell is coincident index specifies a set of provisions
compare the sequence at each position that have a matching index, sequence added in the input data, which contain the original sequence,
get the matching sequence by comparing the results,
represent the matching sequence via submission, which includes the position and length of the matching sequence in the history buffer,
apply a cost function to determine whether the representation less memory when saving than the matching sequence,
if Yes, configure the data so that they included the above view, and move forward the current pointer to the length of the matching sequence,
otherwise, configure the data so that they included the original sequence, and move forward the current decree of the tel on the length of the original sequence, and
when the current pointer is moved through the added data is stacked configured data stream.

13. The method according to item 12, optionally containing phase, which encode at least one of the length and position of the view using coding techniques selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

14. The method according to item 12, wherein, when the initial sequence at the current pointer does not match any sequence in the history buffer, the initial sequence of bytes at the current pointer code for inclusion in the configured data for streaming using coding techniques selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

15. The method according to item 12, optionally containing phase, which determines whether the position matching with one of the set of provisions in the table the most ancient use (NDI), and
each position in the table NDI has a corresponding representation NDI,
each position in the table NDI describes one of the population most who have long used the provisions of the sequences in the data, previously streamed, and
if the position of the matching sequence in the table NDI, the position matching sequences encode using the appropriate representation NIDS table NIDS.

16. Machine-readable media containing Mashinostroenie commands that, when performed by implementing the method according to item 12.

17. Method of data compression setting, implemented in a network system containing a network, the client and the server providing the terminal service client, the server includes a compression process to compress data and at least one buffer prehistory, the method contains the steps that
fill the said history buffer data, compress the data and transmit the compressed data over the network to the client;
receive feedback information, which indicates the availability of resources for transmission of such data over the network from the terminal services client, based on the amount of time spent transferring all the data from the said history buffer; and
configure one or more parameters of the compression procedure in accordance with said information feedback.

18. The method according to 17, in which resources are selected from the group consisting of
the client's hardware resources,
software client resources
network resources network,
software resources of the server and
any combination of them.

19. Machine-readable media containing Mashinostroenie commands that, when performed by implementing the method according to 17.

20. Network system, configured to configure data compression and containing
network
the client and
the server providing the terminal service client, the server includes a compression process to compress data and at least one buffer background
one or more parameters of the compression procedure are configurable in accordance with feedback indicating the availability of resources for transmission is placed in the history buffer of compressed data over the network from the terminal services client and obtained on the basis of the amount of time spent transferring all the data from the above-mentioned buffer background.

21. The system according to claim 20, in which resources are selected from the group consisting of
the client's hardware resources,
software client resources
network resources network
hardware resources of the server,
software resources of the server and
any combination of them.

22. The server that contains
the history buffer having a set of bytes
a lookup table containing a set of cells, with each cell is available with the use of a specific one of the population and indexes, and specifies if the corresponding index in the history buffer, and if so, optionally specifies one or more provisions of the relevant index in the history buffer, and
the compression module, which is designed to perform, to
find one sequence index in the lookup table, which coincides with the initial sequence data for transmission to the client from the terminal services
if the corresponding cell is coincident index specifies the collection of the above-mentioned provisions,
for each position to compare the sequence at the position having the matching index, sequence data, and the above sequence contains the initial sequence,
get the matching sequence by comparing the results based on at least one of the length and position of the sequence at each position, and
to submit a matching sequence with a representation, which includes the length and position of the matching sequence in the history buffer.

23. The server according to article 22, in which the compression module is additionally designed to perform to
find one index in the lookup table for each sequence in the data
to generate compressed data, which contain one and the several views, and
to transmit the compressed data stream.

24. The server according to article 22, in which the cell is coincident index specifies the hash chain, which includes every position coincident index in the history buffer.

25. The server according to article 22, in which the original sequence, and the index consists of at least two bytes.

26. The server according to article 22, in which the compression module advanced
designed to perform, to
to form compressed data containing the representation, and to package the compressed data for transmission in streaming mode
network, and the data is formatted as one or more
packages.

27. The server according to article 22, in which the compression module is additionally designed to perform to encode at least one of the length and position of the view using coding techniques selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

28. The server according to article 22, in which the compression module is additionally designed to perform in order to encode the initial sequence if corresponding cell coincident index does not indicate any position, using coding techniques selected from the group consisting of
the code is by Huffman,
arithmetic encoding,
prefix encoding, and
coding Markov.

29. The server according to article 22, in which the comparison is to retrieve the matching sequence is carried out using one or more thresholds, selected from the group consisting of
the number of provisions that have a matching index to be compared,
size value that describes each position that have a matching index, and
size value, which describes the length of the sequence at each position, which coincides with the sequence in the data that contain the matching index.

30. The server according to article 22, in which the compression module is additionally designed to perform, to apply a cost function to determine whether the representation less memory when saving than the matching sequence, and, if so, the formation of the compressed data that contains the view.

31. The server according to article 22, in which the compression module is additionally designed to perform to determine whether the position matching with one of the set of provisions in the table the most ancient use (NDI), and
each position in the table NDI has a corresponding representation NDI,
each position in the table NDI describes one of sovocool the most recently used of the provisions of the sequences in the data, previously streamed, and
if the position of the matching sequence in the table NDI, the position of the matching sequence is encoded using the appropriate representation NIDS table NIDS.

32. Network system, made with the possibility of data compression and containing
network
the server that contains
the first history buffer having a set of bytes
a lookup table containing a set of cells, with each cell is accessed using a particular one of the set of indexes, and each cell indicates whether the corresponding index in the history buffer, and if so, optionally specifies one or more provisions of the relevant index in the history buffer, and
the compression module, which is designed to perform, to
find one index in the lookup table, which coincides with the initial sequence at the current pointer in the data stream, in accordance with the request remote access
if the corresponding cell is coincident index specifies one or more provisions, to compare the sequence at each position that have a matching index, sequence data at the current pointer, get the matching sequence according to the results than the Oia, to configure the data so that they included the position and length of the matching sequence in the first history buffer, and move forward the current pointer to the length of the matching sequence,
if the corresponding cell is coincident index does not point to any provision, configure the data so that they included the original sequence, and move forward the current pointer to the length of the original sequence, and
when the current pointer is moved through the newly added data stream configured network data and
the client connected with a possibility of connection to the network and containing a second buffer of the historical and the module recovery after compression, which is designed to perform in order to restore after compression of streaming data by finding the matching sequence in the second buffer prehistory on the basis of the position and length specified in the view.

33. System p, in which the automatic recovery after compression is additionally intended for execution by the client to add data recovered after compression, the second history buffer.

34. System p, in which the compression module is additionally designed to perform a server to encode at mariodragon the length and position of the view using coding techniques, selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

35. System p, in which case the corresponding cell of the matching index does not indicate any position, the compression module is additionally designed to perform with the purpose of encoding the original sequence using coding techniques selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

36. System p, in which the compression module is additionally intended for execution by the server to determine whether the position matching with one of the set of provisions, in the table the most ancient use (NDI), and
each position in the table NDI has a corresponding representation NDI,
each position in the table NDI describes one of the collectively most recently used of the provisions of the sequences in the data previously transmitted in the streaming mode, and
if the position of the matching sequence in the table NDI, the position of the matching sequence is encoded using the appropriate representation NIDS table NIDS.

37. Machine-readable wear the spruce, containing Mashinostroenie commands that, when performed by a computer, instruct the computer
find the index in the lookup table, which coincides with the initial sequence data for streaming to the client, and these data are used to generate the application user interface, remotely executed from the client, while the lookup table contains a set of cells, with each cell is accessed using a particular one of the set of indexes, and each cell indicates whether the corresponding index in the history buffer, and if so, optionally specifies one or more provisions of the relevant index in the history buffer,
if the corresponding cell is coincident index specifies a set of provisions
for each position to compare the sequence at the position having the matching index, sequence data, and the above sequence contains the initial sequence, and
to calculate the results of the comparison of the length of the matching sequence.

38. Machine-readable medium according to clause 37, in which Mashinostroenie commands tell the computer to present the matching sequence, using a view that contains the length and laid the E.

39. Machine-readable medium according to clause 37, in which the cell is coincident index specifies the hash chain, which includes every position coincident index in the history buffer.

40. Machine-readable medium according to clause 37, in which the original sequence, and the index consists of at least two bytes.

41. Machine-readable medium according to clause 37, in which Mashinostroenie commands tell the computer to encode at least one of the length and position of the view using a coding technique selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

42. Machine-readable medium according to clause 37, in which Mashinostroenie commands tell the computer to encode the initial sequence if corresponding cell coincident index does not indicate any position, using coding techniques selected from the group consisting of
Huffman encoding,
arithmetic encoding,
prefix encoding, and
coding Markov.

43. Machine-readable medium according to clause 37, in which the comparison is performed using one or more thresholds, selected from the group consisting of
number of locations, with the flowing index be compared,
size value that describes each position that have a matching index, and
size value, which describes the length of the sequence at each position, which coincides with the sequence in the data that contain the matching index.

44. Machine-readable medium according to clause 37, in which Mashinostroenie commands tell the computer to apply a cost function to determine whether a view that contains the length and position of the matching sequence, less memory when saving than the matching sequence, and, if so, to generate compressed data that contains the view.

45. Machine-readable medium according to clause 37, in which Mashinostroenie commands tell the computer to determine whether the position matching with one of the set of provisions in the table the most ancient use (NDI), and
each position in the table NDI has a corresponding representation NDI,
each position in the table NDI describes one of the collectively most recently used of the provisions of the sequences in the data previously transmitted in the streaming mode, and
if the position of the matching sequence in the table NDI, the position of the matching sequence is encoded with what omashu appropriate representation NIDS table NIDS.



 

Same patents:

FIELD: information technologies.

SUBSTANCE: invention is related to administration of conflicts resolution between television programs; in case of coinciding broadcasting timetables preferences are used, which throw into confusion a limited display or their combination. Specified result is achieved by the fact that suggested invention provides for definition of time gaps or time intervals, which identify duration of conflict, and their application for definition of available resources of record. They may be displayed in interface, friendly to user, which is easy to understand and simple to use. Other versions of realisation guarantee possibility of cyclic searching of various programs and/or available resources, independently on preference settings.

EFFECT: provision of possibility of cyclic searching of all available resources of conflict settlement to user.

30 cl, 10 dwg

FIELD: information technologies.

SUBSTANCE: there is offered broadcasting system for supplying information about access of broadcasting service in which transmission device generates information about access for at least one network among broadcasting network and interactive network from which broadcasting service is transmitted and supplies information about access to terminal through specified communication network. Receiver receives information about access of broadcasting service via communication network, analyses the received information about access for determination of network, from which broadcasting service is provided, among broadcasting network and interactive network and determines access address for receiving of broadcasting service.

EFFECT: effective transmitting/receiving of information about access of broadcasting services in broadcasting system.

65 cl, 7 dwg, 37 tbl

FIELD: physics; communication.

SUBSTANCE: invention relates to transmission of data to a mobile data processing unit. Data are received by a digital audio and/or television receiving device (100), where the data are contained in traffic of digital audio and/or television signals. The data are then extracted from the traffic of digital audio and/or television signals and electromagnetic signals are transmitted by the digital audio and/or television receiving device (100) so as to transmit data extracted from the digital audio and/or television receiving device (100) to a mobile data processing unit (200). The extracted data are transmitted from the digital audio and/or television receiving device (100) to the mobile data processing unit (200) in response to periodic queries from the mobile data processing unit (200) to the digital audio and/or television receiving device (100).

EFFECT: provision for additional data provider and mobile unit user with proportional capacities to act on data, which are currently being transmitted to the mobile unit.

24 cl, 5 dwg, 2 ex

FIELD: information technologies.

SUBSTANCE: invention relates to schedules containing programmes information screened on the display and, in particular, to EPG. Method comprises stages where a variety of audience preferences in watching TV programmes and their corresponding emphasis are displayed; choice of one or more audience preferences in watching TV programmes is made out of the mentioned variety; every mentioned audience preference in watching TV programmes is estimated according to the relevance hierarchy diagram; corresponding emphasis of a variety of audience preferences in watching TV programmes is determined according to the relevance hierarchy diagram. Herewith EPG is displayed in programme nomenclature with EPG comprising a quantity of TV programmes for a number of channels in many time intervals. Every mentioned TV programme has a lot of characteristics; and every mentioned TV programme of the programme nomenclature, with characteristics coinciding with chosen one or more audience preferences in watching TV programmes, is displayed with corresponding emphasis.

EFFECT: ensuring improved search of programmes and broadcasting services.

38 cl, 8 dwg

FIELD: physic, video engineering.

SUBSTANCE: present invention is related in general to the field of interactive TV engineering and in particular to record of information content of interactive TV, and more precisely - to record of interactive TV applications. Method for recording of interactive TV programme for its reproduction in later period of time, in which mentioned programme of interactive TV contains at least one application of interactive TV, transfer of mentioned applications is realised inside application modules by means of data carousel in transport flow, at that method contains the following operations: mentioned transport flow is received, transport flow is analysed for availability of application modules, mentioned application modules are memorised in the form of recorded flow on information medium, at that saving of mentioned saved flow is realised in file separately from mentioned transport flow, mentioned file contains sequence of memorised application modules, at that headline precedes to single saved application module, and mentioned headline contains information on location for at least the following application module.

EFFECT: increased efficiency in reproduction.

14 cl, 6 dwg

FIELD: information technology.

SUBSTANCE: present invention relates to a device and method of recording information and to recording medium. The device records digitally encoded video data on a recording medium in accordance with a predefined format, such as BD. The device has an input unit (91) for receiving a data stream, containing video data and application data objects, contained in messages, such as DVB-MHP. The device has message block (92, 94) for picking out a message from the data stream. The message is recorded in message file in form of a message sequence for the program, separately from the video data. The device also has a syntactic analyser (95) for generating application control information, which contains information for access to messages in the message file. The application control information is stored in the information message file.

EFFECT: more functional capabilities.

10 cl, 14 dwg

FIELD: information technologies.

SUBSTANCE: broadcast content is formed via broadcast content providers, broadcast content providers are connected to internal IP-network for broadcasting programs distribution, broadcast content of broadcast content providers is transferred via internal IP-network over communication lines and line equipment of cellular networks, cellular network information is transferred over communication lines and line equipment of cellular networks, total flow of broadcast content information and cellular network information is generated to transfer it to at least one base station of cellular network, independent flows are separated from the said total information flow: cellular network data flow and broadcasting network data. Separated independent data flows are transferred to the said receive/transmit equipment to transfer them over corresponding independent channels to subscribers of integrated communication and broadcasting system who are located in integrated system coverage area.

EFFECT: increase in broadcasting coverage area.

21 cl, 2 dwg

FIELD: physics; communication.

SUBSTANCE: present invention pertains to image distribution system, distributing image data from a server through a network, to a client terminal and a method of controlling the distribution. If the client changes the size of the image window during display of image data, distributed from the server to the image window of the client terminal, client terminal notifies the server of new size of the image window. The server changes the size of the image data such that, the image has the same size as the window on the client terminal, and sends the client terminal image data with the altered size. This way, there can be no need for processing the change in size at the client terminal.

EFFECT: possibility of redistribution of computational load between a client terminal and a server.

22 cl, 17 dwg

FIELD: physics, computer equipment.

SUBSTANCE: invention concerns devices and methods of information processing. The information of property making the metainformation, corresponding to the attribute information of the associated content, contains the information of the plan of data for the initial content containing on a server, such, as the information on a file format, the information of the codec representing the plan of data coding, and the information on resolving ability. In reply to inquiry about reception of the information of the content from the client, generate and transmit the client the information of the content including the information of the plan of data for the initial content. This structure allows the client to output inquiry about content transmission in which the optimum plan of data is spotted on the basis of the plan of data of the initial content.

EFFECT: possibility to the client to gain the information of the plan of data of the initial content containing on the server, and also maintenance of reproduction of data with high quality.

26 cl, 14 dwg

FIELD: videonavigation.

SUBSTANCE: method for delivery of VoD content elements contains following stages in which: multiple content elements are saved in content repository; list of content sequence is saved, which sequence determines order in which content elements are taken from content repository, and associated attributes for each content element in content sequence list are saved in attribute repository, at that, at least one of associated attributes of each content element specifies which navigation actions are available for this content element; content elements with their associated attributes are fed in order determined by content sequence list, at that, navigation within and between elements of VoD is activated in accordance with associated attributes.

EFFECT: providing of properly nonlinear on-line radio navigation.

11 cl, 5 dwg

FIELD: physics; communication.

SUBSTANCE: invention relates to coding information values without loss and, particularly to the concept of guaranteeing maximum bit speed for coded presentation of information values. A compact coded presentation of information values, which does not exceed a predetermined size, can be obtained when the first coding rule, which generates the coded presentation of information values with varying length, is compared with a second coding rule, which generates a coded presentation of information values with fixed length, and when a coding rule, which leads to a coded presentation which requires a lesser number of bits, is chosen. That way, it can be guaranteed that, maximum bit speed will not exceed maximum bit speed of the second coding rule, in accordance with which the second coded presentation is obtained. Through transmission of signals for selecting the coding rule through a certain information rule together with coded presentation of information values, correct information values can be obtained later at the decoder side, using a decoding rule which corresponds to the coding rule, used during coding.

EFFECT: more accurate information display.

17 cl, 6 dwg

FIELD: physics; computer technology.

SUBSTANCE: invention concerns computer systems, in particular, to ways of data transfer between client and server applications, such as e-mail applications. A method of grouping of numerous sets of responses on a server and sending of responses to the client in one group (i.e. "generated chain" or "packed" group). Each set of responses can be changed and-or compressed. If the client accepts group each set is processed separately. The client can be executed with possibility of handing on of the size of not compressed set of responses with which it can operate. The server can use this information for creation of sets of responses of the resolved size and can compress or not compress sets of responses. The server can form chains of sets of responses and can continue forming of a chain of the compressed or uncompressed sets until the server buffer will not be full or close to filling. The set of responses generated by a chain can be sent then to the client and can process each set of responses separately.

EFFECT: increase of performance of the specified connections.

23 cl, 12 dwg

FIELD: physics; communication.

SUBSTANCE: present invention pertains to multimedia information transmission systems. The technical outcome is achieved by that, video image, for example, in a multimedia stream is scanned before compression so as to identify symbols, such as graphic characters and alphanumeric characters. The types, positions and sizes of the symbols are recorded for presenting symbolic information. The image is then compressed with or with out compressing the symbols, which can be removed from the image before compression if necessary. The compressed video and symbolic information is sent to a receiver, which decompresses the video, optionally converts the symbols and then inserts them where the symbolic information indicates.

EFFECT: increased efficiency of transmitting compressed multimedia information.

34 cl, 3 dwg

FIELD: information technology.

SUBSTANCE: method contains steps of processing information on the basis of mathematical transformations, divisions of the image into blocks of the image and coding of the current block, and the division of the image is carried out repeatedly on square blocks whose sizes are defined by a mass of initial data. For blocks which are not analysed before, an un-oriented graph is built, whose each top corresponds to one of such blocks, and each block consistently subject to affine transformations. Each transformed block is compared to all other blocks and if the degree of distortions of such a block at replacement of one of other blocks satisfies with it to the set restrictions on quality of the image between corresponding tops the column create an edge for reception the column, minimal covering which the set of tops answers an optimum base subset of blocks. The information is compared with that stored in memory of the block therefore leaving the information on the storage of the image corresponding to the minimal volume of data necessary for restoration of the image, then the procedure is repeated for the next size of the square block.

EFFECT: increase in the factor of compression of the image with minimal loss of quality at its restoration.

2 cl, 1 dwg

FIELD: physics.

SUBSTANCE: said utility invention relates to signal processing in the form of successive values, e.g., audio signal samples or video signal samples, which, in particular, are especially suitable for lossless coding applications. During processing of a signal containing a sequence of discrete values, having the first frequency band with high energy signal and the second frequency band with low energy signal, the sequence of discrete values is manipulated initially (202) to obtain a sequence of manipulated values so that at least one of the manipulated values would be different from an integer. After that, the sequence of manipulated values is rounded (204) to obtain a sequence of rounded manipulated values. Rounding is performed in order to create a generated rounding error spectrum so that the rounding error with the spectrum created would have higher energy in the first frequency band as compared to the second frequency band.

EFFECT: obtaining particularly efficient coding.

19 cl, 24 dwg

FIELD: computer engineering, possible use for processing signals for serially incoming values.

SUBSTANCE: device contains means for generating first non-integer input value and second non-integer input value, where the first non-integer input value is composed of first source value and third source value by means of first elevation step and second elevation step and following weighing, second non-integer input value is formed by weighing the second source value; means for combining the first and second non-integer input values and for rounding off the non-integer resulting value.

EFFECT: reduced rounding error.

5 cl, 24 dwg

FIELD: technology for transmitting process data from field device to process control center.

SUBSTANCE: in accordance to the invention, process data contains information about working state of field device, and/or information about process variables measured by field device, and/or field device identification data. Process data appearing in time interval between two transmissions is evaluated, divided onto static and dynamic, data is recorded, transferred to process control center. Static data is transferred in abbreviated form, in form of a binary status value.

EFFECT: creation of method for transmitting reduced amount of process data.

2 cl, 2 dwg

FIELD: radio engineering and television, possible use during generation, transmission and receipt of video-frames.

SUBSTANCE: in accordance to invention introduced additionally to encoder are video frames memory block, first function memory block, video frame transmission block, block for storing video frame being reproduced, while input of encoder serially, through block for forming video frames, video frames memory block, block for forming difference video frame, first frame memory block, video frame transmission block and block for memorizing video frame being reproduced is connected to second input of block for forming difference video frame, third input of which is connected to output of first function memory block, output of which is connected to second input of video frame transmission block, output of which is the output of device encoder. Introduced additionally to decoder are video frames receipt block, comparator and second function memory block, while input of decoder is serially, through video frame receipt block, second frame memory block and comparator, is connected to second video frame restoration block, third input of which is connected to output of second function memory device, and output is the output of decoder of device. Device realizes generation, transmission and receipt of code of function of distribution of screen point brightness in a series of frames, making it possible to increase the code compression coefficient.

EFFECT: increased coefficient of code compression of video frame information.

1 tbl, 1 dwg, 7 app

FIELD: technology for encoding and decoding, used for storing and transferring descriptive elements of document of XML-like structure.

SUBSTANCE: method includes using at least one table, received from XML structure, while table contains identification information for unambiguous identification of each descriptive element on hierarchic tree and structural information, browsing of hierarchic image of sample stored in memory from parent descriptive element to children descriptive elements for reaching encoded descriptive element, and extraction of identification information of each browsed descriptive element, encoding of aforementioned descriptive element in form of fragment, containing aforementioned information content and series of extracted identification information.

EFFECT: provision of efficient sample encoding plan and possible expansion of binary format for further plans, determined within limits of MPEG-7.

7 cl, 6 dwg, 2 tbl

FIELD: technology for encoding multimedia objects.

SUBSTANCE: method for encoding a multimedia object includes following stages: multimedia object is encoded for producing a bit stream and information about quality is added to bit stream, while information about quality denotes quality of multimedia object relatively to given position or relatively to given part of bit stream, while information about quality is provided in quality tags, aforementioned quality tag provides a values of quality tag, and value of quality tag characterizes distortion in encoded multimedia object being reproduced, when bit stream is truncated in point, related to quality tag.

EFFECT: development of improved and efficient method/system for encoding multimedia objects.

13 cl, 2 dwg

FIELD: engines and pumps.

SUBSTANCE: invention can be used to protect software of the ICE control unit against unauthorised changing. Proposed method of developing software of the running ICE control unit consists in rewriting the software of the ICE control unit into external two-port RAM, restarting ICE, specifying the software data array including calibration tables and constants for ICE running under various operating conditions. The data made more specific is entered into aforesaid two-port external RAM. The development made, the improved software is written into ERPOM of the ICE control unit microcontroller. Note here that, prior to starting ICE, software is divided into an executable code and data array including calibration tables and constants and rewritten into the said two-port RAM. The executable code is written into EPROM, reading out from EPROM is locked by program means. Finally, the data array with calibration tables and constants is changed. The changed data addresses are added to said executable code. Now, improved software is written into EPROM of the ICE control unit microcontroller and reading out from EPROM is locked by program means.

EFFECT: improved software protection.

2 cl, 1 dwg

Up!