Encoding or decoding characters as word in corpus

Data may be decompressed by receiving a compressed sequence of characters, the compressed sequence of characters being represented by at least a first received number, dividing the first received number by a number of words in a corpus of words to determine a quotient and a remainder, retrieving a word from the corpus of words based on the remainder, retrieving a transformation from a transformation index based on the quotient, and performing the retrieved transformation on the retrieved word. The representations of characters included in the transformed word may be a decompressed version of the received compressed sequence of characters.

TECHNICAL FIELD

This description relates to compressing and decompressing data.

BACKGROUND

Data may be compressed according to algorithms known to both sender and receiver. Compression may reduce the number of bits or other representations required to transmit the data.

SUMMARY

According to an example embodiment, a non-transitory computer-readable storage medium may comprise instructions stored thereon. When executed by at least one processor, the instructions may be configured to cause a computing system to decompress data by receiving, via an electronic transmission medium, a compressed sequence of characters, the compressed sequence of characters being represented by at least a first received number, dividing the first received number by a number of words in a corpus of words to determine a quotient and a remainder, retrieving a word from the corpus of words based on the remainder, the corpus of words being stored on at least one memory device, retrieving a transformation from a transformation index based on the quotient, the transformation index being stored on the at least one memory device, performing the retrieved transformation on the retrieved word, and sending representations of characters included the transformed word to a computing device, the representations of characters included in the transformed word being a decompressed version of the received compressed sequence of characters.

According to another example embodiment, a non-transitory computer-readable storage medium may comprise instructions stored thereon. When executed by at least one processor, the instructions may be configured to cause a computing system to decompress data by receiving, via an electronic transmission medium, a compressed sequence of characters, the compressed sequence of characters being represented by at least a distance value and a length value, determining whether the distance value exceeds a window size of a window of previously decoded characters, the window of previously decoded characters being stored on at least one memory device. If the distance value does not exceed the window size, the instructions may be configured to cause the computing system to repeat a sequence of previously decoded characters from the window of previously decoded characters with a length based on the length value at a position in the window of previously decoded characters based on the distance value. If the distance value does exceed the window size, the instructions may be configured to cause the computing system to retrieve a word from a corpus of words, the corpus of words being stored on the at least one memory device. The instructions may be further configured to cause the computing system to send representations of characters included in the retrieved word to a computing device, the representations of characters included in the retrieved word being a decompressed version of the received compressed sequence of characters.

According to another example embodiment, a non-transitory computer-readable storage medium may comprise instructions stored thereon. When executed by at least one processor, the instructions may be configured to cause a computing system to compress data by determining whether a sequence of characters matches a word included in a corpus of words or matches a transformed version of the word, the corpus of words being stored in at least one memory device and the transformation performed on the word being stored in the at least one memory device. If the sequence if characters does not match the word included in the corpus of words and is not one transformation away from the word, the instructions may be configured to cause the computing system to encode the sequence of characters as a sequence of codewords. If the sequence of characters matches the word included in the corpus of words, the instructions may be configured to cause the computing system to encode the sequence of characters with a reference to the word. If the sequence of characters matches the transformed version of the word, the instructions may be configured to cause the computing system to encode the sequence of characters with a reference to the word and a reference to the transformation.

DETAILED DESCRIPTION

FIG. 1is a diagram of a communication system100according to an example implementation. The communication system100may transmit information and/or data from a source102to a destination110. The information and/or data may represent characters, such as letters, numbers, punctuations marks, and/or symbols, in any language, such as English, German, Hungarian, Arabic, and/or Chinese. The characters may be encoded into a bit-level (ones and zeroes) or other representation, with combinations of multiple bits or other symbols representing characters, and may be compressed. Compression may reduce the number of bits or other symbols needed to represent the information and/or data.

The information and/or data may be compressed by, for example, including references to words and/or transformations. Rather than representing each character individually with a combination of bits or other symbols, some sequences of characters may be represented by references to words, or sequences of characters stored in a corpus or dictionary, and/or transformations, which may be modifications of or changes to the words. The words may be stored sequences of multiple characters, such as at least two characters, at least three characters, at least four characters, or any minimum number of characters. The minimum number of characters should be low enough to include a large number of words to facilitate encoding, but high enough that encoding by a length/distance pair requires fewer bits or other symbols than simply encoding each character individually.

The transformations may include, for example, an addition of a space (“ ”) before or after the word, capitalization of a first character of the word, addition of and/or prepending a prefix before and/or to the word, addition of and/or appending a period or suffix after and/or to the word, addition of a space and a common word (e.g. “the”) after the word, or a change of font (e.g. italicization) of the word. Including suffixes, rather than prefixes (and/or but not prefixes) in the transformations, may facilitate determining whether a transformed word ends with a most recent character. The references to words and/or transformations may reduce the number of bits or other symbols needed to represent the information and/or data. Some sequences of characters may also be represented by references to previous sequences of characters, further reducing the number of bits or other symbols needed to represent the information and/or data.

