next up previous
Next: About this document ... Up: Bilingual Sentence Alignment: Balancing Previous: References

Optimizations in the Salign Algorithm

To lower the computational complexity of the Salign search algorithm, it is necessary to reformulate the computation of the WA(I,J), as presented in Section 3.3. This reformulation requires that we assume P(m | n), the probability of observing a size m string as the translation of a size n string, to be the same for all values of m and n. Then, the value of $\delta(I-i,
J-j)$ becomes constant in the computation of the scoring function W(i,I,j,J), and the following relation holds:

\begin{displaymath}
W(i,I,j,J) = W(i,I,j,k) + W(i,I,k,J), \qquad j < k < J \end{displaymath}

We define Wp(I,J,i) to be the score of the best alignment over the pair of text prefixes s0 ... sI and t0 ... tJ, whose last correspondence covers segments si ... sI-1:

\begin{displaymath}
W_p(I,J,i) = \min_{0 \leq j < J} [ W_A(i,j) + W(i,I,j,J) ] \end{displaymath}

(See Figure 8.)


  
Figure 8: Computation of Wp(I,J,i): Find the value of j that produces the best alignment over s0 ... sI-1 and t0 ... tJ-1, containing a single correspondence that covers text segment si ... sI-1
\begin{figure}
\centerline{
\epsfig {figure=SimPla-fig8.eps,width=3in}
}\end{figure}

It is then possible to express the value of WA(I,J) in terms of Wp(I,J,i):

\begin{displaymath}
W_A(I,J) = \min_{0 \leq i < I} W_p(I,J,i) \end{displaymath}

What makes this intermediate notation interesting is that the computation of each value of Wp(I,J,i) can be greatly simplified:

 
Figure 8: Computation of Wp(I,J,i): Find the value of j that produces the best alignment over s0 ... sI-1 and t0 ... tJ-1, containing a single correspondence that covers text segment si ... sI-1
Wp(I,J,i) = $\displaystyle \min_{0 \leq j < J} (W_A(i,j) + W(i,I,j,J))$    
  = $\min W_A(i,J-1) + W(i,I,J-1,J),\min_{0 \leq \j < J-1} (W_A(i,j) + W(i,I,j,J)))$    
  = $\min W_A(i,J-1) + W(i,I,J-1,J),\min_{0 \leq \j < J-1} (W_A(i,j) + W(i,I,j,J-1) + W(i,I,J-1,J) ) )$    
  = $W(i,I,J-1,J) + \min ( W_A(i,J-1), \min_{0 \leq \j < J-1} (W_A(i,j) + W(i,I,j,J-1)) )$    
  = $W(i,I,J-1,J) + \min ( W_A(i,J-1), W_p(I,J-1,i) )$    

Salign alternately computes rows of values of WA(I,J) and Wp(I,J,i), and stores them in a vector. Computing each value of WA(I,J) then requires O(N) time. Computing individual values of Wp(I,J,i) would normally require O(N2) time, but this can be cut down to O(N), if values of $\sum_{l=i}^{I-1}tr(t_k\vert s_l)$ are pre-computed and stored, for each possible pair of values of i and I. This pre-computation step requires O(N2) time and space.

All things considered, the program must compute O(NM) values of WA(I,J) and Wp(I,J,i), so the overall computational complexity of the algorithm is O(N2M), while space complexity is O(N2).


next up previous
Next: About this document ... Up: Bilingual Sentence Alignment: Balancing Previous: References
Michel Simard
4/24/1998