Burrows-Wheeler transform acceleration based on CUDA

DOI

Description

Burrows-Wheeler transform (BWT) is a commonly used transform in compression or text comparison. For example, in bzip2, BWT is used to preprocess the original data, then the same characters in the original data are close to each other, which improves the compression rate. Because the prefix tree of the original string can be easily obtained from the result of the BWT, BWT is also applied to the search and comparison of strings. For instance, the comparison of DNA sequences uses the BWT algorithm. However, BWT is not a fast algorithm, only tens of megabytes per second on CPU. This article uses the GPU to sort the original string by the base of the 4-byte key size radix sort. After radix sort, the part with insufficient length is sorted again to complete the BWT algorithm.

Journal

Keywords

Details 詳細情報について

  • CRID
    1390569700725601280
  • DOI
    10.5954/icarob.2021.os13-2
  • ISSN
    21887829
  • Text Lang
    en
  • Data Source
    • JaLC
    • Crossref
  • Abstract License Flag
    Disallowed

Report a problem

Back to top