An example index of transformations is appended hereto as Appendix A. In the example of Appendix A, a first column may include prefixes for which the transformation includes prepending the character(s) (if any) to the retrieved word, a second column includes transformations that include changing the characters in the retrieved word such as changing case or capitalization (such as from lower case to upper case or upper case to lower case) or removing a character, and a third column includes suffixes for which the transformation includes appending the (character(s) if any to the retrieved word. An ID of the transformation, which may range from 0 to 105 in the example shown in Appendix A, may be used to index the transformation. The quotient determined by dividing the distance value by the number of words in the corpus and/or subcorpus may directly index the ID of the transformation, or a remainder determined by dividing the quotient by the number of transformations (e.g. 105+1=106 transformations) may be used to index the ID of the transformation.

The system100may include the source102. The source102may include a computing system, or a component of a computing system such as a memory or a file, which stores information or data that represent characters, such as alphanumeric characters, punctuation marks, or characters or symbols according to any understood character system and/or language. The source102may, in response to an instruction or as part of an operation or function to transmit the information or data, provide the data or characters to an encoder104.

The encoder104may encode the data for transmission to the destination110via a communication channel106. The encoder104may compress the data to reduce a number of bits or other symbols that are needed to transmit the data or information over the channel106. The encoder104may, for example, compress the characters by encoding the characters using codewords according to a lossless compression algorithm, such as Huffman encoding, which generates a unique sequence of bits for each possible character in the data stream. The encoder104may also compress the data by referencing previous sequences of characters and/or words which were encoded.

Rather than repeat each character in the previously encoded word, the encoder104may include a reference to the previously encoded word, such as a distance from the present position in the data stream, and the length of the previously encoded word. Encoder104may, for example, include the distance or number of characters back from the present position and/or current character that the previously encoded word was encoded and/or began, and the length of the referenced and/or previously encoded word, or number of characters in the referenced and/or previously encoded word. The encoder104may maintain a window of previously encoded characters and/or words. The encoder104may encode sequences of characters by reference to previously encoded sequences of characters within the window of previously encoded characters and/or words.

The encoder104may also encode sequences of characters by a reference to a word within a dictionary or corpus of words, and/or a reference to a transformation of the word. In an example implementation, the encoder104may distinguish between repeating a previously encoded sequence of characters and referencing a word in the dictionary or corpus of words by the distance value. A distance value that is within a size of the window of previously encoded characters and/or words may indicate that the encoder104has encoded the word by repeating a previously encoded sequence of characters. A distance value that exceeds the window size may indicate that the encoder104had encoded the sequence of characters by reference to the corpus of words or dictionary and/or the transformation. The sequence of characters may be encoded and/or compressed. In encoded and/or compressed form, the sequence of characters may be represented by a first number and/or second number. The first number and/or second number may represent the length value and/or the distance value.

The encoder104may send the encoded data to a decoder108via the communication channel106. While not shown inFIG. 1, the system100may also include a transmitter, which may include a modulator for modulating and/or generating the signals for transmission of the data from the encoder104over the channel106, and a receiver, which may include a demodulator for demodulating and/or interpreting the signals received via the channel106and providing the encoded data to the decoder108.

The system100may also include the decoder108. The decoder108may decode the data according to an algorithm stored, understood, and/or agreed to by both the encoder104and the decoder108, and/or according to an algorithm designed to decode data encoded according to the algorithm implemented by the encoder104. The decoder108may, for example, decode codewords that represent individual characters, decode sequences of characters based on references to previously decoded characters, and/or may decode sequences of characters based on references to words in the corpus of words and/or references to transformations. The decoder108may have maintained a same codebook or encoding table to decode the codewords as the encoder104before receiving the encoded data, or may generate the codebook or encoding table based on information received from the encoder104, such as a map of characters to codewords or a frequency table used to generate the codebook or encoding table. The decoder108may have also maintained a same or matching corpus of words and/or index(es) of transformation as the encoder104before receiving the encoded data, or may generate the corpus of words and/or index(es) of transformation based on information received from the encoder104.

The decoder108may decode some characters as literals and/or codewords representing single characters, and decode some characters as members of previously decoded sequences, members of words, and/or members of transformed words. The encoded data may include an indicator, such as a specific sequence of bits or other symbols, indicating that subsequent bits or other symbols will refer to a previously encoded sequence of characters, a word, and/or a transformed word. The decoder108may, for example, divide a received number, which may represent a distance value, by a number of words in a corpus of words and/or subcorpus included in the corpus of words, to determine a quotient and a reminder. The decoder may retrieve a word from the corpus and/or subcorpus based on the remainder, and may perform a transformation on the retrieved word based on the quotient. The decoder108may decode the received number, and/or a second received number which may be included in a length/distance pair, as the transformed word.

The decoder108may, for example, determine whether a received distance value exceeds a window size of a window of previously decoded characters. If the distance value does not exceed the window size, then the decoder108may repeat a string and/or sequence of previously decoded characters from the window of previously decoded characters with a length based on a received length value at a position in the window of previously decoded characters based on the distance value. If the distance value does exceed the window size, then the decoder108may retrieve a word from a corpus of words. The decoder108may use the distance value as an index to select a word from the corpus of words.

If a group, series, or sequence of bits or other symbols refers to a previously encoded/decoded word, the group, series, or sequence of bits or other symbols may include a length value and a distance value. The length value and distance value may be included in a length/distance pair.

The decoder108may check, for example, whether the distance value included in the encoded data exceeds a window size. If the distance value does not exceed the window size, then the decoder108may use the distance value and the length value to repeat a previously decoded string of characters. If the distance value does exceed the window size, then the decoder108may use the length value to select a subcorpus within the corpus of words, and/or to select a transformation index. The decoder108may, for example, use the distance value to select a word, and/or a transformation, from the corpus or subcorpus of words and/or the selected transformation index. In an example implementation, the decoder108may divide the distance value by the number of words in the corpus or subcorpus. The decoder108may use the quotient to select a transformation from the index of transformations, and may use the remainder to select a word from the corpus or subcorpus of words. The decoder108may perform the selected transformation on the selected word. The decoder108may provide the decompressed and/or decoded version of the characters and/or data, which may include representations of characters including individual characters, repeated sequences of characters, and/or transformed words, to the destination110, which may be a computing device such as a memory device and/or file included in a computing system that may also include the decoder108.

FIG. 2is a diagram of a computing system200according to an example implementation. The computing system200may include features of the encoder104and/or decoder108. The computing system200may be designed, for example, to only compress data, to only decompress data, or to both compress and decompress data according to a same and/or reciprocal compression/decompression algorithm. The functions, modules, and/or devices described with respect to the computing system200may be performed by and/or included in a single computing device, or may be divided and/or distributed between multiple computing devices. The computing system200may include an encoder202which performs any combination of the functions of the encoder104, a decoder204, which performs any combination of the functions of the decoder108, at least one memory device206, which may store instructions and/or data accessible by the encoder202and/or decoder204, a processor208, and/or an input/output module210.

The encoder202may encode and/or compress data according to any combination of the functions and techniques described herein. The encoder202may include a sequence scanner212. The sequence scanner212may scan sequences of characters and pass the sequences of characters to a match determiner220.

The sequence scanner212may include a window scanner214. The window scanner214may scan a window of previously encoded characters. The window254, an example of which is shown inFIG. 3A, may be stored in the at least one memory device206. The window scanner214may, for example, scan the window of previously encoded characters at different positions and with different lengths. The window scanner214may, for example, scan the window from a first position for words of increasing length from a minimum length to a maximum length, such as from length two, length three, length four, length five, up to the maximum word length. The window scanner214may then scan the window from a second position for words from the minimum length to the maximum length. The window scanner214may scan the window from all possible starting or beginning positions in the window and for all allowable lengths, and pass the words resulting from the scans to the match determiner220

FIG. 3Ais a diagram showing recent data300and an example window254. As shown inFIG. 3A, the recent data300, which may represent characters that have recently been encoded, in the order that they were encoded, may include characters numbered from zero to N−1. The characters may be represented by numbers that increase as time increases from the present to the past, as shown by the ‘t’ and arrow, with zero representing the most recently encoded character.

The window254of characters may represent a window size of characters that may be repeated by reference to distance and length. The window254may have a size, N. The size of the recent data, M, may represent the number of all characters recently encoded (such as the number of characters within a file that have been encoded), or may represent a number of encoded characters stored in the at least one memory device206.

The window scanner214may scan the window254for all possible sequences of characters for all possible starting positions in the window254from the minimum word size to the maximum word size, such as from N−1 to N−2, from N−1 to N−3, from N−1 to N−4, up to the maximum word size (the word size would be reflected by the difference between the beginning and end points of the scanned sequence plus one, e.g. ([beginning character] (N−1)−[ending character] (N−2)+1) would have a length of two), from N−2 to N−3, and so forth. The window scanner214may pass all of the scanned sequences within the window254to the match determiner220as candidate previous words and/or candidate previous sequences of characters (and/or previously encoded words, previously encoded strings of characters, or previously encoded sequences of characters) for repeating by reference to length and distance, along with a length value and a distance value for each scanned sequence. The match determiner220may determine whether a sequence of characters to be encoded matches a previously encoded sequence of characters in the window254. If the sequence of characters to be encoded does match a sequence of characters in the window254, then a previous sequence encoder224may encode the sequence of characters by a reference to a length and distance, with the distance referring to the beginning point (e.g. N−1) and the length indicating the number of characters and being used to determine the end point (e.g., end point=beginning point−length+1).

The window scanner214may also scan the window254to retrieve candidate current words and/or candidate current sequences of characters, which may be encoded by a reference to a candidate previous word and/or candidate previous sequence of characters or by a reference to a word in the corpus or subcorpus and/or a transformation in the transformation index. The window scanner214may scan the window254for all allowed lengths, such as from two or another minimum length sequentially to the longest allowed length, with the ending character being 0 for each possible present and/or most recent word and/or sequence of characters. For example, the window scanner214may scan characters 1 through 0 as a possible two-character candidate current word and/or candidate current sequence of characters, may scan characters 2 through 0 as a possible candidate current three-character word and/or candidate current sequence of characters, may scan characters 3 through 0 as a possible four-character candidate current word and/or candidate current sequence of characters, and so on until reaching either the beginning of the recent data (character M−1) or the beginning of the window254(character N−1) or the maximum allowed length of the word. The window scanner214may pass the scanned words and/or sequences of characters to the match determiner220as candidate current words and/or candidate current sequences of characters for encoding by reference to either candidate previous words and/or candidate previous sequences of characters or by reference to words in the corpus or subcorpus and/or transformation index. The window scanner214may also pass the beginning points in association with the candidate current words and/or candidate current sequences to the match determiner220.

FIG. 3Bis a diagram showing encoded data according to an example implementation. In this example, recent data300may include data encoded according to an alphabet including at least one codeword302. The codeword302may represent a literal encoding of a single character, and may include a sequence of bits or other symbols which represents a single character according to any encoding system, such as the American Standard Code for Information Interchange (ASCII), Unicode, or a lossless compression algorithm such as Huffman encoding. The codeword302may represent a character encoded by mapping characters to codewords according to an alphabet such as the alphabet260described with respect toFIG. 6, and which may be decoded by mapping codewords to characters according to the alphabet. The recent data may include more codewords following the codeword302, representing a sequence of codewords and representing a sequence of encoded characters, as shown by the ellipses between the codeword302and an indicator304.

The recent data300may include one or more length/value pairs that either refer to previously encoded sequences of characters, or refer to a word in the corpus and/or a transformation. The recent data300may include an indicator304preceding the length/distance pair. The indicator304may be a unique sequence of bits that indicates that characters will be encoded by a succeeding length/distance pair which may include a length value and distance value. The unique sequence of bits representing the indicator304may be determined by the encoding system and/or codebook. The length/distance pair succeeding the indicator304may include a length306, which either indicates a length of the sequence of characters to be repeated or a subcorpus of words and index of transformations, and a distance308, which indicates either a distance from the present position that the sequence of characters begins or is used to determine the word and transformation.

The recent data300may include more blocks and/or codewords as represented by the ellipses after the distance308, which may include codewords representing individual characters, and/or length/value pairs which may include sequences of indicators, lengths, and/or distances. While the example ofFIG. 3Bshows the length306preceding the distance308, the length and distance may be encoded in any order. In an example implementation, the indicator304need not be encoded separately, and the length and distance may instead be encoded with unique codewords and/or sequences of bits that are distinct from the codewords used to encode single characters.

Returning toFIG. 2, the sequence scanner212may include a corpus scanner216. The corpus scanner216may scan a corpus of words as candidate stored words or corpus words to encode the candidate current words and/or candidate current sequences of characters by reference to the candidate stored words or corpus words. The corpus256may be stored in the at least one memory device206.

FIG. 4shows the corpus256according to an example implementation. The corpus256may include multiple words which may be encoded by references to the words by the length/distance pair. In an example implementation, the corpus256may include subcorpuses402,404. The subcorpuses402,404may each include multiple words organized into an index and/or array. The words within the subcorpuses402,404and/or corpus256may be arranged in any order, such as alphabetically or based on their respective frequencies of occurrence as determined by sampling multiple data samples. The words in the subcorpuses402,404may be indexed from 0 to N−1 or M−1, for example, where N and M are the numbers of words in the respective subcorpuses402,404. The number of words, N, M, may be different for different subcorpuses402,404, or each subcorpus402,404may have a same number of words, according to example implementations.

The subcorpuses402,404may include words from different languages, such as English, Chinese, German, Arabic, or even words found in technical literature, such as computer science. The corpus256may include one subcorpus402,404for each language, or may include multiple subcorpuses for one or more languages to reduce the number of words in some subcorpuses402,404and/or to maintain a similar number of words in each subcorpus402,404.

Returning toFIG. 2, the corpus scanner216may provide all of the words in the corpus256to the transformer218, or only some of the words which are candidates for including the most recent character (denoted 0 inFIG. 3A). The corpus scanner216may, for example, perform a function such as a hash function on the most recent character (denoted by ‘0’ inFIG. 3A) to determine one or more languages and/or subcorpuses402,404(and associated transformation indexes described below) that may include the most recent character, thereby reducing the number of transformations to be performed by the transformer218and/or comparisons to be performed by the match determiner220.

The sequence scanner212may include a transformer218. The transformer218may perform transformations on the words received from the corpus scanner216. The transformer218may perform all transformations included in a transformation index on each of the words received from the sequence scanner, or may perform only transformations that may result in words ending with the most recent character. Transformations may include no change to the word, the addition of a space at the end of the word, the addition of a comma at the end of the word, capitalization of a first letter of the word, the addition of an ‘s’ at the end of the word, an addition of a suffix to the end of the word, a change of font (such as italicization), a transformation such as a transformation listed in the appendix to this document, or any other change. The transformations available may be the same for all of the subcorpuses402,404, or may be different for each subcorpus402,404. The transformations may be different for each subcorpus402,404because different changes to words are made for each language, for example.

FIG. 5shows an example of stored transformations258. The transformations258may be stored in the at least one memory device206. The stored transformations258may include multiple indices502,504which each include transformations. The indices may each include different numbers (e.g., N, M) of transformations, or may each include a same number of transformations. The values of N and M may be different in the examples described with reference toFIGS. 3A, 4, and 5. The values in the index502,504may be used to retrieve a transformation.

The transformer218may perform transformations based on all the transformation indexes502,504, or only transformation indexes that may include transformations that will result in a word which has a last character matching the most recent character. The transformer218may select, for each word to be transformed, a transformation index502,504matching and/or associated with the subcorpus402,404from which the word was retrieved, and/or a transformation index based on the most recent character, such as by performing a function such as a hash function on the most recent character to select the transformation index502,504. Performing transformations on the words received from the corpus scanner216may result in transformed words. The transformer218may provide the transformed words as candidate transformed words to the match determiner220. The transformer218may also provide and/or pass a number or other identifier of the subcorpus402,404, a number or other identifier of the transformation index502,504(which may or may not be the same as the number or other identifier of the subcorpus402,404), an identifier of the word, and/or an identifier of the transformation, to the match determiner220in association with the transformed word.

The encoder202may include a match determiner220. The match determiner220may determine whether a candidate current word or candidate current sequence of characters received from the window scanner214matches either a candidate previous word and/or candidate previous sequence of characters received from the window scanner214or a candidate transformed word received from the transformer218. The match determiner220may determine whether a match exists by comparing each candidate current word or candidate current sequence of characters received from the window scanner to each candidate previous word and/or candidate previous sequence of characters received from the window scanner214and each candidate transformed word received from the transformer218. If the match determiner220determines that more than one match exists, then the encoder202may encode the longest match and/or match with the most characters, or may select a match based on a cost metric. The cost metric may apply an information entropy model to choose a likely best match. The match determiner220may, for example, take into account the distance of the match and/or estimated entropy of the literals and/or characters that are replaced by the match. Some characters that were previously encoded as single characters may be re-encoded as previously encoded words and/or transformed words. If the match determiner220determines that a match does not exist, then the encoder may encode the most recent character as a single character.

The encoder202may include a character encoder222. If the match determiner220determined that there was no match, then the character encoder222may encode the most recent character as a literal, and/or with a single codeword, based on an encoding scheme as described above.

The encoder202may also include a previous sequence encoder224. The previous sequence encoder224may encode the sequence of characters if the match determiner220determined that the longest matching sequence of characters matched a previously encoded sequence of characters in the window254. The previous sequence encoder224may encode the sequence of characters by the length value and distance value. The previous sequence encoder224may include the length value, such as the length306shown inFIG. 3B, and the distance value, such as the distance308shown inFIG. 3B, of the longest match. The length value and distance value may have been received by the match determiner220in association with the candidate current word and/or candidate current sequence of characters.

If the match determiner220determined that the longest match was a transformed word, then the encoder202may encode the current or most recent sequence of characters a reference to the word in the corpus256and/or subcorpus402,404, and/or a transformation in the transformations258and/or one of the transformation indexes502,504. The word may be encoded, for example, by the length/distance pair. The length may indicate which subcorpus402,404the word should be found in and/or from which transformation index502,504should be selected. The word within the subcorpus402,404may be indexed using the distance value. In an example implementation, when decoded, the word within the subcorpus402,404may be indexed by the remainder resulting from dividing the distance value by the number of words in the subcorpus402,404, and/or the transformation may be indexed by the quotient resulting from dividing the distance value by the number of words in the subcorpus402,404.

The encoder202may include a corpus/transformation encoder226. The corpus/transformation encoder226may encode sequences of words when the match determiner220has determined that the longest match is a transformed word, and/or the current or most recent sequence of characters matches a word included in the corpus256, and/or subcorpus402,404, or is one transformation away from a word included in the corpus256and or subcorpus402,404.

The corpus/transformation encoder226may include a multiplier228and an adder230. The multiplier228may multiply the number of words in the subcorpus402,404from which the word is retrieved by an index number of the transformation performed on the word to achieve the match; the index number of the transformation may have been provided by the transformer218in association with the candidate transformed word which had the longest match. The adder230may add an index number of the word to the product determined by the multiplier228; the index number may have been provided by the corpus scanner216and/or transformer in association with the candidate transformed word which had the longest match. The sum of the value determined by the adder230and the multiplier228may be used to provide the distance value in the length/distance pair, such as a distance308. The length value in the length/distance pair may indicate the subcorpus402,404and/or transformation index502,504which stores the word and/or transformation of the transformed word with the longest match.

The computer system200may include a decoder204. The decoder204may decode and/or decompress data received by the computing system200according to any combination of the functions and techniques described herein. The decoder204may decode and/or decompress data received by the computing system200that was decoded and/or decompressed according to an algorithm similar to that described herein with respect to the encoder202. The decoder204may receive codewords representing individual characters in accordance with the alphabet260described with respect toFIG. 6. The decoder204may also receive a first value and/or a second value, which may be included in a length/distance pair in which the first value represents a length value and/or the second value represents a distance value, respectively, or the first value may represent a distance value and/or the second value may represent a length value.

The decoder204may include a match checker232. The match checker232may determine whether data has been encoded based on a match to either previous data within the window254or a word in the corpus256and/or a transformation, or was encoded as a literal and/or by representing a single character with a codeword. The match checker232may determine whether the data was encoded based on a match by checking for an indicator304, or based on codewords or other representations of a length and/or distance value that indicate encoding based on a match.

If the match checker232determines that there is no match to either a previously encoded data or to words and/or transformations, the decoder204may decode the data as literals and/or decode a single, most recent codeword or other representation as a single character. If the match checker232determines that the data has been encoded by a reference to previously encoded window of data, then the decoder204may decode the data by repeating a previously decoded string of characters. If the match checker232determines that the data has been encoded by a reference to a word in the corpus256and/or a transformation, then the data may be decoded by retrieving the word and/or transformation, and if a transformation is retrieved, performing the retrieved transformation on the retrieved word.

The decoder204may include a codeword decoder234. The codeword decoder234may decode the data and/or most recent codeword or other representation as a literal, and/or as a single character. The codeword decoder234may decode the data according to an encoding/decoding scheme, such as ASCII, Unicode, or a compression algorithm, such as Huffman encoding, which was mutually understood and/or agreed upon by the decoder108(which may include the decoder204) and encoder104(which may include an encoder similar to the encoder202).

The decoder204may include a distance comparator236. The distance comparator236may compare the distance value to the window size. If the distance value is less than or equal to the window size, then the decoder204may decode the data by repeating a previously decoded sequence of characters. If the distance exceeds the window size, then the decoder204may decode the data retrieving the words from the corpus256, and/or subcorpus402,404, and/or performing a transformation stored in the stored transformations258and/or one of the transformations indexes502,504on the retrieved word.

The decoder204may include a string repeater238. The string repeater238may repeat a previously decoded string or sequence of characters if the distance comparator236determined that the length was less than or equal to the window size. The string repeater238may repeat the previously decoded string of characters beginning at a point indicated by the distance value and ending at a point determined based on both the distance value and the length value.

The decoder204may include a divider240. If the match checker232determined that there was a match, and a distance comparator236determined that the received distance exceeded the window size254, the divider240may perform division to determine a word index number and/or a transformation index number. The divider240may determine the transformation index number based on a quotient by dividing a received distance value by a number of words in the corpus256and/or subcorpus402,404from which the word is included. The divider240may determine the word index number based on a remainder by dividing a received distance value by a number of words in the corpus256and/or subcorpus402,404from which the word is included. The subcorpus402,404may be determined based on the length value.

The decoder204may include a word retriever244. The word retriever244may retrieve a word if the match checker232determined a match and the distance comparator236determined that the received distance value exceeded the window size. The word retriever244may retrieve a word from the corpus256. The word retriever244may include a corpus selector246. The corpus selector246may select a subcorpus402,404from the corpus256based on the received length value. The subcorpuses402,404may, for example, each be associated with an integer value, such as 0, 1, 2, 3, 4, etc. The corpus selector246may select the subcorpus402,404associated with the value included in the received length value. After the corpus selector246has selected the subcorpus402,404, the word retriever244may retrieve the word from the subcorpus402,404. The word retriever244may retrieve the word from the subcorpus402,404based on the remainder243determined by the divider240. The word retriever244may, for example, use the remainder243as an index value to select the word from the subcorpus402,404.

The decoder204may include a transformer248. The transformer248may select a transformation based on the quotient242determined by the divider240. The transformer248may use the quotient242as an index to select the transformation from the stored transformations258and/or selected index of transformation502,504. In an example in which the transformations258include different sets, arrays, and/or indexes of transformations for each length value and/or each subcorpus402,404, the transformer248may include an index selector250. The index selector250may select a transformation index502,504from which the transformation matrix will be selected. The index selector250may select a transformation index502,504based on the received length value and/or based on the subcorpus402,404. In an example implementation, the transformation index502,504may each be associated with one subcorpus402,404.

The transformer248may select a transformation from the stored transformations258and/or selected transformation index502,504. The transformer248may use the quotient242as an index into the selected transformation index502,504to select a transformation. The transformer248may perform the selected transformation on the retrieved word. After the transformer248has performed the transformation on the retrieved word, the decoder204may add the transformed word to an output stream of decoded characters.

The at least one memory device206may include a non-transitory computer-readable storage medium. The memory device206may include a single memory device, or may include multiple memory devices. The memory device(s)206may include instructions252stored thereon. Instructions252may include instructions that may be executed by the processor208to cause the computing system200to perform any combination of the methods and/or functions described herein.

The memory206may store the window254. The window254may include previously encoded characters or previously decoded characters, which may be referenced by the string repeater238and/or referenced by the previous sequence encoder224. The size and/or length of the window254may be based on available memory or cache, or may be shortened to be less than a window length that would be possible using available memory or cache to facilitate more instances of encoding characters as transformed words.

The memory206may store the corpus256. The corpus256may include words that may be retrieved by the corpus scanner216and/or word retriever244. The corpus256may be subdivided into subcorpuses402,404.

The memory device206may store the transformations258. The transformations258may include transformations that may be retrieved and performed by the transformer218and/or transformer248. The transformations258may include a number of transformation indexes502,504based on, and/or equal to, the number of subcorpuses402,404.

The memory206may also include an alphabet260. The alphabet260may include encodings for characters that may be received in encoded form. The alphabet260may include, for example, a fixed-length encoding scheme, such as ASCII or Unicode, or may include encodings according to compression methods such as Huffman encoding. The alphabet260may have been stored by the computer system200before receiving data, or may have been generated based on information associated with the encoded data either before or after the encoding. The alphabet260may, for example, have been previously stored by both the encoder202and decoder204before any encoding or decoding, or may be generated based on the data to be decoded.

If the alphabet260was generated based on the data to be encoded, the encoder104may send the alphabet260to the decoder108in association with the encoded data. The alphabet260may have been literally included with the data received, such as by including the characters and associated representations in a header file, or the decoder108may generate the alphabet260based on information received from the encoder104in association with the encoded data, such as a frequency distribution that may be used to construct a Huffman encoding table.

FIG. 6shows an example of a stored alphabet260mapping characters to encodings. As shown inFIG. 6, characters602may map to encodings604in a one-to-one correspondence. The characters602may include alphanumeric characters and punctuation marks, which may also be used to represent the length value and the distance value, or the encodings604may include distinct representations of length and/or distance values that represent length and/or distance values but do not represent numeric values that are not encoded by reference to previously encoded/decoded words or words and/or transformations stored in the corpus256and/or stored transformations258. In the example in which distinct encodings604are used to represent length and distance values, the length and distance values may be represented by a shared set of values mapped to encodings, or the encodings used to represent length values may be distinct from the encodings used to represent distance values.

The computing system200may include a processor208. The processor208may include a processor capable of executing instructions, such as the instructions252stored in the memory206, to perform functions, processes, and/or methods such as the functions, processes, and/or methods described herein.

The computing system200may also include an input/output module210. The input/output module210may receive input and/or provide output. The input/output module210may include a single device that performs both input and output functions, or may include two or more modules that each perform either input functions or output functions. The input/output module210may, for example, receive the encoded data, output the decoded data, receive instructions from a user, and/or provide the decoded data to a display for viewing by the user.

FIG. 7is a flowchart showing a method700for encoding data according to an example implementation. The method700may include the window scanner214scanning a sequence of characters for candidate current words and/or candidate current sequences of characters (702), as described above with respect toFIG. 2. The sequence of characters may include characters in the window254of characters.

The method700may include the match determiner220determining whether any of the candidate current words and/or candidate current sequences of characters match a previously encoded sequence (704). The match determiner220may determine whether any of the candidate current sequences ending with the most recent character matches any of the previously encoded sequences. If the scanned sequence of characters does match a previously encoded sequence, and/or if the match determiner220determines that the match between the scanned sequence of characters is longer than any other match (either with previously encoded characters or a word in the corpus256), then the method700may include the previous sequence encoder224encoding the sequence with a reference to a previously encoded sequence (706). The sequence may be encoded with reference to a previously encoded sequence by including a length value indicating a length of the previously encoded sequence, and a distance value indicating a distance from the present position and/or most recent character.

If the scanned sequence of characters does not match a previously encoded sequence, then the method700may include the match determiner220determining whether the scanned sequence of characters matches a word in the corpus256(708). In an example, the match determiner220may determine whether the scanned sequence of characters matches a word in the corpus256even if the scanned sequence of characters does match a previously encoded sequence. If the scanned sequence of characters does match a word in the corpus256, and/or if the match determiner220determines that the longest match of the scanned sequence of characters is a match to a word in the corpus256, then the method700may include encoding the sequence of characters with a reference to the word in the corpus (710).

The scanned sequence of characters may be encoded with a reference to the word in the corpus by, for example, the length value indicating the subcorpus402,404and the distance value indexing the word in the corpus256.

If the scanned sequence of characters does not match a word in the corpus256, then the method700may include determining whether the scanned sequence of characters is one transformation away from a word in the corpus256(712). In an example, the match determiner220may determine whether the scanned sequence of characters is one transformation away from a word in the corpus256even if the match determiner220determined that the scanned sequence of characters matches a previously encoded sequence and/or that the scanned sequence of characters matches a word in the corpus256.

If the scanned sequence of characters is one transformation away from a word in the corpus256, and/or if the match determiner220determines that the longest match of the scanned sequence of words is to a transformed word, then the method700may include the corpus/transformation encoder226encoding the scanned sequence of characters with a reference to the word and the transformation (716). The scanned sequence of characters may be encoded with a reference to the word in the corpus256by the length value indicating the subcorpus402,404and the transformation index, and the distance value being used to determine both the word and the transformation. If the scanned sequence of characters is not one transformation away from a word in the corpus, then the method700may include encoding the scanned sequence of characters as single characters with individual codewords (714). Encoding the scanned sequence of characters as single characters may include encoding each individual character using a codeword or other encoding representation based on the alphabet260.

FIG. 8is a flowchart showing a method800for decoding data according to an example implementation. The method800may include the decoder204receiving a sequence of encoded characters (802). The encoded characters may be received as part of a file. The method800may include the match checker232determining whether the encoded character(s) are encoded as a match to previously encoded characters or a match to a stored word and/or transformation (804). If the encoded character(s) is not encoded as a match, then the method800may include the decoder204decoding the encoded character as a single character (806). The encoded character may be decoded as a literal, translating a codeword into a single character, based on the alphabet260stored in the memory206.

If the encoded character(s) is a match, then the distance comparator236may determine whether the encoded characters match a previously decoded word (808). The decoder204may determine whether the encoded data unit matches a previously decoded word by the distance comparator236comparing a received distance value to the window size. If the distance value is less than or equal to the window size, then the distance comparator236, and/or decoder204, may determine that the encoded data unit does match a previously decoded word, and repeat the previously decoded word (810). The string repeater238of the decoder204may repeat the previously decoded word by repeating the sequence of characters that are the distance value previous from a present or current character, for the number of characters equal to a received length value.

If the distance comparator236of the decoder204determines that the encoded characters do not match a previously decoded word, then the decoder204may determine a corpus and/or a transformation (812). The decoder204may determine the corpus and/or a transformation by the corpus selector246selecting the corpus256and/or subcorpus402,404based on the length value, and/or the index selector250may select the transform index502,504based on the length value.

After the word retriever determines the corpus and the transformer248determines the transformation, the divider240may determine the quotient and remainder of the distance value (814). The divider240of the decoder204may determine the quotient242by dividing the distance value by the number of words in the corpus256or subcorpus402,404. The divider240of the decoder204may determine the remainder243by performing a modulo operation, dividing the distance value by the number of words in the corpus256or subcorpus402,404, and determining the remainder243.

The word retriever244of the decoder204may then retrieve the word (816). The word retriever244may retrieve the word by using the remainder243as an index into the corpus256or subcorpus402,404.

The decoder204may then select a transformation (818). The transformer248of the decoder204may select a transformation by using the quotient242as an index into the transformation index502,504and/or transformations258.

After retrieving the word (816) and selecting the transformation (818), the transformer248of the decoder204may perform the selected transformation on the retrieved word (820). The decoder204may perform the selected transformation on the retrieved word by, for example, adding a space after the word, capitalizing a first letter of the word, adding a character, such as ‘s’ to the end of the word, adding a suffix to the end of the word, omitting an indexed character or number of characters from the word (e.g., “Omit1” may indicate omitting the character indexed by 1 or omitting the first character from the word, “Omit5” may indicate omitting the character indexed by 5 from the word or omitting the first five characters from the word), or changing a font of the word.

FIG. 9is a flowchart showing a method900for decompressing data according to an example implementation. The method900may include receiving, via an electronic transmission medium, a compressed sequence of characters, the compressed sequence of characters being represented by at least a first received number (902). The method900may also include dividing the first received number by a number of words in a corpus of words to determine a quotient and a remainder (904). The method900may also include retrieving a word from the corpus of words based on the remainder, the corpus of words being stored on at least one memory device (906). The method900may also include retrieving a transformation from a transformation index based on the quotient, the transformation index being stored on the at least one memory device (908). The method900may also include performing the retrieved transformation on the retrieved word (910). The method900may also include sending representations of characters included the transformed word to a computing device, the representations of characters included in the transformed word being a decompressed version of the received compressed sequence of characters (912).

According to an example embodiment, retrieving the word from the corpus of words may include indexing the corpus of words as an array using the remainder.

According to an example embodiment, the instructions may be further configured to cause the computing system to receive the number via a communication channel.

According to an example embodiment, the instructions may be further configured to cause the computing system to output the transformed word.

According to an example embodiment, the instructions may be further configured to cause the computing system to output the transformed word within a sequence of characters, the sequence of characters including the transformed word and characters that were individually decoded by mapping codewords to characters.

According to an example embodiment, the instructions may be further configured to cause the computing system to output the transformed word within a sequence of characters, the sequence of characters including the transformed word and words that were generated by referencing words that had previously been decoded.

According to an example embodiment, the instructions may be further configured to cause the computing system to select the corpus of words from at least a first corpus of words including words from a first language and a second corpus of words including words from a second language.

According to an example embodiment, the received number may be a first received number, and the instructions may be further configured to cause the computing system to select a subcorpus from multiple subcorpuses included in the corpus of words based on a second received number.

According to an example embodiment, the received number may be a first received number, and the performing the transformation may include performing the transformation on the retrieved word based on the quotient and a second received number.

FIG. 10is a flowchart showing a method1000for decompressing data according to an example implementation. The method1000may include receiving, via an electronic transmission medium, a compressed sequence of characters, the compressed sequence of characters being represented by at least a distance value and a length value (1002). The method1000may include determining whether the distance value exceeds a window size of a window of previously decoded characters, the window of previously decoded characters being stored on at least one memory device (1004). The method1000may include, if the distance value does not exceed the window size, repeating a sequence of previously decoded characters from the window of previously decoded characters with a length based on the length value at a position in the window of previously decoded characters based on the distance value (1006). The method1000may include, if the distance value does exceed the window size, retrieving a word from a corpus of words, the corpus of words being stored on the at least one memory device (1008). The method1000may include sending representations of characters included in the retrieved word to a computing device, the representations of characters included in the retrieved word being a decompressed version of the received compressed sequence of characters (1010).

According to an example embodiment, the distance value may be included in a length/distance pair and the length value is included in the length/distance pair.

According to an example embodiment, the retrieving the word from the corpus of words may include retrieving the word from the corpus of words based on the length value and the distance value.

According to an example embodiment, the retrieving the word from the corpus of words may include determining a subcorpus of the corpus of words based on the length value, determining a remainder by dividing the distance value by a number of words in the subcorpus, and indexing the retrieved word within the subcorpus based on the remainder.

According to an example embodiment, the method1000may further include performing a transformation on the retrieved word.

According to an example embodiment, the method1000may further include performing a transformation on the retrieved word based on the distance value.

According to an example embodiment, the method1000may further include performing a transformation on the retrieved word based on the distance value and a number of words in the corpus of words.

According to an example embodiment, the word may be retrieved from a subcorpus included in the corpus of words, the subcorpus being selected based on the length value.

According to an example embodiment, the method1000may further include performing a transformation on the retrieved word by selecting a subcorpus of the corpus of words based on the length value, determining a quotient of the distance divided by a number of words in the selected subcorpus, and selecting the transformation based on the quotient.

According to an example embodiment, the method1000may further include maintaining a first subcorpus for words in the corpus of words of a first language and a second subcorpus for words in the corpus of words of a second language.

According to an example embodiment, the retrieving the word within the corpus of may include indexing the corpus of words using a remainder based on dividing the distance value by a number of words in the corpus of words.

According to an example embodiment, the method1000may further include selecting a subcorpus from the corpus of words based on the length value, selecting an index of transformations from the at least one memory device based on the length value, and performing a transformation on the retrieved word, the transformation being selected from the selected index of transformations.

According to an example embodiment, the retrieved word may be selected based on a remainder determined by dividing the distance value by a number of words in the subcorpus; and the transformation may selected by indexing the selected index of transformations based on a quotient determined by dividing the distance value by the number of words in the subcorpus.

According to an example embodiment, the corpus of words may store the words in an order based on their frequencies.

FIG. 11is a flowchart showing a method1100for compressing data according to an example implementation. The method1100may include determining whether a sequence of characters matches a word included in a corpus of words or matches a transformed version of the word, the corpus of words being stored in at least one memory device and the transformation performed on the word being stored in the at least one memory device (1102). If the sequence if characters does not match the word included in the corpus of words and is not one transformation away from the word, the method1100may include encoding the sequence of characters as a sequence of codewords (1104). If the sequence of characters matches the word included in the corpus of words, the method1100may include encoding the sequence of characters with a reference to the word (1106). If the sequence of characters matches the transformed version of the word, the method1100may include encoding the sequence of characters with a reference to the word and a reference to the transformation (1108).

According to an example embodiment, the method1100may further include determining whether the sequence of characters matches a previously encoded sequence of characters, and if the sequence of characters does match the previously encoded sequence of characters, encoding the sequence of characters with a reference to the previously encoded sequence of characters.

According to an example embodiment, the reference to the word and the reference to the transformation may include a number based on multiplying a number of words in a corpus by a number associated with the transformation and adding a number associated with the word.

FIG. 12shows an example of a generic computer device1200and a generic mobile computer device1250, which may be used with the techniques described herein. Computing device1200is intended to represent various forms of digital computers, such as laptops, desktops, workstations, personal digital assistants, servers, blade servers, mainframes, and other appropriate computers. Computing device1250is intended to represent various forms of mobile devices, such as personal digital assistants, cellular telephones, smart phones, and other similar computing devices. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

Computing device1200includes a processor1202, memory1204, a storage device1206, a high-speed interface1208connecting to memory1204and high-speed expansion ports1210, and a low speed interface1212connecting to low speed bus1214and storage device1206. Each of the components1202,1204,1206,1208,1210, and1212, are interconnected using various busses, and may be mounted on a common motherboard or in other manners as appropriate. The processor1202can process instructions for execution within the computing device1200, including instructions stored in the memory1204or on the storage device1206to display graphical information for a GUI on an external input/output device, such as display1216coupled to high speed interface1208. In other implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices1200may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system).

