Hirschberg:   Introduction

• Saw string edit distance and alignment in
  
  
• O(n²) -time and -space
  
  
• But Hirschberg showed how to do it in
  
  
  • O(n²)-time and
    
    
  • just O(n)-space
    
    
• using divide and conquer . . .

Basic Idea for aligning 2 strings, s1[ ] and s2[ ]

• cut s1[ ] in half at mid-point,   s1 = s1a ++ s1b
  
  
• must be some s2a and s2b s.t.
  
  
  1. s2 = s2a ++ s2b   and
     
     
  2. D( s1, s2 ) = D( s1a, s2a ) + D( s1b, s2b )
     
     
• find this cut-point in distance matrix
  
  
• solve the 2 smaller problems recursively

General Case,   | s1 | > 1

• s1a = 1st half of s1,   s1b = 2nd half,   s1 = s1a ++ s1b
  
  
• run DPA forward on s1a and all of s2
  
  
• run DPA backwards in s1b and all of s2
  
  
• using final "rows", find optimal cut,   s2 = s2a ++ s2b
  
  
• recursively solve
  
  
  • s1a : s2a     and
    
    
  • s1b : s2b

Base Case

• | s1 | = 0,   or
  
  
• | s1 | = 1   -- both easy
  
  

function Hirschberg(int p1, int p2,  int q1, int q2)
/* align s1[p1..p2) with s2[q1..q2). Strings are global! */
 { int mid, i,  s2mid, sum best;

   if( p2 <= p1 )
      a base case ... s1 is empty, match '' : s2

   else if( q2 <= q1 )
      a base case ... s2 is empty, match s1 : ''

   else if( p2-1 == p1 ) /* s1 is 1 character & s2 is not empty */
      a base case ... find best match for s1[p1] in s2[]

   else /* p2>p1+1, s1 has at least 2 chars, divide s1 & conquer */
    { mid = (p1+p2) / 2;
      fwdDPA(p1, mid, q1, q2, fwd);  /* fwd[] is one row */
      revDPA(mid, p2, q1, q2, rev);  /* rev[] is one row */
      s2mid = q1;
      best = huge_number;
      for( i=q1; i<=q2; i++ ) /* seek cheapest split of s2 */
       { sum = fwd[mid % 2][i] + rev[mid % 2][i];
         if( sum < best ) { best=sum; s2mid=i; }
       }
      Hirschberg(p1,mid, q1,s2mid); /* divide & */
      Hirschberg(mid,p2, s2mid,q2); /* conquer! */
    }
 }/*align*/

Space Complexity

• Can compute row ``i'' of D[ , ] from row ``i-1''
  
  
• So Hirschberg uses just O( | s2 | ) - space

Time Complexity

Hirschberg: Summary

• saw another example of divide and conquer, c.f.
  • merge sort
  • quick sort
    
    
• Here we traded time ( x 2 ) for space O( n² ) ----> O( n )
  
  
• [lecturer: use demo; class: take notes!]

Prepare

• ( Dictionary | Lookup ) - Tables