Computing Unplugged
(Part 3: Data & Searching)

Kansas 4-H Discovery Days 2016

Algorithm

INPUT: a two-word phrase of form,  "Word1 Word2"
OUTPUT: an  AnswerList,  a list of the numbers of the Web pages that
contain the phrase

ALGORITHM:
(0.  The  AnswerList  starts with nothing saved in it.)

1. Extract from the table the list of  Page#-Position#  pairs for  Word1.  Call it  List1.

2. Extract from the table the list of  Page#-Position#  pairs for  Word2.  Call it  List2.

3. For each  page#-pos#  pair in List1,
      search  List2  to see if there is a pair,  page#-(pos#+1).
        (that is, the page# is the same and pos# differs by +1)
      if yes, then include  page#  in the  AnswerList.
      if no, then ignore this pair.

4. Announce all the page numbers in  AnswerList

Nearness

• Look up "cat sat" using the list
• Look up:
  • cat stood
  • "cat stood"
  • cat OR stood
• How would that algorithm change?

Ranking with Keywords

• Which page is more likely to be about dogs? Cats? How could you tell?
• How would you modify the algorithm to account for that?

AltaVista

• Early web search engine with crawler and indexer
• 1996: 5 servers, 210 GB storage & 4GB RAM on main indexer
• 1998: 20 servers, 500 GB storage & 130 GB RAM, 13 million queries daily
• Bought by Yahoo in in 2003, shut down in 2011

Problems?

• Web Spam
• Computation Time
• Non-textual Data
• Structured Data


• Others?

Compression

• Resources are expensive
  • Storage space
  • Transmission bandwidth
  • Time to read/send
• Does require more computation; can be a tradeoff

Run Length Encoding

• Find "runs" (repeated sequences) in data
• Replace them with a shorter version
• Usually the sequence and a count

RLE Example

WWWWWWWWWWWWBWWWW
WWWWWWWWBBBWWWWWW
WWWWWWWWWWWWWWWWW
WBWWWWWWWWWWWWWWW

Image Source: Wikipedia

RLE Example

WWWWWWWWWWWWBWWWW
WWWWWWWWBBBWWWWWW
WWWWWWWWWWWWWWWWW
WBWWWWWWWWWWWWWWW
12W1B12W3B24W1B15W

Image Source: Wikipedia

RLE Example

WWWWWWWWWWWWBWWWW
WWWWWWWWBBBWWWWWW
WWWWWWWWWWWWWWWWW
WBWWWWWWWWWWWWWWW

Image Source: Wikipedia

Escape Coding

WWWWWWWWWWWWBWWWW
WWWWWWWWBBBWWWWWW
WWWWWWWWWWWWWWWWW
WBWWWWWWWWWWWWWWW
WW12BWW12BB3WW24BWW15

Image Source: Wikipedia

Huffman Coding

• Count the occurrences of each character
• Make a binary tree with the data
• The paths of the tree give the codes

Huffman Example

THIS IS AN EXAMPLE OF
A HUFFMAN TREE
288 bits (8 * 36)

Image Source: Wikipedia

Huffman Example

THIS IS AN EXAMPLE OF
A HUFFMAN TREE

• space: 7
• a: 4
• e: 4
• f: 3
• h: 2
• i: 2
• m: 2
• n: 2
• s: 2
• t: 2
• l: 1
• o: 1
• p: 1
• r: 1
• u: 1
• x: 1

Image Source: Wikipedia

Huffman Example

THIS IS AN EXAMPLE OF
A HUFFMAN TREE
0110 1010 1000 1011
111 1000 1011 111
010 0010 111 000 10010
... (135 bits)

Image Source: Wikipedia

Intuition - Squeezing

Hello there

Hello there

Hello ghere

Hello ghere

Simple - Addition

Hello there

72 101 108 108 111 32
116 104 101 114 101 33
= 1101
      

Simple - Addition

• If we only have the sum, can we recover the original?
• How well does this detect errors?
• Are there errors it cannot detect?
• 1101 is larger than 8 bits. How should we handle that?
• Can we do better?

Better - Pinpoint

4837543622563997

Better - Pinpoint

483725436822565399784306

Better - Pinpoint

483725436827565399784306

Better - Fletcher's Checksum

INPUT:  a data word (e.g., a sequence of ASCII-numbers)
OUTPUT: two checksums for the word, each sized to fit
        in one byte

ALGORITHM:
1. divide the  Word  into a sequence of equally-sized
   blocks, b1 b2 ... bn
2. define two checksums, starting at  C1 = 0  and  C2 = 0
3. for each block, bi,
        add  bi to  C1
        add the new value of  C1  to  C2
4.  compute  Checksum1 = C1 mod 255 and
    Checksum2 = C2 mod 255
5.  return  Checksum1  and  Checksum2

Better - Fletcher's Checksum

72 101 108 108 111 32 116 104 101 114 101 33

Testing Fletcher's

• 72 101 108
• 72 108 101
• 74 99 108
• 72 101 0 108


• Which ones does it catch?

Cyclic Redundancy Check (CRC)

Input: 010100001001
Check: 1011

    010100001001
XOR  1011
    ------------
        10001001
    XOR 1011
       ---------
        00111001
      XOR 1011
         -------
           10101
       XOR 1011
          ------
  Checksum: 011

Hash Codes

Choose a "hash base", b (e.g., b= 2 or b= 10 or b= 37)

For a word of integers of length n+1:
    w =  x0 x1 x2 ... xn-1 xn,

Compute this hash number:
    hash(w) =  (x0 * bn) + (x1 * bn-1) + (x2 * bn-2) + ...
               (xn-1 * b1) + xn
             

Hash Codes

For  word = 4 5 6,
when  b = 10,
     hash(word) = (4 * 102) + (5 * 101) + 6  =
     400 + 50 + 6  =  456
when b = 100,
     hash(word) = (4 * 1002) + (5 * 1001) + 6  =
     40000 + 500 + 6  =  40506
when b = 5,
     hash(word) = (4 * 52) + (5 * 51) + 6  =
     100 + 20 + 6  =  126
when b = 2,
     hash(word) = 16 + 10 + 6 =  32
when b = 1,
     hash(word) = 4 + 5 + 6 = 15
             

Hash Codes

For word = 12 33 08,
when b = 10,
     hash(word) = (12 * 102) + (33 * 101) + 8  =
     1200 + 330 + 8  =  1538
when b = 100,
     hash(word) = (12 * 1002) + (33 * 1001) + 8  =
     120000 + 3300 + 8  =  123308
when b = 5,
     hash(word) = (12 * 52) + (33 * 51) + 8  =
     300 + 165 + 8  =  473
when b = 2,
     hash(word) = 48 + 66 + 8 =  122
       

Hamming Codes

BIT#:    1       2        3  4       5  6  7
        -------------------------------------------
PURPOSE: P3,5,7  P3,6,7   D  P5,6,7  D  D  D

where  D  is a data bit, and
Pa,b,c,...  is the parity bit for data bits at  a,b,c,...

Examples:
DATA 3 5 6 7  P3,5,7  P3,6,7  P5,6,7   HAMMING CODE
------------------------------------------------------
     0 1 0 0     1       0       1     1 0 0 1 1 0 0

     1 0 1 1     0       1       0     0 1 1 0 0 1 1