The memory1204stores information within the computing device1200. In one implementation, the memory1204is a volatile memory unit or units. In another implementation, the memory1204is a non-volatile memory unit or units. The memory1204may also be another form of computer-readable medium, such as a magnetic or optical disk.

The storage device1206is capable of providing mass storage for the computing device1200. In one implementation, the storage device1206may be or contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. A computer program product can be tangibly embodied in an information carrier. The computer program product may also contain instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory1204, the storage device1206, or memory on processor1202.

The high speed controller1208manages bandwidth-intensive operations for the computing device1200, while the low speed controller1212manages lower bandwidth-intensive operations. Such allocation of functions is exemplary only. In one implementation, the high-speed controller1208is coupled to memory1204, display1216(e.g., through a graphics processor or accelerator), and to high-speed expansion ports1210, which may accept various expansion cards (not shown). In the implementation, low-speed controller1212is coupled to storage device1206and low-speed expansion port1214. The low-speed expansion port, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet) may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

The computing device1200may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server1220, or multiple times in a group of such servers. It may also be implemented as part of a rack server system1224. In addition, it may be implemented in a personal computer such as a laptop computer1222. Alternatively, components from computing device1200may be combined with other components in a mobile device (not shown), such as device1250. Each of such devices may contain one or more of computing device1200,1250, and an entire system may be made up of multiple computing devices1200,1250communicating with each other.

