We would further need to retain the subphrase alignment s in order to know the correspondence between the words (i, j) ∈ s in the aligned phrases, and the total number of foreign words that each e i is aligned with (|{i|(i, j) ∈ s}|).
since a phrase alignment <f ,ē > may have multiple possible word-level alignments, we retain a set of alignments s and take the maximum: our suffix array-based data structure can be used straightforwardly to look up all aligned translations for a given phrase and calculate the probabilities on-the-fly.