Sorted sliding window compression

Summary form only given. Sorted sliding window compression (SSWC) uses a new model (sorted sliding window model, SSWM) to encode strings efficiently, which appear again while encoding a symbol sequence. The SSWM holds statistics of all strings up to a certain length k in a sliding window of size n. The compression program can use the SSWM to determine if the string of the next symbols are already contained in the sliding window and returns the length of match. SSWM gives directly statistics (borders of subinterval in an interval) for use in entropy encoding methods like arithmetic coding or dense coding. For a given number in an interval and string length the SSWM gives back the corresponding string which is used in decompressing. After an encoding (decoding) step the model is updated with the just encoded (decoded) characters. The model sorts all string starting points in the sliding window lexicographically. A simple way to implement the SSWM is by exhaustive search in the sliding window. An implementation with a B-tree together with special binary searches is used here. SSWC is a simple compression scheme, which uses this new model to evaluate its properties. It looks on the next characters to encode and determines the longest match with the SSWM. If the match is smaller than 2, the character is encoded. Otherwise the length and the subinterval of the string are encoded. The length values are encoded together with the single characters by using the same adaptive frequency model. Additionally some rules are used to reduce the matching length if the code length gets worse. Encoding of frequencies and intervals is done with dense coding