Computing device1250includes a processor1252, memory1264, an input/output device such as a display1254, a communication interface1266, and a transceiver1268, among other components. The device1250may also be provided with a storage device, such as a microdrive or other device, to provide additional storage. Each of the components1250,1252,1264,1254,1266, and1268, are interconnected using various buses, and several of the components may be mounted on a common motherboard or in other manners as appropriate.

The processor1252can execute instructions within the computing device1250, including instructions stored in the memory1264. The processor may be implemented as a chipset of chips that include separate and multiple analog and digital processors. The processor may provide, for example, for coordination of the other components of the device1250, such as control of user interfaces, applications run by device1250, and wireless communication by device1250.

Processor1252may communicate with a user through control interface1258and display interface1256coupled to a display1254. The display1254may be, for example, a TFT LCD (Thin-Film-Transistor Liquid Crystal Display) or an OLED (Organic Light Emitting Diode) display, or other appropriate display technology. The display interface1256may comprise appropriate circuitry for driving the display1254to present graphical and other information to a user. The control interface1258may receive commands from a user and convert them for submission to the processor1252. In addition, an external interface1262may be provide in communication with processor1252, so as to enable near area communication of device1250with other devices. External interface1262may provide, for example, for wired communication in some implementations, or for wireless communication in other implementations, and multiple interfaces may also be used.

