@inproceedings{brown-2004-modified,
    title = "A modified Burrows-Wheeler transform for highly scalable example-based translation",
    author = "Brown, Ralf D.",
    editor = "Frederking, Robert E.  and
      Taylor, Kathryn B.",
    booktitle = "Proceedings of the 6th Conference of the Association for Machine Translation in the Americas: Technical Papers",
    month = sep # " 28 - " # oct # " 2",
    year = "2004",
    address = "Washington, USA",
    publisher = "Springer",
    url = "https://preview.aclanthology.org/fix-sig-urls/2004.amta-papers.4/",
    pages = "27--36",
    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."
}