Elamur Research⌕
☰
home / papers / 1999 / Bitext Maps and Alignment via Pattern Recognition

Bitext Maps and Alignment via Pattern Recognition

Paper · 1999 · I. Dan Melamed

Summary

Melamed addresses bitext mapping: finding which words and segment boundaries in the two halves of a parallel text correspond. He treats the task as a pattern recognition problem with three parts: generating candidate correspondence points (signal), removing spurious ones (noise filtering), and searching the bitext space for the true chain of correspondences. His algorithm, SIMR (Smooth Injective Map Recognizer), plots word-pair matches in a two-dimensional space whose axes are character positions in each text. It finds matches through cognates, measured with the Longest Common Subsequence Ratio, or through a small seed translation lexicon. It then uses localized noise filters and a local search over roughly linear chains. A companion algorithm, GSA (Geometric Segment Alignment), converts SIMR's maps into sentence or segment alignments. Evaluation on existing gold standards shows high accuracy for very different language pairs, including French/English and Korean/English. Both algorithms outperform comparable published methods and run in linear time. This matters because the approach still works when sentence boundaries are unreliable, scripts differ, or translations contain omissions and reordering.

Key points

  • Geometric framing:
    • A bitext is a rectangle with axes measured in characters. The paper chose characters because they correlate better than token counts across translations.
    • Each word token is placed at its median character.
    • Matching sentence boundaries are placed between characters (offset by .5).
  • Mapping vs. alignment:
    • Bitext maps are injective partial functions approximating the "true bitext map" of all true points of correspondence (TPCs).
    • Unlike classic alignment, the maps allow crossing correspondences.
  • Signal sources:
    • Signals come from cognates (LCSR) or a small hand-built seed translation lexicon.
    • The lexicon lets mapping proceed even when there are no cognates and no detectable sentence boundaries.
  • Languages and resources:
    • SIMR was ported to French/English, Spanish/English, and Korean/English.
    • It mapped over 200 MB of French–English bitexts, and GSA turned those maps into alignments.
    • The maps and alignments are distributed through the Linguistic Data Consortium.
  • Comparison with earlier methods:
    • Length-based aligners (Gale & Church; Brown, Lai & Mercer) fail on runs of similar-length segments, such as parliamentary vote records.
    • They also struggle with non-phonetic scripts like Chinese.
    • GSA aligns in expected linear time, so large bitexts do not need manual pre-alignment.

Interesting ideas

  • I1. Splitting the problem into signal, noise filtering, and search. Breaking a matching task into these three stages lets each stage be improved and evaluated on its own. This could help with other alignment problems, such as audio–transcript or OCR–source matching.
  • I2. Filtering noise locally rather than globally. Noise density varies across a document, so thresholds set per region are more accurate than one global cutoff. This is a useful principle for any long-document matching pipeline.
  • I3. Building the fine structure first, then deriving the coarse one. SIMR first produces a word-level map that tolerates crossings and omissions, and GSA reduces it to segment alignments afterwards. Going from fine to coarse is more robust than aligning coarse units directly, especially for noisy, markup-heavy, or OCR-damaged texts.
  • I4. Keeping language-specific parts behind small modules. Tokenizers, cognate tests, and seed lexicons are encapsulated, so the core algorithm moves to a new language pair with little effort. This design suits low-resource pairs, for example Ukrainian paired with distant languages.
  • I5. Bootstrapping from a tiny hand-made lexicon. When neither cognates nor sentence boundaries are available, a small manually built lexicon can supply enough anchor points to map a bitext. This is a cheap way to start parallel-corpus work for new language pairs.

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

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,085 worksArtificial Intelligence · 8,888 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as I. Dan Melamed. 1999. Bitext Maps and Alignment via Pattern Recognition. Computational Linguistics.

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

