Exhaustive Search in Practice: CS 306 Lecture notes

Computer Algorithms II Lecture Notes

9 October 2008 • Exhaustive Search in Practice

Outline

Perfect hash functions.
String matching.

The Problem

A compiler recognizes letter sequences as words.

Some words (reserved words) are special.

asm default false new static typeid

auto delete float operator static_cast typename

bool do for private struct union

break double friend protected switch location

case dynamic_cast goto public variable unsigned

catch else if register template using

char enum inline reinterpret_cast this virtual

class explicit int return throw void

const export long short true volatile

const_cast declarations mutable signed try wchar_t

continue extern namespace sizeof typedef while

Quickly identify words as reserved words.

Hash Tables

A hash table solves this problem easily.
- A random-permutation hash function produces byte indices.
- A 256-bucket scatter table (α = 0.26).
Implementing the hash table results in
- One chain of length 8.
- Only 11 words don't collide (1/6 the list).

Analysis

That is unimpressive performance.
- An ordered list has no overhead and worst-case six-probe search.
The hash table is chained; an open-address hash table would have larger clusters.
- But why use a chained hash table?
  - The key-space size is known and fixed.

Trouble Shooting.

Maybe another random permutation would be better.
- “Better:” more non-colliding keys and shorter chains.
Searching a thousand permutations produces
- 5 4-element chains and 6 non-colliding words.
- 12 non-colliding words and 3 5-element chains.

Trouble Shooting..

Maybe a bigger scatter table would work.
- A 661-element scatter table (α = 0.1) has 62 non-colliding words and two two-element chains.
- A 1321-element scatter table (α = 0.05) has 64 non-colliding words.
- At this point it’s the luck of the random permutation.
An ordered list is at least ×10 smaller.

Results

A big scatter table acts like a hash table.
Smaller scatter tables may underperform an ordered list.
- And they're larger than an ordered list.
The hash table's hard to software engineer.
- Add this new keyword; make it faster.
How can hash tables do better?

Exploiting The Key Space

We know the key space size and content.
- We've used the key-space size to influence scatter-table size.
- Without particular success.
Collisions are the problem.
Can we use key knowledge to create a better hash function?
- “Better:” low or no collisions.

Custom Hash Functions

Create a hash function for
{ alb gel mug sog zip }
It falls right out.
```
unsigned hash(word)
  return word[0]
```
A perfect hash function has no collisions over its key space.
How big's the scatter table?

Scatter-Table Size

The scatter table has the range between the largest and smallest possible characters.
- 'z' - 'a' + 1 = 26 in this case.
How can we make the scatter table smaller? How small?

Reducing Scatter-Table Size

How about

map['a'] = 0
map['g'] = 1
map['m'] = 2
map['s'] = 3
map['z'] = 4
map[*]   = 5

unsigned hash(word)
  return map[word[0]]

Now the scatter table has the smallest number of buckets possible.

Further Problems

What happens with more than 26 keys?
What happens if bool and break are keys?
- Look at two characters; the first and last, say.
What if const and const_cast are keys?
- Look at some other pair of characters, or more characters.
- Add the word length to the index.

Custom Hash Table

The custom hash table is
1. The perfect hash function
```
unsigned hash(word)
  unsigned n = strlen(word)
  return n + map[word[0]] + map[word[n-1]]
```
2. The 26-element character map.
3. The open-addressed scatter table, size determined by the character map.
The trick is finding the character map.

Brute-Force Search

Treat map as a 26-digit hexadecimal number.
- Each character maps into [0, 15].

This leads directly to the solution

map = 0
while map < 0xfffffffffffffffffffffffffff 
  if not has-collisions(map, words)
    return map
  map++

Are We Done?

map has roughly 16²⁶ possible values.
- That's about 2×10³¹ values.
Done in by intractable behavior.
We need a way to cut down on the number of values to search.

A Refinement

It isn't necessary to assign values to all 26 letters.
- Just to the letters appearing at the start or end of a string.
This reduces map to a n-digit number, where n distinct letters start or end the words.
- That's better, but not by much if n > 8.
- And n could be 26.

Another Refinement

If a particular assignment to map fails, where's the problem?
- It's not clear.
The code assigns values to letters, but it's the words that collide.
Better to assign values to letters as directed by the words.

Another Solution

solve(words, map, keys)
  if words is empty
    // success
  else
    pick a word in words
    for map[word[0]] = 0 to 15
      for map[word[n-1]] = 0 to 15
        if no-collisions(keys, map)
          solve(words - word, map)
    // failure

This is equivalent to assigning values to an n-digit hexadecimal number.

Choosing Words

