Abstract
The Burrows-Wheeler Transform (BWT) was originally developed for data compression, but can also be applied to indexing text. In this paper, an adaptation of the BWT to word-based indexing of the training corpus for an example-based machine translation (EBMT) system is presented. The adapted BWT embeds the necessary information to retrieve matched training instances without requiring any additional space and can be instantiated in a compressed form which reduces disk space and memory requirements by about 40% while still remaining searchable without decompression. Both the speed advantage from O(log N) lookups compared to the O(N) lookups in the inverted-file index which had previously been used and the structure of the index itself act as enablers for additional capabilities and run-time speed. Because the BWT groups all instances of any n-gram together, it can be used to quickly enumerate the most-frequent n-grams, for which translations can be precomputed and stored, resulting in an order-of-magnitude speedup at run time.- Anthology ID:
- 2004.amta-papers.4
- Volume:
- Proceedings of the 6th Conference of the Association for Machine Translation in the Americas: Technical Papers
- Month:
- September 28 - October 2
- Year:
- 2004
- Address:
- Washington, USA
- Editors:
- Robert E. Frederking, Kathryn B. Taylor
- Venue:
- AMTA
- SIG:
- Publisher:
- Springer
- Note:
- Pages:
- 27–36
- Language:
- URL:
- https://link.springer.com/chapter/10.1007/978-3-540-30194-3_4
- DOI:
- Cite (ACL):
- Ralf D. Brown. 2004. A modified Burrows-Wheeler transform for highly scalable example-based translation. In Proceedings of the 6th Conference of the Association for Machine Translation in the Americas: Technical Papers, pages 27–36, Washington, USA. Springer.
- Cite (Informal):
- A modified Burrows-Wheeler transform for highly scalable example-based translation (Brown, AMTA 2004)
- PDF:
- https://link.springer.com/chapter/10.1007/978-3-540-30194-3_4