@article{melamed1999bitext,
  title = {{Bitext Maps and Alignment via Pattern Recognition}},
  author = {I. Dan Melamed},
  journal = {Computational Linguistics},
  year = {1999},
  url = {https://aclanthology.org/J99-1003/}
}

References

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

  1. Bellman, Richard. 1957. Dynamic Programming. Princeton University Press, Princeton, NJ. find
  2. Brown, Peter F., Stephen Della Pietra, Vincent Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, •9(2): 263-311. find
  3. Brown, Peter F., Jennifer C. Lai, and Robert L. Mercer. 1991. Aligning sentences in parallel corpora. In Proceedings of the 29th Annual Meeting, pages 169-176, Berkeley, CA. Association for Computational Linguistics.
  4. Catizone, Roberta, Graham Russell, and Susan Warwick. 1993. Deriving translation data from bilingual texts. In Proceedings of the First International Lexical Acquisition Workshop, Detroit, MI. find
  5. Chen, Stanley. 1996. Building Probabilistic Models for Natural Language. Ph.D. dissertation, Harvard University, Cambridge, MA. find
  6. Church, Kenneth W. 1993. Char_align: A program for aligning parallel texts at the character level. In Proceedings of the 31st Annual Meeting, pages 1-8, Columbus, OH. Association for Computational Linguistics. find
  7. Church, Kenneth W., Ido Dagan, William Gale, Pascale Fung, J. Helfman, and B. Satish. 1993. Aligning parallel texts: Do methods developed for English-French generalize to Asian languages? In Proceedings of PacfoCol'93. Taipei, Taiwan. find
  8. Cousin, Pierre-Henri, Lorna Sinclair, Jean-Francois Allain, and Catherine E. Love. 1991. The Collins Paperback French Dictionary. Harper Collins Publishers, Glasgow, Scotland. find
  9. Dagan, Ido, Kenneth W. Church, and William Gale. 1993. Robust word alignment for machine aided translation. find
  10. In Proceedings of the Workshop on Very Large Corpora: Academic and Industrial Perspectives, pages 1-8, Columbus, OH. Debili, Fathi and Ely@s Sammouda. 1992. Appariement des phrases de textes bilingues. In Proceedings of the 14th International Conference on Computational Linguistics, pages 517-538, N… find
  11. Dempster, A. P., N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. find
  12. Journal of the Royal Statistical Society, 34(B): 1-38. find
  13. Fung, Pascale. 1995. A pattern matching method for finding noun and proper noun translations from noisy parallel corpora. In Proceedings of the 33rd Annual Meeting, pages 236-243, Boston, MA. Association for Computational Linguistics. find
  14. Fung, Pascale and Kenneth W. Church. 1994. K-vec: A new approach for aligning parallel texts. In Proceedings of the 15th International Conference on Computational Linguistics, pages 1,096-1,102, Kyoto, Japan. find
  15. Fung, Pascale and Kathleen McKeown. 1994. Aligning noisy parallel corpora across language groups: Word pair feature matching by dynamic time warping. In Proceedings of the Conference of the Association for Machine Translation in the Americas, pages 81-88, Columbia, MD. find
  16. Gale, William and Kenneth W. Church. 1991a. A program for aligning sentences in bilingual corpora. In Proceedings of the 29th Annual Meeting, pages 177-184, Berkeley, CA. Association for Computational Linguistics.
  17. Gale, William and Kenneth W. Church. 1991b. Identifying word correspondences in parallel texts. In Proceedings of the DARPA SNL Workshop, pages 152-157. find
  18. Harris, Brian. 1988. Bi-text, a new concept in translation theory. Language Monthly, 54: 8-10. find
  19. J. W. Hunt and T. G. Szymanski. 1977. A fast algorithm for computing longest common subsequences. Communications of the ACM, 20(5): 350-353. find
  20. Isabelle, Pierre. 1992. Bi-textual aids for translators. In Proceedings of the 8th Annual Conference of the UW Centre for the New OED and Text Research, pages 1-15, Waterloo, Canada. find
  21. Kay, Martin and Martin R6scheisen. 1993. Text-translation alignment. Computational Linguistics, 19(1): 121-142.
  22. Knight, Kevin and Jonathan Graehi. 1997. Machine transliteration. In Proceedings of the 35th Annual Meeting, pages 128-135, Madrid, Spain. Association for Computational Linguistics.
  23. Macklovitch, Elliott. 1996. Peut-on v4rifier automatiquement la coh4rence terminologique? META 41(3). . find
  24. McEnery, Tony and Michael Oakes. 1995. Cognate extraction in the CRATER project: Methods and assessment. In Proceedings of From Texts to Tags: Issues in Multilingual Language Analysis, pages 77-86, Dublin, Ireland. find
  25. Melamed, I. Dan. 1996a. Automatic detection of omissions in translations. In Proceedings of the 16th International Conference on Computational Linguistics, pages 764-769, Copenhagen, Denmark. find
  26. Melamed, I. Dan. 1996b. Automatic construction of clean broad-coverage translation lexicons. In Proceedings of the 2nd Conference of the Association for Machine Translation in the Americas, pages 125-134, Montreal, Canada. find
  27. Melamed, I. Dan. 1996c. Porting SIMR to new language pairs. Institute for Research in Cognitive Science Technical Report 96-26, University of Pennsylvania, Philadelphia, PA. find
  28. Melamed, I. Dan. 1997. A portable algorithm for mapping bitext correspondence. In Proceedings of the 35th Annual Meeting, pages 305-312, Madrid, Spain. Association for Computational Linguistics. find
  29. Melamed, I. Dan. 1998a. Models of co-occurrence. Institute for Research in Cognitive Science Technical Report 98-05, University of Pennsylvania, Philadelphia, PA. find
  30. Melamed, I. Dan. 1998b. Empirical Methods for Exploiting Parallel Texts. Ph.D. dissertation, University of Pennsylvania, Philadelphia, PA. find
  31. Nerbonne, John, Lauri Karttunen, Elena Paskaleva, Gabor Proszeky, and Tiit Roosmaa. 1997. Reading more into foreign languages. In Proceedings of the 5th ACL Conference on Applied Natural Language Processing, pages 135-138, Washington, DC. find
  32. Papageorgiou, Harris, Lambros Cranias, and Stelios Piperidis. 1994. Automatic alignment in parallel corpora. In Proceedings of the 32nd Annual Meeting (Student Session), pages 334-336, Las Cruces, NM. Association for Computational Linguistics. find
  33. Resnik, Philip and I. Dan Melamed. 1997. Semi-automatic acquisition of domain-specific translation lexicons. In Proceedings of the 5th ACL Conference on Applied Natural Language Processing, pages 340-347, Washington, DC. find
  34. Simard, Michel, George F. Foster, and Pierre Isabelle. 1992. Using cognates to align sentences in bilingual corpora. In Proceedings of the Fourth International Conference on Theoretical and Methodological Issues in Machine Translation, pages 67-81.
  35. Simard, Michel and Pierre Plamondon. 1996. Bilingual sentence alignment: Balancing robustness and accuracy. In Proceedings of the 2nd Conference of the Association for Machine Translation in the Americas, pages 135-144, Montreal, Canada. find
  36. Ren4 V. V. Vidal, editor. 1993. Applied Simulated Annealing. Springer-Verlag, Heidelberg, Germany. find
  37. Wu, Dekai. 1994. Aligning a parallel English-Chinese corpus statistically with lexical criteria. In Proceedings of the 32nd Annual Meeting, pages 80-87, Las Cruces, NM. Association for Computational Linguistics. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/melamed-1999-bitext-maps-alignment-pattern-recognition/