How should the solution choose a word from words?
Two general principles provide useful guidelines:
1. Make important decisions first.
2. Find mistakes as early as possible.
How can word choice follow these guidelines?

Important Decisions

Frequently occuring letters are more important than infrequently occurring letters.

elk, egg, the, elf, end, pit

e: 5, k: 1, g: 1, t: 2, f: 1, d: 1, p: 1
- Frequently occurring letters effect more words.
Order words by decreasing letter frequency.
```
f[word.first] + f[word.last]
```

Early Mistakes

Find collisions as soon as possible.
egg, elf, ..., fog
A word should be tested for collisions as soon as its first and last letters have values.
egg, elf, fog, ...
Reorder the list to test for collisions as soon as possible.

Word Ordering Example

Keys are egg, nog, ego, gao, new.
Letter frequences are
g: 3, o: 2, e: 2, n: 2, w: 1
Decreasing frequency order is
egg, gao, nog, ego, new
Early collision order
egg, gao, ego, nog, new

Does It Help?

Sometimes.

set 1 set 2 set 3

Unsorted 13.2 3.6 30.3

Sorted 0.2 0.0 0.0
Sometimes not.

set 4 set 5 set 6

Unsorted 0.6 2.1 9.7

Sorted 0.7 3.9 9.7
These are guidelines, not rules.
See the the code.

	set 1	set 2	set 3
Unsorted	13.2	3.6	30.3
Sorted	0.2	0.0	0.0

	set 4	set 5	set 6
Unsorted	0.6	2.1	9.7
Sorted	0.7	3.9	9.7

Caveats

Large key spaces still confound the algorithm.
- Intractable behavior.
- Non-mappable collisions among keys.
Split large key spaces into smaller ones.
- Multiple hash tables.
- Split unmappable keys among smaller spaces.

String Matching

Find an occurance of a pattern string in a text string.

text: GAGCTCCTGCACTGGATGGTGGC

pattern: CAAAGA
The text string can be many orders of magnatitude larger than the pattern string.
Often somebody's sitting there, waiting for the answer.

text:		GAGCTCCTGCACTGGATGGTGGC
pattern:		CAAAGA

Basic Searching

string searching

Brute-Force String Search

int match(text, pattern)

  t = p = 0

  do
    if text[t] == pattern[p]
      t++; p++
    else 
      t = t - p + 1; p = 0
  while t < T and p < P

  return p == P ? i - p : -1

Brute-Force Example

Pattern text is AGT.
Can we do better?
- Is there any unexploited information?

A Few More Examples

Pattern text is AGT.
Note that t never moves backward.
What information was exploited?

Refinement

You know the characters matched.
You know A appears once in the pattern.
- What if it doesn't?
Don't move the pattern past the second occurence.

Pattern Preprocessing

Create a table to advance the pattern based on characters matched.
- Pattern text: A G A T
  
  mismatch at p = 0 1 2 3
  
  adjust t by 1 0 0 -1
```
if text[t] == pattern[p]
  t++; p++
else 
  t += t-adj[p]; p = 0
```

Can We Do Better?

Is there any information left to exploit?
Given the pattern text
A₀T₁G₂A₃B₄A₅T₆G₇
how far should the pattern advance if there's a mismatch at A₅?
Look at all the pattern characters macthced, not just the first one.

Using More Matches

Advance the pattern so that remaining prefix matches to the left of the mismatch.

A₀ T₁ G₂ A₃ B₄ A₅ T₆ G₇
A₀ T₁ G₂ A₃ B₄ A₅ T₆ G₇
A₀ T₁ G₂ A₃ B₄ A₅ T₆ G₇
A₀ T₁ G₂ A₃ B₄ A₅ T₆
A₀ T₁ G₂ A₃ B₄ A₅
A₀ T₁ G₂ A₃ B₄
This is the Knuth-Morris-Pratt string search.

References

Minimal Perfect Hash Functions Made Simple by Richard Cichelli, Communications of the ACM, January 1980, pages 17-19.
String Searching, Chapter 19 in Algorithms by Robert Sedgewick, Addison Wesley, 1983.

A₀	T₁	G₂	A₃	B₄	A₅	T₆	G₇
	A₀	T₁	G₂	A₃	B₄	A₅	T₆	G₇
		A₀	T₁	G₂	A₃	B₄	A₅	T₆	G₇
			A₀	T₁	G₂	A₃	B₄	A₅	T₆
				A₀	T₁	G₂	A₃	B₄	A₅
					A₀	T₁	G₂	A₃	B₄

mismatch at p =	0	1	2	3
adjust t by	1	0	0	-1