Alignment of Shared Forests for Bilingual Corpora

Research in example-based machine translation (EBMT) has been hampered by the lack of efficient tree alignment algorithms for bilingual corpora. This paper describes an alignment algorithm for EBMT whose running time is quadratic in the size of the input parse trees. The algorithm uses dynamic programming to score all possible matching nodes between structure-sharing trees or forests. We describe the algorithm, various optimizations, and our implementation.

• Publication year

  1996

• Venue

  International Conference on Computational Linguistics

• Publication date

  1996-08-05

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/992628.992708
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• On the Agreement of Many Trees

  1995cited by this paper
• Constituent Boundary Parsing for Example-Based Machine Translation

  1994cited by this paper
• The Mathematics of Statistical Machine Translation: Parameter Estimation

  1993cited by this paper
• Structural Matching of Parallel Texts

  1993cited by this paper
• Aligning Sentences in Bilingual Corpora Using Lexical Information

  1993cited by this paper
• Kaikoura Tree Theorems: Computing the Maximum Agreement Subtree

  1993cited by this paper
• Learning Translation Templates From Bilingual Text

  1992cited by this paper
• Combining rationalist and empiricist approaches to machine translation

  1992cited by this paper
• The BICORD System Combining Lexical Information from Bilingual Corpora and Machine Readable Dictionaries

  1990cited by this paper
• Toward Memory-based Translation

  1990cited by this paper
• Structure Sharing with Binary Trees

  1985cited by this paper
• A Structure-Sharing Representation for Unification-Based Grammar Formalisms

  1985cited by this paper
• A framework of a mechanical translation between Japanese and English by analogy principle

  1984cited by this paper

• Dual Attention Model for Citation Recommendation

  2020cites this paper
• Optimising Tree Edit Distance with Subtrees for Textual Entailment

  2013cites this paper
• Wealth of Flora and Vegetation in the La Campana-Peñuelas Biosphere Reserve, Valparaiso Region, Chile

  2012cites this paper
• Improving MT Word Alignment Using Aligned Multi-Stage Parses

  2011cites this paper
• Text-to-Text Generation for Question Answering

  2011cites this paper
• Reifying the Alignments

  2010cites this paper
• Automatic Generation of Parallel Treebanks: An Efficient Unsupervised System

  2010cites this paper
• Dependency Graph Based Sentence Fusion and Compression

  2010cites this paper
• Study and implementation on key techniques for an example based machine translation system

  2010cites this paper
• Cross-lingual Annotation Projection for Semantic Roles

  2009cites this paper
• Chinese-English Chunk Alignment Based on Anchor Chunk

  2009cites this paper
• Complementary approaches to tree alignment. Combining statistical and rule-based methods

  2008cites this paper
• Generalized Parsers for Machine Translation

  2007cites this paper
• Indução de léxicos bilíngües e regras para a tradução automática

  2007cites this paper
• Dependency-based paraphrasing for recognizing textual entailment

  2007cites this paper
• Dependency-Based Phrase Alignment

  2006cites this paper
• Recognizing Textual Entailment with Tree Edit Distance: Application to Question Answering and Information Extraction

  2006cites this paper
• Normalized alignment of dependency trees for detecting textual entailment

  2006influential citation
• Aligning ASL for Statistical Translation Using a Discriminative Word Model

  2006cites this paper
• The digital sublime: Myth, power, and cyberspace

  2006cites this paper
• Computation of Semantic Equivalence for Question Answering

  2005cites this paper
• Explorations in Sentence Fusion

  2005cites this paper
• Classification of Semantic Relations by Humans and Machines

  2005cites this paper
• Sentence Fusion for Multidocument News Summarization

  2005cites this paper
• Computing the Maximum Agreement of Phylogenetic Networks

  2004cites this paper
• Automatic Construction of Translation Knowledge for Corpus-based Machine Translation

  2004cites this paper
• Rooted Maximum Agreement Supertrees

  2004cites this paper
• Statistical Machine Translation by Parsing

  2004cites this paper
• Statistical Machine Translation by Generalized Parsing

  2004cites this paper
• Translation Knowlegde Acquisition for Pattern-based Machine Translation

  2004cites this paper
• Text Simplification for Reading Assistance: A Project Note

  2003cites this paper
• An Overview of EBMT

  2003cites this paper
• Consensus Algorithms for Trees and Strings

  2003cites this paper
• Finding Translation Patterns from Paired Source and Target Dependency Structures

  2003cites this paper
• Extracting Translation Knowledge from Parallel Corpora

  2003cites this paper
• A Synchronization Structure of SSTC and Its Applications in Machine Translation

  2002cites this paper
• Machine Translation and the Information Soup

  2002cites this paper
• Structure Alignment Using Bilingual Chunking

  2002cites this paper
• Corpus-based Generation of Numeral Classifier using Phrase Alignment

  2002cites this paper
• Translation Pattern Extraction and Recombination for Example-Based Machine Translation

  2001cites this paper
• Hierarchical Phrase Alignment Harmonized with Parsing

  2001cites this paper
• Covering Treebanks with GLARF

  2001cites this paper
• Inducing probabilistic invertible translation grammars from aligned texts

  2001cites this paper
• Finding Target Language Correspondence for Lexicalized EBMT System

  2001cites this paper
• Finding Structural Correspondences from Bilingual Parsed Corpus for Corpus-based Translation

  2000cites this paper
• Öø¹¹¹××× Ìööò×××ö Êùðð Ôôðð Blockin Blockinøøóò Ò Åå Blockinòò Ìööò×ððøøóò

  2000cites this paper
• Chart-Based Transfer Rule Application in Machine Translation

  2000cites this paper
• Review Article: Example-based Machine Translation

  1999influential citation
• Iterative Alignment of Syntactic Structures for a Bilingual Corpus

  1999cites this paper
• Deriving Transfer Rules from Dominance-Preserving Alignments

  1998cites this paper
• A multilingual procedure for dictionary-based sentence alignment

  1998cites this paper
• A Class-based Approach to Word Alignment

  1997cites this paper
• Integrated translation-memory for advanced architecture machine translation

  1997influential citation
• Deriving Transfer Rules from Dominance-Preserving Alignments

  1997cites this paper
• 1 Project Title & Acronym and Abstract DAESO : Detecting and Exploiting Semantic Overlap

  year unknowncites this paper
• Proteus Project Working Paper #2: Statistical Machine Translation by Parsing

  year unknowncites this paper