Representing Text

Question 1

What is a character set?

Answer 1

a list of characters and the codes used to represent each one

Question 2

What is ASCII? How many characters are used?

Answer 2

a character set (american standard code for information interchange)

uses 7 bits for each character and there are 128 unique characters, 33 are control characters and the others were numbers, letters, and punctuation

Question 3

What is the difference between ASCII and extended ASCII?

Answer 3

extended ascii uses all 8 bits instead of 7, can also represent lines, symbols, and letters with accents, there are several incompatbile versions

Question 4

What are control characters? Which codes are they in ASCII?

Answer 4

control how text appears, do not appear as text (space, tab)

0-31 and 127 (first 32 and last one)

Question 5

What are the codes for decimal digits? How can you find the code for the number 6?

Answer 5

start at 48, 0=48, 48-57

48 + 6 = 54

Question 6

Where do the codes for uppercase letters start? What about lowercase? If you know the code for a lowercase letter how can you find upper case and vice versa?

Answer 6

start at 65-90

start at 97-122

they are seperated by 32 codes, lower case -32 = uppercase and uppercase +32 = lowercase

Question 7

How can you find the code for K? What about k?

Answer 7

K is 11th letter, 65 + (11-1)= 75

k is 11th letter, 97 + (11-1)= 107

Question 8

Is extended ASCII still limited?

Answer 8

yes, missing common symbols, as well as letters in different languages, can’t use multiple languages at the same time

Question 9

What is Unicode? What is it compared to ASCII?

Answer 9

a character set that is a superset of ASCII

the first 128 characters correspond to the same ones in ASCII, it uses 16+ bits per character and can represent more than 1 million characters

Question 10

How is Unicode organized?

Answer 10

divided into blocks or characters, each block has a theme

ex. arabic, hebrew, etc

Question 11

What are emoji? where did they come from? Where are they located in unicode?

Answer 11

symbol typically appearning in text

japanese word for picture/letter

Miscellaneous Symbols and Pictographs, range 1F300-1F5FF and Emoticons, range 1F600-1F64F

Question 12

What is data compression?

Answer 12

a reduction in the amount of
space needed to store a piece of data

Question 13

What is compression ratio?

Answer 13

the size of the compressed data divided by the size of the original data

Question 14

Is a compression ratio of 90% or 80% more?

Answer 14

80 b/c it means the original data was compressed by 20% while 90 means it was only compressed by 10%

Question 15

What are the two types of data compression?

Answer 15

Lossless, when the data can be retrieved without losing any of the original information

Lossy, some information may be lost in the process of compaction

Question 16

What is keyword encoding?

Answer 16

words that are frequently used in text are replaced with a character, characters that are used to encode cannot be used in the text

ex. as is represented as ~

Question 17

What is run length encoding?

Answer 17

when a single character is repeated a lot of times in a long sequence, doesn’t usually occur in english text but it often occurs in large data streams

Question 18

In run lenght encoding what are sequences of repeating character replaced with?

Answer 18

a sequence like this is replaced by a flag character (*), followed by the repeated character, and a digit to signifiy how many times the character is repeated

Question 19

What is huffman encoding?

Answer 19

huffman codes use variable-length bit strings to represent each character, some characters are represented by 5 bits, 7 bits etc

Question 20

What is one challenge that huffman encoding faced? What was the solution?

Answer 20

hard to know where one symbol ends and the other begins

prefix property: no code is a prefix of another code

Question 21

What is a benefit of huffman encoding in terms of compression?

Answer 21

because it only uses a few bits for characters that appear often and reserves longer bit strings for characters that are less common the overall size of the document is smaller

Question 22

Where did the idea for huffman encoding come from?

Answer 22

morse code, fewer dots and dashes for common letters

Question 23

What is input/output/property in reference to huffman encoding?

Answer 23

input is symbols and their frequency

output is the binary code for each symbol

property is the optimal compression rate with prefix property

Question 24

What are the steps in creating a huffman algorithm?

Answer 24

1. sort the symbols in ascending order of frequency (least to most frequently used) place them in a sorted queue
2. replace the symbols with the two smallest frequencies with a combined symbol, place in 2nd queue
3. repeat step two until one remains in the queue
4. result is binary tree

Question 25

What is root of binary tree?

Answer 25

topmost node or spot on the tree

Question 26

What is branch of binary tree?

Answer 26

connects root to node or node to node

Question 27

What is node of binary tree?

Answer 27

intersection of binary tree

Question 28

What is leaf of binary tree?

Answer 28

bottommost node, end of tree, symbol

Question 29

How do you label the branches of binary tree? Can you label it another way?

Answer 29

left branches is 0 and right branches are 1

yes as long as one branch is 0 and the other is 1

Question 30

How can you find the binary code for a symbol using a completed binary tree?

Answer 30

follow the path from the root of the tree to the leaf and the corresponding binary sequence is the code

Question 31

How can you find the compressed bit length using binary tree?

Answer 31

the summation of (character code length x frequency count)

ex. c appears 3 times and the code is 000, (3 x 3), a appears 17 times and the code is 01, (2 x 17)

Question 32

What is the least and most effective lossless encoding on their own?

Answer 32

least is keyword encoding

most if huffman encoding