In the early days of statistical machine translation, models operated on a simple, intuitive assumption: words that belong together in meaning usually stay together in a sentence. This "contiguity assumption" allowed researchers to treat translation as a sequence of adjacent word mappings or contiguous phrase spans.
However, human language is rarely so tidy. Languages are full of discontinuous semantic units—concepts expressed through multiple words separated by intervening text. Think of the English phrasal verb "pick the phone up," the French bipartite negation "ne ... pas," or German separable verbs where the prefix migrates to the end of the clause. When alignment models assume contiguity, these "gappy" structures are often fragmented into nonsensical individual parts.
The Spatial Adjacency Trap
Most traditional alignment algorithms rely on spatial adjacency heuristics. As Jörg Tiedemann notes in Word to word alignment strategies, these heuristics fail when a single semantic unit is split. If an aligner expects a 1-to-1 or a contiguous N-to-M mapping, it cannot easily link a single target word to two source words that are five positions apart.
To solve this, Jörg Tiedemann proposed a "baby-steps" philosophy in the Uppsala Word Aligner (UWA). By first performing easy, reliable alignments for contiguous words, the system can use those "anchors" to gradually identify more complex, non-contiguous multi-word units.
Bridging the Gap with Agreement
A major breakthrough in handling these structures came from the concept of "gappy" phrasal alignment. In Gappy Phrasal Alignment By Agreement, Chris Quirk and Robert C. Moore modified the Hidden Semi-Markov Model (HSMM) framework.
The intuition here is agreement: if you train one model to align Source $\rightarrow$ Target and another to align Target $\rightarrow$ Source, and both models independently decide that a specific "gap" exists in a phrase, that gap is likely a legitimate linguistic feature rather than statistical noise. This dual-directional constraint prevents the model from overfitting and allows it to capture bipartite structures like ne ... pas without losing structural coherence.
From Linear Sequences to Semantic Graphs
If the problem is that words are separated in a linear string, one solution is to stop looking at the string and start looking at the graph. Semantic representations, such as the Abstract Meaning Representation (AMR), represent concepts as nodes and relationships as edges, effectively "collapsing" the distance between split components.
- Transition-Based Parsing: Chuan Wang and Nianwen Xue developed specialized mechanisms for Chinese AMR parsing to unify discontinuous elements into a single semantic node. Their work in Transition-Based Chinese AMR Parsing shows that by using advanced merging logic, a parser can "pull" distant tokens together into one conceptual unit.
- Logical Abduction: Hitomi Yanaka and colleagues took this further in Acquisition of Phrase Correspondences Using Natural Deduction Proofs. They used logical proofs to identify where sentence entailment fails. By looking at the "missing links" in a logical graph, they could infer (or abduce) correspondences between discontinuous phrases that traditional word-order-based methods would miss.
Modern Neural Approaches
Even with the advent of deep learning, the "gappy" problem persists. Modern span-based models, which align variable-length chunks of text, still struggle with non-contiguous spans. Wuwei Lan and Wei Xu addressed this in Neural semi-Markov CRF for Monolingual Word Alignment by introducing "skip alignments."
While these skip alignments are statistically rarer than contiguous ones, they are structurally vital. By allowing a neural CRF to operate on non-adjacent tokens, the model can finally treat a phrasal verb as a single entity, even when an object is wedged in the middle.
Why It Matters
The shift from contiguous to discontinuous alignment is more than a technical hurdle; it is a move toward a more linguistically "intelligent" translation. As Kostadin Cholakov and Valia Kordoni demonstrate in Better Statistical Machine Translation through Linguistic Treatment of Phrasal Verbs, explicitly modeling these split structures leads to significantly higher translation quality. When a system understands that "pick" and "up" are two halves of the same thought, it no longer produces the fragmented, nonsensical outputs that plagued earlier generations of machine translation.