The memory1264stores information within the computing device1250. The memory1264can be implemented as one or more of a computer-readable medium or media, a volatile memory unit or units, or a non-volatile memory unit or units. Expansion memory1274may also be provided and connected to device1250through expansion interface1272, which may include, for example, a SIMM (Single In Line Memory Module) card interface. Such expansion memory1274may provide extra storage space for device1250, or may also store applications or other information for device1250. Specifically, expansion memory1274may include instructions to carry out or supplement the processes described above, and may include secure information also. Thus, for example, expansion memory1274may be provide as a security module for device1250, and may be programmed with instructions that permit secure use of device1250. In addition, secure applications may be provided via the SIMM cards, along with additional information, such as placing identifying information on the SIMM card in a non-hackable manner.

The memory may include, for example, flash memory and/or NVRAM memory, as discussed below. In one implementation, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory1264, expansion memory1274, or memory on processor1252, that may be received, for example, over transceiver1268or external interface1262.

Device1250may communicate wirelessly through communication interface1266, which may include digital signal processing circuitry where necessary. Communication interface1266may provide for communications under various modes or protocols, such as GSM voice calls, SMS, EMS, or MMS messaging, CDMA, TDMA, PDC, WCDMA, CDMA2000, or GPRS, among others. Such communication may occur, for example, through radio-frequency transceiver1268. In addition, short-range communication may occur, such as using a Bluetooth, WiFi, or other such transceiver (not shown). In addition, GPS (Global Positioning System) receiver module1270may provide additional navigation- and location-related wireless data to device1250, which may be used as appropriate by applications running on device1250.

The computing device1250may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a cellular telephone1280. It may also be implemented as part of a smart phone1282, personal digital assistant, or other similar mobile device.