In today’s data-driven world, efficient storage and transmission of information are more critical than ever. Lossless compression techniques play a pivotal role in achieving this efficiency by reducing data size without compromising its integrity. Unlike lossy compression, which sacrifices some data to achieve higher compression rates, lossless methods ensure that the original data can be perfectly reconstructed from its compressed form. This makes lossless compression ideal for applications where data accuracy is paramount, such as text files, computer programs, executables, and databases.
In this blog post, we will focus on two fundamental lossless compression techniques: dictionary encoding and run-length encoding. By implementing these methods in Python, we will demonstrate their effectiveness in compressing a list of colours representing the different Lego bricks needed to build a colourful Lego tower.
Dictionary Encoding
Dictionary encoding, also known as substitution encoding, replaces recurring elements with shorter codes or symbols. This technique is effective when the data contains many repetitions. For our LEGO tower, we can use dictionary encoding to replace frequently occurring colours with shorter identifiers as follows:
Run-Length Encoding
Run-length encoding (RLE) is a simple form of data compression where consecutive elements (runs) are stored as a single data value and count. This technique is particularly effective for data with many consecutive repetitions. In our Lego tower, RLE can compress sequences of the same colour into a more compact form:
Combing Dictionary Encoding and Run-Length Encoding
By combining both lossless compression methods it may be possible to reach a higher compression rate, still without losing any data (lossless compression)!
Lossless Compression Algorithms, using Python!
Let’s use our Python skills to implement the two lossless compression techniques described above. To fully understand the code provided below, you will need a good understanding of how lists, dictionaries (a.k.a. hash tables) and tuples work in Python. You may first notice the use of square brackets [] in Python for storing data in a list, the use of curly brackets {} for storing pairs of key:value in a dictionary and the use of standard brackets () to store data in a tuple.
Use the tabs below to investigate how we have implemented our compression algorithms to compress our list of Lego brick colours.
# Dictionary Encoding
def dictionary_encoding(data):
compressedData = []
dictionary = {}
reversedDictionary = {}
for value in data:
if value not in reversedDictionary:
key = value[0] # e.g. "Y" for "Yellow"
dictionary[key] = value # "Y":"Yellow"
reversedDictionary[value] = key # "Yellow":"Y"
compressedData.append(key) # "Y"
else:
key = reversedDictionary[value]
compressedData.append(key)
return compressedData, dictionary
data = ["Yellow","Yellow","Yellow","Red","Red","Blue","Blue","Blue","Green","Red"]
print(">>> Original Data (Before compression)")
print(data)
print("")
compressedData, dictionary = dictionary_encoding(data)
print(compressedData)
print(dictionary)
# Run-Length Encoding
def run_length_encoding(data):
compressedData = []
currentKey = data[0]
counter = 1
for i in range(1,len(data)):
if data[i]==currentKey:
counter+=1
else:
compressedData.append((currentKey,counter))
counter=1
currentKey = data[i]
compressedData.append((currentKey,counter))
return compressedData
data = ["Yellow","Yellow","Yellow","Red","Red","Blue","Blue","Blue","Green","Red"]
print(">>> Original Data (Before compression)")
print(data)
print("")
compressedData = run_length_encoding(data)
print(compressedData)
# Lossless Compression Algorithms using Python - www.101computing.net/lossless-compression-algorithms-using-python
# Dictionary Encoding
def dictionary_encoding(data):
compressedData = []
dictionary = {}
reversedDictionary = {}
for value in data:
if value not in reversedDictionary:
key = value[0] # e.g. "Y" for "Yellow"
dictionary[key] = value # "Y":"Yellow"
reversedDictionary[value] = key # "Yellow":"Y"
compressedData.append(key) # "Y"
else:
key = reversedDictionary[value]
compressedData.append(key)
return compressedData, dictionary
# Run-Length Encoding
def run_length_encoding(data):
compressedData = []
currentKey = data[0]
counter = 1
for i in range(1,len(data)):
if data[i]==currentKey:
counter+=1
else:
compressedData.append((currentKey,counter))
counter=1
currentKey = data[i]
compressedData.append((currentKey,counter))
return compressedData
# Combining Both Lossless Compression Techniques
def lossless_compression(data):
print(" >>> Step 1: Dictionary Encoding")
compressedData, dictionary = dictionary_encoding(data)
print(" > Compressed Data:")
print(compressedData)
print(" > Dictionary:")
print(dictionary)
print("")
print(" >>> Step 2: Run-Length Encoding")
fullyCompressedData = run_length_encoding(compressedData)
print(" > Fully Compressed Data:")
print(fullyCompressedData)
data = ["Yellow","Yellow","Yellow","Red","Red","Blue","Blue","Blue","Green","Red"]
print(">>> Original Data (Before compression)")
print(data)
print("")
lossless_compression(data)
Try it online…
You can now test these functions using the code provided below…
Python Challenge
Your Python challenge is to write an algorithm to decompress data using a list of compressed data and a given dictionary, your python code will need to reconstruct the original data:
Solution...
The solution for this challenge is available to full members!Find out how to become a member:
➤ Members' Area
The aim of this first challenge is to write a Python function that asks the user for the current month and displays all the crops that can be planted in that month.
Reusing similar code to the code provided to solve challenge 1, write another function Python function that asks the user for the current month and displays all the crops that can be harvested in that month.
Some gardeners have limited space and need to grow crops in pots. Write a function that lists all crops that can be grown in containers.
Modify your program to ask the user about their soil type and sunlight conditions and then recommend crops that match their garden environment.
Enhance your program by allowing users to search for a specific crop and view detailed growing advice, including watering needs and best companion plants.
One of the main purpose of the Operating System is to control the hardware and more specifically the CPU. The CPU performs all the jobs/processes requested by the different applications. A scheduler is a program of the Operating System that manages the amount of time that is allocated to each job that the CPU needs to process. To do so the scheduler keeps a list of all the jobs that need to be processed. This is called the job queue. The scheduler also uses a scheduling algorithm to determine in which order these jobs will be processed and the amount of processing time to allocate to each job.
LMC Simulator
Logic Gates Circuits
Network Designer
Flowchart Studio
Online Python IDE