System and method for applying an efficient data compression scheme to URL parameters
Disclosed is a system and methods for data compression and decompression. The systems and methods discussed herein include an encoder, dictionary, decoder, literal string and control output. The discussed systems and methods encode data transmitted over a communications channel through the use of a dynamically compiled dictionary. Upon reviewing the characters within the transmitted data in view of the dictionary, an encoded/compressed output string is created. Such output string may also be decoded in a similar fashion via a dynamically compiled dictionary.
1. A method comprising:
receiving, at a computing device, an input data string, the input data string comprising a plurality characters;
initializing, via the computing device, a dictionary with a plurality of characters based in part upon the input data string; and
encoding the input data string based in part upon the dictionary, said encoding comprises:
comparing, via the computing device, the characters of the input data string with the characters of the dictionary, said comparing comprising sequentially traversing the input data string and the dictionary, and comparing each character in the input data string with each dictionary character;
identifying, via the computing device, a first string, said first string identified by determining a match between at least one consecutive character in the input data string and at least one character in the dictionary;
writing, via the computing device, the first string to a control output string;
identifying, via the computing device, a second string, said second string comprising at least one consecutive character in the input data string not present within the dictionary;
writing, via the computing device, the second string to a literal output string; and
generating, via the computing device, an encoded output string based on the control output string and the literal output string.
2. The method of claim 1 , wherein writing the first string to the control output string comprises:
converting the first string to a first alpha-numeric representation, said first alpha-numeric representation comprises a first number and a second number, said first number representing the number of characters from the end of the dictionary from where the first string was identified, said second number representing the length of the first string; and
writing the first string to the control output string based on said first alpha-numeric representation.
3. The method of claim 2 , further comprising:
determining the length of the first string;
wherein if the length of the first string is less than 3 characters, individually writing each character in the first string to the dictionary, said writing each character comprises appending each character to the dictionary; and
wherein if the length of the first string is at least 3 characters, writing the number of characters in the first string to the literal output string and writing the characters in the first string to the control output string.
4. The method of claim 2 , wherein writing the second character to the literal output string comprises:
converting the second string to a second alpha-numeric representation, said second alpha-numeric representation comprises a number of characters in the second string; and
writing the second string to the control output string based on the second alpha-numeric representation, wherein said second alpha-numeric representation is prepended to the first alpha-numeric representation in the control output string.
5. The method of claim 1 , wherein said encoding is repeated until all of the characters in the input data string have been compared against the dictionary.
6. The method of claim 1 , further comprising:
appending the literal output string to the dictionary;
appending the control output string to the dictionary, said control output string is appended to the appended literal output string within the updated dictionary, wherein upon repetition of said encoding, the updated dictionary is utilized for subsequent comparisons against remaining characters in the input data string that have yet to be compared against the dictionary, said subsequent comparisons occur until all of the characters in the input data string have been compared against the dictionary.
7. The method of claim 6 , wherein the dictionary is initialized based upon expected characters comprised within the input data string, the dictionary comprising 128 characters, wherein upon the dictionary growing in length, if the dictionary length exceeds 128 characters, a first character in the dictionary is removed for every character appended to the dictionary.
8. The method of claim 6 , wherein generating the encoded output string comprises:
reversing the order of the literal output string; and
appending the reversed literal output string to the control output string.
9. The method of claim 1 , wherein the input data string is a URL.
10. The method of claim 1 , wherein the control output string comprises 82 legal and unambiguous alpha-numeric characters.
11. The method of claim 8 , wherein the encoded output string is read during decoding.
12. A non-transitory computer-readable storage medium tangibly encoded with computer executable instructions, that when executed by a processor associated with a computing device, perform a method comprising:
receiving an input data string, the input data string comprising a plurality characters;
initializing a dictionary with a plurality of characters based in part upon the input data string; and
encoding the input data string based in part upon the dictionary, said encoding comprises:
comparing the characters of the input data string with the characters of the dictionary, said comparing comprising sequentially traversing the input data string and the dictionary, and comparing each character in the input data string with each dictionary character;
identifying, a first string, said first string identified by determining a match between at least one consecutive character in the input data string and at least one character in the dictionary;
writing the first string to a control output string;
identifying a second string, said second string comprising at least one consecutive character in the input data string not present within the dictionary;
writing the second string to a literal output string; and
generating an encoded output string based on the control output string and the literal output string.
13. The non-transitory computer-readable storage medium of claim 12 , wherein writing the first string to the control output string comprises:
converting the first string to a first alpha-numeric representation, said first alpha-numeric representation comprises a first number and a second number, said first number representing the number of characters from the end of the dictionary from where the first string was identified, said second number representing the length of the first string; and
writing the first string to the control output string based on said first alpha-numeric representation.
14. The non-transitory computer-readable storage medium of claim 13 , further comprising:
determining the length of the first string;
wherein if the length of the first string is less than 3 characters, individually writing each character in the first string to the dictionary, said writing each character comprises appending each character to the dictionary; and
wherein if the length of the first string is at least 3 characters, writing the number of characters in the first string to the literal output string and writing the characters in the first string to the control output string.
15. The non-transitory computer-readable storage medium of claim 13 , wherein writing the second character to the literal output string comprises:
converting the second string to a second alpha-numeric representation, said second alpha-numeric representation comprises a number of characters in the second string; and
writing the second string to the control output string based on the second alpha-numeric representation, wherein said second alpha-numeric representation is prepended to the first alpha-numeric representation in the control output string.
16. The non-transitory computer-readable storage medium of claim 12 , wherein said encoding is repeated until all of the characters in the input data string have been compared against the dictionary.
17. The non-transitory computer-readable storage medium of claim 12 , further comprising:
appending the literal output string to the dictionary;
appending the control output string to the dictionary, said control output string is appended to the appended literal output string within the updated dictionary, wherein upon repetition of said encoding, the updated dictionary is utilized for subsequent comparisons against remaining characters in the input data string that have yet to be compared against the dictionary, said subsequent comparisons occur until all of the characters in the input data string have been compared against the dictionary.
18. The non-transitory computer-readable storage medium of claim 17 , wherein generating the encoded output string comprises:
reversing the order of the literal output string; and
appending the reversed literal output string to the control output string.
19. A system comprising:
a processor;
a non-transitory computer-readable storage medium for tangibly storing thereon program logic for execution m logic comprising:
receiving logic executed by the processor for receiving an input data string, the input data string comprising a plurality characters;
initializing logic executed by the processor for initializing a dictionary with a plurality of characters based in part upon the input data string; and
encoding logic executed by the processor for encoding the input data string based in part upon the dictionary, said encoding comprises:
comparing logic executed by the processor for comparing the characters of the input data string with the characters of the dictionary, said comparing comprising sequentially traversing the input data string and the dictionary, and comparing each character in the input data string with each dictionary character;
identifying logic executed by the processor for identifying, a first string, said first string identified by determining a match between at least one consecutive character in the input data string and at least one character in the dictionary;
writing logic executed by the processor for writing the first string to a control output string;
identifying logic executed by the processor for identifying a second string, said second string comprising at least one consecutive character in the input data string not present within the dictionary;
writing logic executed by the processor for writing the second string to a literal output string; and
generating logic executed by the processor for generating an encoded output string based on the control output string and the literal output string.