compression, encryption and hashing

Compression

• Compression is the process used to reduce the storage space required by a file, meaning you can store more files with the same amount of storage space.

• Compression is particularly important for sharing files over networks or the Internet.

• The larger a file, the longer it takes to transfer and so compressing files increases the number of files that can be transferred in a given time

lossy compression

• reduces the size of a file while also removing some of its information.

• This could result in a more pixelated image or less clear audio recording.

lossless compression

• reduces the size of a file without losing any information.

• the original file can be recovered from the compressed version

run length encoding

• method of lossless compression

• repeated values are removed and replaced with one occurrence of the data followed by the number of times it should be repeated.

• For example, the string AAAAAABBBBBCCC could be represented as A6B5C3.

• In order to work well, run length encoding relies on consecutive pieces of data being the same, if there’s little repetition, run length encoding doesn’t offer a great reduction in file size.

dictionary encoding

• method of lossless compression

• Frequently occurring pieces of data are replaced with an index and compressed data is stored alongside a dictionary which matches the frequently occurring data to an index.

• The original data can then be restored using the dictionary.

encryption def

used to keep data secure when it’s being transmitted

Symmetric Encryption

• both the sender and receiver share the same private key, which they distribute to each other in a process called a key exchange.

• This key is used for both encrypting and decrypting data. It’s important that the private key is kept secret.

• If the key is intercepted during the key exchange then any communications sent can be intercepted and decrypted using the key.

Asymmetric Encryption

• two keys are used: one public and a second, private, key.

• The public key can be published anywhere, free for the world to see, while the private key must be kept secret.

• Together, these keys are known as a key pair and are mathematically related to one another.

• messages encrypted with the recipient’s public key can only be decrypted with the recipient’s private key, which should only be in the possession of the recipient.

hashing

a process in which an input (called a key) is turned into a fixed size value (called a hash)

usus of hashing

• Unlike encryption, the output of a hash function can’t be reversed to form the key. This quality makes hashing useful for storing passwords.

• Another use of hashing is hash tables. A hash table is a data structure which holds key-value pairs. Formed from a bucket array and a hash function, hash tables can be used to lookup data in an array in constant time. When data needs to be inserted, it is used as the key for the hash function and stored in the bucket corresponding to the hash.

collisions when using hashing

• If two pieces of data (keys) produce the same hash, a collision is said to have occurred.

• John​ and Sandra​ both hash to 02​. There are a variety of methods to overcome collisions, including storing items together in a list under the hash value, or using a second hash function to generate a new hash. A good hash function should have a low chance of collision and should be quick to calculate.

• can increase the size of the hash table to avoid collisions