1.3: Exchanging data:
Lossy v. lossless compression:
● Lossy compression:
○ Data is lost in the process to reduce file size which reduces quality.
○ Suitable for images, audio and video files. E.G: JPEG and MP3.
● Lossless compression:
○ No data is lost and the original file can be recreated when the file is
uncompressed.
○ Suitable for executable files and documents. E.G: PNG and Zip.
Lossless compression:
● Dictionary coding:
○ Dictionary coding works by building an index that we visualise as a table.
○ Every data item or entry(such as a word or letter) in the file is recorded,
along with an indexed reference or unique code.
○ The compressed file will consist of:
■ The dictionary index
■ The sequence of occurrences needed to recreate the original file
● Run length encoding:
○ Run length encoding works by finding runs of repeated binary patterns and
replacing them with a single instance of the pattern and a number that
specifies how many times the pattern is repeated.
○ Run-length encoding is ideal for compressing bitmap images. Bitmap
images are made up of discrete pixels.
○ E.g: with two colours, we can encode an image with a colour depth of 1 bit
(0 for white and 1 for black). This can be compressed by storing a single
colour code, followed by the number of times that the colour is repeated.
Encryption:
● Plaintext of a message sent is encrypted using a cipher algorithm and key into the
equivalent ciphertext.
● When received, the ciphertext is decrypted back to plaintext using the same or
different key.
● Symmetric encryption:
○ Symmetric encryption is also known as ‘private key encryption’.
○ The same key is used to encrypt and decrypt data.
○ This means that the key must also be transferred to the recipient.
○ Security problems:
■ The key can be intercepted as easily as the ciphertext message.
■ For this reason, asymmetric encryption may be used instead.
● Asymmetric encryption:
○ This uses two but related keys.
○ One key, known as the public key, is made public so that others wishing to
send you data can use this key to encrypt it:
■ The public key cannot decrypt the data.
■ A private key, known only to you, is used to decrypt the data.
Hashing:
, ● A hash function is an algorithm that converts a hash key to a hash value. The
function provides a mapping between an arbitrary length input and a usually fixed
length or smaller output.
● It is one-way; you cannot get back to the original.
● This is useful for storing encrypted PINs and passwords so that they cannot be
read by a hacker. To verify a user’s password, the software applies the hash
function to the user input and compares the hashed result with the one stored.
● The main requirements of a hash function are that it must:
○ Always produce the same hash value for the same key.
○ Provide a uniform distribution of hash values. This means that every value
has an equal probability of being generated.
○ Minimise clustering; this will arise when many different keys produce the
same hash value. Where two or more different keys produce the same
Hash value, we say a ‘collision’ has occurred.
○ Be very fast to compute.
● Rehashing:
○ Over time, items will be added/deleted from the hash table. If the hash table
starts to fill up, or a large number of items are in the wrong place, the
performance of the hash table will degrade. Rehashing is used to address
this problem.
○ When you rehash, a new hash table is created (larger if needed). The key
for each item in the existing table will be rehashed and the item will be
inserted into the new hash table. If the new table is larger the hashing
algorithm will need to be modified as it will need to generate a larger range
of hash values. Rehashing is also an opportunity to review the overall
effectiveness of the hash function and to review how collisions are handled.
Database concepts:
● Relational database:
○ A database where the data is held in more than one table, and the tables
are linked together using relationships.
● Flat file:
○ A database where all the data is stored in a single table. This type of
database can be sufficient if there is only a small amount of data and useful
when data is mostly static (it doesn't change frequently).
○ Most databases deal with a large amount of data that is dynamic, and so
they need to provide a centralised and automated way of manipulating
data.
● Keys:
○ Primary Key: A unique identifier for every value in a table
○ Secondary Key: One or more of these keys can be indexed. This is usually
done for fields that are often used as search criteria.
○ Foreign Key: A key that links one table to another through the external
table’s primary key
○ Composite Key: A combination of two or more fields in a table that can be
used to uniquely identify each record.
● Indexing:
○ The database automatically maintains an index of primary keys so that a
specific primary key can be located quickly and easily. The index provides
the position of each record according to its primary key (and secondary key
if applicable). This makes retrieval of records references by the index much
quicker, as items do not need to be searched sequentially but it takes more
space in the database.
● Entity relationship modelling:
Lossy v. lossless compression:
● Lossy compression:
○ Data is lost in the process to reduce file size which reduces quality.
○ Suitable for images, audio and video files. E.G: JPEG and MP3.
● Lossless compression:
○ No data is lost and the original file can be recreated when the file is
uncompressed.
○ Suitable for executable files and documents. E.G: PNG and Zip.
Lossless compression:
● Dictionary coding:
○ Dictionary coding works by building an index that we visualise as a table.
○ Every data item or entry(such as a word or letter) in the file is recorded,
along with an indexed reference or unique code.
○ The compressed file will consist of:
■ The dictionary index
■ The sequence of occurrences needed to recreate the original file
● Run length encoding:
○ Run length encoding works by finding runs of repeated binary patterns and
replacing them with a single instance of the pattern and a number that
specifies how many times the pattern is repeated.
○ Run-length encoding is ideal for compressing bitmap images. Bitmap
images are made up of discrete pixels.
○ E.g: with two colours, we can encode an image with a colour depth of 1 bit
(0 for white and 1 for black). This can be compressed by storing a single
colour code, followed by the number of times that the colour is repeated.
Encryption:
● Plaintext of a message sent is encrypted using a cipher algorithm and key into the
equivalent ciphertext.
● When received, the ciphertext is decrypted back to plaintext using the same or
different key.
● Symmetric encryption:
○ Symmetric encryption is also known as ‘private key encryption’.
○ The same key is used to encrypt and decrypt data.
○ This means that the key must also be transferred to the recipient.
○ Security problems:
■ The key can be intercepted as easily as the ciphertext message.
■ For this reason, asymmetric encryption may be used instead.
● Asymmetric encryption:
○ This uses two but related keys.
○ One key, known as the public key, is made public so that others wishing to
send you data can use this key to encrypt it:
■ The public key cannot decrypt the data.
■ A private key, known only to you, is used to decrypt the data.
Hashing:
, ● A hash function is an algorithm that converts a hash key to a hash value. The
function provides a mapping between an arbitrary length input and a usually fixed
length or smaller output.
● It is one-way; you cannot get back to the original.
● This is useful for storing encrypted PINs and passwords so that they cannot be
read by a hacker. To verify a user’s password, the software applies the hash
function to the user input and compares the hashed result with the one stored.
● The main requirements of a hash function are that it must:
○ Always produce the same hash value for the same key.
○ Provide a uniform distribution of hash values. This means that every value
has an equal probability of being generated.
○ Minimise clustering; this will arise when many different keys produce the
same hash value. Where two or more different keys produce the same
Hash value, we say a ‘collision’ has occurred.
○ Be very fast to compute.
● Rehashing:
○ Over time, items will be added/deleted from the hash table. If the hash table
starts to fill up, or a large number of items are in the wrong place, the
performance of the hash table will degrade. Rehashing is used to address
this problem.
○ When you rehash, a new hash table is created (larger if needed). The key
for each item in the existing table will be rehashed and the item will be
inserted into the new hash table. If the new table is larger the hashing
algorithm will need to be modified as it will need to generate a larger range
of hash values. Rehashing is also an opportunity to review the overall
effectiveness of the hash function and to review how collisions are handled.
Database concepts:
● Relational database:
○ A database where the data is held in more than one table, and the tables
are linked together using relationships.
● Flat file:
○ A database where all the data is stored in a single table. This type of
database can be sufficient if there is only a small amount of data and useful
when data is mostly static (it doesn't change frequently).
○ Most databases deal with a large amount of data that is dynamic, and so
they need to provide a centralised and automated way of manipulating
data.
● Keys:
○ Primary Key: A unique identifier for every value in a table
○ Secondary Key: One or more of these keys can be indexed. This is usually
done for fields that are often used as search criteria.
○ Foreign Key: A key that links one table to another through the external
table’s primary key
○ Composite Key: A combination of two or more fields in a table that can be
used to uniquely identify each record.
● Indexing:
○ The database automatically maintains an index of primary keys so that a
specific primary key can be located quickly and easily. The index provides
the position of each record according to its primary key (and secondary key
if applicable). This makes retrieval of records references by the index much
quicker, as items do not need to be searched sequentially but it takes more
space in the database.
● Entity relationship modelling:
