1.3.1 - compression / encoding / hashing

describe compression (what is it / why’s it needed / 2 types)

• process used to reduce storage space required by a file

• needed to:

  • reduce download/upload times

  • reduce storage requirements

• 2 types:

  • lossy

    • where you reduce the quality of the file in order to reduce file size

  • lossless

    • where you reduce the file-size without changing the file quality

what’s run-length encoding?

• type of lossless compression, meant for (bitmap) images

• compression is done by grouping pixels of the same colour that are next to each other

• done using “frequency/data” pairs

what’s dictionary encoding?

• type of lossless compression, meant for text files

• works by making an index (using a dictionary data structure) that contains frequently repeating values from the file

• the file’d then consist of just the index and a sequence of references to this index

what’s encryption?

• it’s used to keep data secure during transmissions (between senders/recievers)

describe symmetric encryption (what is it / downsides)

• a single key is used to both encrypt and decrypt the message

• 1 single key can be used for every single transmission OR different key can be generated each transmission

• downsides:

  • message can be cracked by either:

    • intercepting the key

    • duplication of the key production process to get a copy of the key

describe assymetric encryption (what is it / how it works / benefits)

• 2 keys are used (together they form “key pairs”), one key is picked to be “public key”, other is “private key”

• messages are encrypted with public key, decrypted with private key

• how it works:

  • sender/reciever each has their own key pair

  • 1 - sender uses their private key the other public key to encrypt the message (combination os called “combination encryption key”)

  • 2 - to decrypt, reciever uses sender’s public key and their private key

• benefits

  • general benefits of encryption (nobody can read it)

  • can ensure the message is authentic

describe hashing (how it works / how its applied in data security/structures)

• hashing involves transforming a string into a key, using a hashing function

• can’t undo hashing

• data security

  • can store personal info in its hashed form

  • makes it so that even if a hacker has the right hashing function / hashed values, they can’t decode the values

• hash tables

  • value to be stored is passed into a hash function to determine the index of it in the structure

  • has O(1) search time