Compression, Encryption, and Hashing Techniques

Purpose of compression

To reduce the storage space required by a file, making it quicker to transfer and easier to store.

Difference between lossy and lossless compression

Lossy removes some data and cannot be reversed; lossless retains all data and allows full recovery of the original file.

Example of lossy compression usage

Compressing audio files by removing inaudible frequencies.

Run-length encoding (RLE)

A lossless compression method that replaces sequences of the same data with one value and a count (e.g., A6B5C3).

Effectiveness of run-length encoding

When data has many repeated, consecutive values.

Dictionary encoding

A method of lossless compression where frequently used data is replaced with shorter representations via a dictionary.

Need for dictionary transfer in dictionary encoding

Because it's needed to decode and restore the original data.

Purpose of encryption

To keep data secure during transmission.

Symmetric encryption

Encryption where the same private key is used for both encrypting and decrypting data.

Key exchange in symmetric encryption

The process of securely sharing the private key between sender and receiver.

Asymmetric encryption

A method using a public-private key pair, where data encrypted with the public key can only be decrypted with the private key.

Advantage of asymmetric over symmetric encryption

It avoids the need to share a private key, reducing the risk of interception.

Using asymmetric encryption to verify sender's identity

By encrypting with the sender's private key—anyone with the public key can decrypt and verify authenticity.

Hashing

A process that converts input data (a key) into a fixed-size value (hash) using a hash function.

Difference between hashing and encryption

Hashing is one-way and cannot be reversed to retrieve the original data.

Usefulness of hashing for passwords

Because stored hashes can't be reversed, so even if leaked, original passwords stay hidden.

Hash table

A data structure that stores key-value pairs and allows fast lookup using hashes.

Collision in hashing

When two different inputs produce the same hash value.

Ways to handle collisions in hash tables

Using lists to store multiple items at the same hash or using a secondary hash function.

Qualities of a good hash function

Low collision rate, fast computation, and output smaller than the input.