Input: a source sentence ψ, a forest F , an alignment a, and k Output: minimal initial phrase set R 1: for each node v ∈ V in a bottom-up order do 2: for each hyperedge e ∈ E and head(e) = v do 3: W ← ∅ 4: fixs ← EnumFixed(v, modif iers(e)) 5: floatings ← EnumFloating(modif iers(e)) 6: add structures fixs, floatings to W 7: for each ω ∈ W do 8: if ω is consistent with a then 9: generate a rule r 10: R.append(r) 11: keep k-best dependency structures for v In tree-based rule extraction, one just needs to first enumerate all bilingual phrases that are consistent with word alignment and then check whether the dependency structures over the target phrases are well-formed.
this algorithm fails to work in the forest scenario because there are usually exponentially many well-formed structures over a target phrase.