A modified Burrows-Wheeler transform for highly scalable example-based translation

Ralf D. Brown


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
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:
Bibkey:
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)
Copy Citation:
PDF:
https://link.springer.com/chapter/10.1007/978-3-540-30194-3_4