# This function is used in the Lz78 algorithm.
def longest_common_substring(s1, s2):
# go along the first string and search for the longest match
maxLongest = 0
offset = 0
for i in range(0, len(s1)):
longest = 0
if ((i == len(s1) - len(s2) - 2)):
break
for j in range(0, len(s2)):
if (i+j < len(s1)):
if s1[i+j] == s2[j]:
longest = longest + 1
if (maxLongest < longest):
maxLongest = longest
offset = i
else:
break
else:
break
return maxLongest, offset
def compress_lz77(text, ws):
'''
Parameters:
text
ws: window size
Returns:
ouput: tuple list the compression
'''
ws = int(ws)
matches = 0
output = []
for i in range(0, len(text)):
# Skip many iterations as matches
if matches > 0:
matches = matches - 1
continue
# Search window
if len(text[:i]) > ws:
window = text[i - ws:i]
else:
window = text[:i]
# Largest prefix
prefix = text[i]
while True:
if prefix in window:
matches = matches + 1
aux = prefix
# check next prefix
prefix = text[i:i + matches + 1]
# special case last char
if aux == prefix:
prefix = prefix + '_'
break
else:
break
# Output
if matches == 0:
offset = 0
length = 0
symbol = prefix
else:
length = len(prefix) - 1 # prefix is the last checked that didn't match
symbol = prefix[length]
prefix = prefix[:-1] # correct prefix
offset = i - window.rfind(prefix) - (i - len(window))
output.append((offset, length, symbol))
return output
def decompress_lz77(tuples):
'''
Parameters:
tuples: compress output
Returns:
decoded: original text
'''
decoded = ""
for i in range(0, len(tuples)):
if tuples[i][0] == 0:
# Add new patterns
decoded += tuples[i][2]
else:
offset = tuples[i][0]
length = tuples[i][1]
symbol = tuples[i][2]
j = len(decoded)
# Add repeated patterns
rep = decoded[j - offset:j - offset + length]
decoded += rep
# Final text special case
if symbol != "_":
decoded += symbol
return decoded
def compress_lz78(text):
dictionary = dict()
i = 0
index = 1
encodedNumbers = []
encodedLetters = []
while i < len(text):
stringToBeSaved = text[i]
indexInDictionary = 0
while stringToBeSaved in dictionary:
indexInDictionary = dictionary[stringToBeSaved]
if (i == len(text) - 1):
stringToBeSaved = " "
break
i = i + 1
stringToBeSaved = stringToBeSaved + text[i]
#print ("<{0}, {1}>".format(indexInDictionary, stringToBeSaved[len(stringToBeSaved) - 1]))
encodedNumbers.append(indexInDictionary)
encodedLetters.append(stringToBeSaved[len(stringToBeSaved) - 1])
if (stringToBeSaved not in dictionary):
dictionary[stringToBeSaved] = index
index = index + 1
i = i + 1
return encodedNumbers, encodedLetters, dictionary
def decompress_lz78(encodedNumbers, encodedLetters, dictionary):
decoded = ""
i = 0
while i < len(encodedNumbers):
if (encodedNumbers[i] != 0):
decoded += str(list(dictionary.keys())[list(dictionary.values()).index(encodedNumbers[i])])
decoded+=(encodedLetters[i])
i = i+1
return decoded
# Initialize global variable for lz77 algorithm
index_compress_lz77 = 0
index_decompress_lz77 = 0
data_original_lz77 = "tipp tap tipp tap tippe tippe tipp tap"
data_compressed_lz77 = compress_lz77(data_original_lz77,len(data_original_lz77))
data_decompressed_lz77 = decompress_lz77(data_compressed_lz77)
# Initialize global variable for lz78 algorithm
index_compress_lz78 = 0
index_decompress_lz78 = 0
data_original_lz78 = "tipp tap tipp tap tippe tippe tipp tap"
data_compressed_lz78=[]
[encodedNumbers, encodedLetters, dictionary]=compress_lz78(data_original_lz78)
for i in range(len(encodedNumbers)):
data_compressed_lz78.append([encodedNumbers[i], encodedLetters[i]])
data_decompressed_lz78 = decompress_lz78(encodedNumbers, encodedLetters, dictionary)
# Functions for the Lz77 compress
def get_compress_input_lz77(*args, **kwargs):
global index_compress_lz77, data_original_lz77, data_compressed_lz77
data_original_lz77 = Element("data_original_input_lz77").element.value
data_compressed_lz77 = compress_lz77(data_original_lz77,len(data_original_lz77))
index_compress_lz77 = 0
pyscript.write("data_compressed_lz77", data_compressed_lz77[:index_compress_lz77])
def button_compress_previous_lz77(condition):
global index_compress_lz77
index_compress_lz77 -= 1
index_compress_lz77 = index_compress_lz77 % len(data_compressed_lz77)
pyscript.write("data_compressed_lz77", data_compressed_lz77[:index_compress_lz77+1])
def button_compress_next_lz77(condition):
global index_compress_lz77
index_compress_lz77 += 1
index_compress_lz77 = index_compress_lz77 % len(data_compressed_lz77)
pyscript.write("data_compressed_lz77", data_compressed_lz77[:index_compress_lz77+1])
# Functions for the Lz78 compress
def get_compress_input_lz78(*args, **kwargs):
global index_compress_lz78, data_original_lz78, data_compressed_lz78,encodedNumbers,encodedLetters, dictionary
data_original_lz78 = Element("data_original_input_lz78").element.value
data_compressed_lz78=[]
[encodedNumbers, encodedLetters, dictionary]=compress_lz78(data_original_lz78)
for i in range(len(encodedNumbers)):
data_compressed_lz78.append([encodedNumbers[i], encodedLetters[i]])
index_compress_lz78 = 0
pyscript.write("data_compressed_lz78", data_compressed_lz78[:index_compress_lz78])
def button_compress_previous_lz78(condition):
global index_compress_lz78,encodedNumbers
index_compress_lz78 -= 1
index_compress_lz78 = index_compress_lz78 % len(encodedNumbers)
pyscript.write("data_compressed_lz78", data_compressed_lz78[:index_compress_lz78+1])
def button_compress_next_lz78(condition):
global index_compress_lz78
index_compress_lz78 += 1
index_compress_lz78 = index_compress_lz78 % len(data_compressed_lz78)
pyscript.write("data_compressed_lz78", data_compressed_lz78[:index_compress_lz78+1])
# Functions for the Lz77 decompress
def get_decompress_input_lz77(*args, **kwargs):
global index_decompress_lz77, data_compressed_lz77, data_decompressed_lz77
data_compressed_lz77 = eval(Element("data_compressed_input_lz77").element.value)
index_decompress_lz77 = -1
data_decompressed_lz77 = " "
pyscript.write("data_decompressed_lz77", " ")
def button_decompress_previous_lz77(condition):
global index_decompress_lz77, data_decompressed_lz77
index_decompress_lz77 -= 1
index_decompress_lz77 = index_decompress_lz77 % len(data_compressed_lz77)
data_decompressed_lz77 = decompress_lz77(data_compressed_lz77[:index_decompress_lz77 + 1])
pyscript.write("data_decompressed_lz77", data_decompressed_lz77)
def button_decompress_next_lz77(condition):
global index_decompress_lz77, data_decompressed_lz77
index_decompress_lz77 += 1
index_decompress_lz77 = index_decompress_lz77 % len(data_compressed_lz77)
data_decompressed_lz77 = decompress_lz77(data_compressed_lz77[:index_decompress_lz77 + 1])
pyscript.write("data_decompressed_lz77", data_decompressed_lz77)
# Functions for the Lz78 decompress
def get_decompress_input_lz78(*args, **kwargs):
global index_decompress_lz78, data_compressed_lz78, data_decompressed_lz78
data_compressed_lz78 = eval(Element("data_compressed_input_lz78").element.value)
index_decompress_lz78 = 0
data_decompressed_lz78 = " "
pyscript.write("data_decompressed_lz78", " ")
def button_decompress_previous_lz78(condition):
global index_decompress_lz78, data_decompressed_lz78,encodedNumbers, encodedLetters, dictionary
index_decompress_lz78 -= 1
index_decompress_lz78 = index_decompress_lz78 % len(encodedNumbers)
data_decompressed_lz78 = decompress_lz78(encodedNumbers[:index_decompress_lz78 + 1], encodedLetters[:index_decompress_lz78 + 1], dictionary)
pyscript.write("data_decompressed_lz78", data_decompressed_lz78)
def button_decompress_next_lz78(condition):
global index_decompress_lz78, data_decompressed_lz78,encodedNumbers, encodedLetters, dictionary
index_decompress_lz78 += 1
index_decompress_lz78 = index_decompress_lz78 % len(encodedNumbers)
data_decompressed_lz78 = decompress_lz78(encodedNumbers[:index_decompress_lz78 + 1], encodedLetters[:index_decompress_lz78 + 1], dictionary)
pyscript.write("data_decompressed_lz78", data_decompressed_lz78)
Element("data_original_input_lz77").element.value = data_original_lz77
Element("data_compressed_input_lz77").element.value = [(0, 0, 't'), (0, 0, 'i'), (0, 0, 'p'), (1, 1, ' '), (5, 1, 'a'), (4, 3, 'i'), (9, 9, 'p'), (1, 1, 'e'), (6, 6, ' '), (21, 8, '_')]
Element("data_original_input_lz78").element.value = data_original_lz78
Element("data_compressed_input_lz78").element.value = [[0, 't'], [0, 'i'], [0, 'p'], [3, ' '], [1, 'a'], [4, 't'], [2, 'p'], [6, 'a'], [6, 'i'], [3, 'p'], [0, 'e'], [0, ' '], [1, 'i'], [10, 'e'], [12, 't'], [7, 'p'], [15, 'a'], [3, ' ']]