Burrows-Wheeler transform acceleration based on CUDA

DOI

説明

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.

収録刊行物

キーワード

詳細情報 詳細情報について

  • CRID
    1390569700725601280
  • DOI
    10.5954/icarob.2021.os13-2
  • ISSN
    21887829
  • 本文言語コード
    en
  • データソース種別
    • JaLC
    • Crossref
  • 抄録ライセンスフラグ
    使用不可

問題の指摘

ページトップへ