---
title: "Synchronous Binarization for Machine Translation — Zhang 2006"
description: "The authors propose synchronous binarization: each rule is split into binary pieces so that every… 13 references, cited by 71 papers here."
authors: ["Hao Zhang", "Liang Huang", "Daniel Gildea", "Kevin Knight"]
year: 2006
venue: "Proceedings of the Human Language Technology Conference of the NAACL, Main Conference"
source: "https://aclanthology.org/N06-1033/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/zhang-2006-synchronous-binarization-machine-translation/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/zhang-2006-synchronous-binarization-machine-translation/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Synchronous Binarization for Machine Translation

# Synchronous Binarization for Machine Translation

**Authors:** [Hao Zhang](https://md.research.elamur.ai/free/en/authors/hao-zhang/), [Liang Huang](https://md.research.elamur.ai/free/en/authors/liang-huang/), [Daniel Gildea](https://md.research.elamur.ai/free/en/authors/daniel-gildea/) and [Kevin Knight](https://md.research.elamur.ai/free/en/authors/kevin-knight/) · **Year:** 2006 · **Venue:** [Proceedings of the Human Language Technology Conference of the NAACL, Main Conference](https://md.research.elamur.ai/free/en/venues/naacl/) ([NAACL 2006](https://md.research.elamur.ai/free/en/venues/naacl/2006/)) · **Publisher:** [Association for Computational Linguistics](https://md.research.elamur.ai/free/en/publishers/association-for-computational-linguistics/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/N06-1033/) · [PDF](https://aclanthology.org/N06-1033.pdf) · [OpenAlex](https://openalex.org/W1964388487)

**Citations:** 121 citations (OpenAlex, 2026-10-14) · [71](https://md.research.elamur.ai/free/en/papers/zhang-2006-synchronous-binarization-machine-translation/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Syntax-based translation systems built on synchronous grammars or tree transducers can produce better output, but decoding gets expensive when rules contain many nonterminals. Reordering between the two languages forces the decoder to track the boundary words of every child, so the cost of n-gram language model integration grows exponentially with rule size. The authors propose synchronous binarization: each rule is split into binary pieces so that every intermediate (virtual) nonterminal covers a contiguous span in both the source and the target language. They give a linear-time algorithm that factors a rule's permutation where possible, and they extend it to tree-to-string rules that contain terminals. They tested it on over 50 million rules extracted from a large Chinese-English corpus with the method of Galley et al. (2004). Almost all of these rules turned out to be binarizable. Compared with ordinary monolingual binarization, the binarized grammar made decoding both faster and more accurate, and it outperformed an alignment-template system in BLEU. This makes large, syntactically rich rule sets practical to decode with an integrated language model.

## Key points
- Standard left-to-right binarization of the source side leaves m-gram decoding at O(|w|^(3+2n(m−1))). Synchronous binarization makes this O(|w|^(3+4(m−1))), which no longer depends on rule size. Binary SCFG parsing is O(|w|^6), whereas general SCFG parsing is NP-hard.
- The rule set was built as follows:
  - GIZA++ alignments on a Chinese-English parallel corpus with 50M English words;
  - English parses from a variant of the Collins parser;
  - rules extracted with the algorithm of Galley et al. (2004).
  The result was 50,879,242 rules.
- 99.7% of the rules are binarizable, and no length bucket exceeds 25% non-binarizable rules. 86.8% of rules keep either identical or fully reversed order. Human inspection attributed most non-binarizable rules to alignment errors.
- Removing the 0.3% non-binarizable rules did not change BLEU in the baseline system.
- On 116 Chinese test sentences of at most 15 words, with a trigram LM, BLEU scores were:

  | System | BLEU |
  |---|---|
  | Monolingual binarization | 36.25 |
  | Synchronous binarization | 38.44 |
  | Alignment-template system (Och and Ney, 2004) | 37.00 |

## Interesting ideas
- **Judge a factorization by contiguity on both sides.** A good decomposition is one where each intermediate piece covers an unbroken span in both languages. The same test could guide factoring in any setting that aligns two sequences, such as parallel treebanks or cross-lingual annotation projection.
- **Check binarizability with a stack.** The algorithm merges adjacent spans whenever they form a consecutive range, in either straight or inverted order. This gives a cheap, linear-time way to test whether a permutation decomposes hierarchically, which could also serve as a reordering-complexity diagnostic for corpora.
- **Measure on real data, not theory.** In theory almost no long permutations are binarizable, yet extracted rules are nearly all binarizable. Running a "spectrum analysis" on real data before accepting a worst-case argument is good practice in general.
- **Read leftover exceptions as noise signals.** The few non-binarizable rules mostly came from alignment errors, so dropping them cost nothing. Rules that fail a structural check could therefore be used to spot word-alignment or extraction errors.
- **Name virtual nonterminals by their content.** Naming intermediate symbols after their sub-alignment, much like Earley dotted rules, lets different rules share intermediate states without ambiguity. This is a reusable trick for compacting large extracted grammars.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of Pennsylvania](https://md.research.elamur.ai/free/en/universities/university-of-pennsylvania/) — University, Philadelphia, United States · 170 works · 60,739 citations
- [University of Southern California](https://md.research.elamur.ai/free/en/universities/university-of-southern-california/) — University, Los Angeles, United States · 104 works · 33,876 citations
- [University of Rochester](https://md.research.elamur.ai/free/en/universities/university-of-rochester/) — University, Rochester, United States · 25 works · 6,799 citations

📚 Shelves (5): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,085 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,888 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [🧮 Computational Theory and Mathematics](https://md.research.elamur.ai/free/en/shelves/computer-science/computational-theory-and-mathematics/) · 116 works

🧭 Topics (1): [🔁 Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/) · 958 works

## Cite

Cite as: Hao Zhang, Liang Huang, Daniel Gildea and Kevin Knight. 2006. Synchronous Binarization for Machine Translation. Proceedings of the Human Language Technology Conference of the NAACL, Main Conference.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{zhang2006synchronous,
  title = {{Synchronous Binarization for Machine Translation}},
  author = {Hao Zhang, Liang Huang, Daniel Gildea and Kevin Knight},
  booktitle = {Proceedings of the Human Language Technology Conference of the NAACL, Main Conference},
  year = {2006},
  doi = {10.3115/1220835.1220868},
  url = {https://doi.org/10.3115/1220835.1220868}
}
```

- [← previous Bootstrapping Path-Based Pronoun Resolution](https://md.research.elamur.ai/free/en/papers/bergsma-2006-bootstrapping-path-based-pronoun-resolution/)
- [next → Computing relative polarity for textual inference](https://md.research.elamur.ai/free/en/papers/nairn-2006-computing-relative-polarity-textual-inference/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## References

13 references, 6 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Albert V. Aho and Jeffery D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume 1. Prentice-Hall, Englewood Cliffs, NJ. [find](https://scholar.google.com/scholar?q=Albert+V%2E+Aho+and+Jeffery+D%2E+Ullman%2E+1972%2E+The+Theory+of+Parsing%2C+Translation%2C+and+Compiling%2C+volume+1%2E+Prentice%2DHall%2C+Englewood+Cliffs%2C+NJ%2E)
2. David Chiang. 2005. [A hierarchical phrase-based model for statistical machine translation](https://md.research.elamur.ai/free/en/papers/chiang-2005-hierarchical-phrase-based-model-statistical/). In Proceedings of ACL-05, pages 263–270, Ann Arbor, Michigan.
3. Jason Eisner. 2003. [Learning non-isomorphic tree mappings for machine translation](https://md.research.elamur.ai/free/en/papers/eisner-2003-learning-non-isomorphic-tree-mappings/). In Proceedings of ACL-03, companion volume, Sapporo, Japan. 7e+09
4. Michel Galley, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. [What’s in a translation rule?](https://md.research.elamur.ai/free/en/papers/galley-2004-what-s-translation-rule/) In Proceedings of HLT/NAACL-04.
5. Liang Huang, Hao Zhang, and Daniel Gildea. 2005. Machine translation as lexicalized parsing with hooks. In Proceedings of IWPT-05, Vancouver, BC. [find](https://scholar.google.com/scholar?q=Liang+Huang%2C+Hao+Zhang%2C+and+Daniel+Gildea%2E+2005%2E+Machine+translation+as+lexicalized+parsing+with+hooks%2E+In+Proceedings+of+IWPT%2D05%2C+Vancouver%2C+BC%2E)
6. Kevin Knight and Jonathan Graehl. 2005. An overview of probabilistic tree transducers for natural language processing. In Conference on Intelligent Text Processing and Computational Linguistics (CICLing). LNCS. [find](https://scholar.google.com/scholar?q=Kevin+Knight+and+Jonathan+Graehl%2E+2005%2E+An+overview+of+probabilistic+tree+transducers+for+natural+language+processing%2E+In+Conference+on+Intelligent+Text+Processing+and+Computational+Linguistics+%28CICLi)
7. I. Dan Melamed. 2003. Multitext grammars and synchronous parsers. In Proceedings of NAACL-03, Edmonton. [find](https://scholar.google.com/scholar?q=I%2E+Dan+Melamed%2E+2003%2E+Multitext+grammars+and+synchronous+parsers%2E+In+Proceedings+of+NAACL%2D03%2C+Edmonton%2E)
8. Franz Josef Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30(4). [find](https://scholar.google.com/scholar?q=Franz+Josef+Och+and+Hermann+Ney%2E+2004%2E+The+alignment+template+approach+to+statistical+machine+translation%2E+Computational+Linguistics%2C+30%284%29%2E)
9. Giorgio Satta and Enoch Peserico. 2005. Some computational complexity results for synchronous context-free grammars. In Proceedings of HLT/EMNLP-05, pages 803–810, Vancouver, Canada, October. [find](https://scholar.google.com/scholar?q=Giorgio+Satta+and+Enoch+Peserico%2E+2005%2E+Some+computational+complexity+results+for+synchronous+context%2Dfree+grammars%2E+In+Proceedings+of+HLT%2FEMNLP%2D05%2C+pages+803%E2%80%93810%2C+Vancouver%2C+Canada%2C+October%2E)
10. L. Shapiro and A. B. Stephens. 1991. Bootstrap percolation, the Schröder numbers, and the n-kings problem. SIAM Journal on Discrete Mathematics, 4(2):275– 280. [find](https://scholar.google.com/scholar?q=L%2E+Shapiro+and+A%2E+B%2E+Stephens%2E+1991%2E+Bootstrap+percolation%2C+the+Schro%CC%88der+numbers%2C+and+the+n%2Dkings+problem%2E+SIAM+Journal+on+Discrete+Mathematics%2C+4%282%29%3A275%E2%80%93+280%2E)
11. Stuart Shieber and Yves Schabes. 1990. [Synchronous tree-adjoining grammars](https://md.research.elamur.ai/free/en/papers/shieber-1990-synchronous-tree-adjoining-grammars/). In COLING-90, volume III, pages 253–258.
12. Dekai Wu. 1996. [A polynomial-time algorithm for statistical machine translation](https://md.research.elamur.ai/free/en/papers/wu-1996-polynomial-time-algorithm-statistical-machine/). In 34th Annual Meeting of the Association for Computational Linguistics.
13. Dekai Wu. 1997. [Stochastic inversion transduction grammars and bilingual parsing of parallel corpora](https://md.research.elamur.ai/free/en/papers/wu-1997-stochastic-inversion-transduction-grammars-bilingual/). Computational Linguistics, 23(3):377–403.

*Updated 24 October 2026*