BWT（Haskellでのコーディング練習）

はじめに

• Haskellの勉強のためにBWT（Burrows-Wheeler Transform）を書いてみました。

BWT（および逆変換）

• Qiita上にもわかりやすい説明がいっぱいあるので省略。

使い方

• 下記のソースコードのusageおよび使用例のように使用してください。

• bwtで変換する文字列に"\$"は使用できません（コマンドの内部で、文字列の終端として"\$"を付与してるので）。

• Haskellの勉強のために、（ちょっと無理やりですが）モナドを使用して結果がMaybe Stringとして返ってきます。

【実装】

  {-
  BWT変換(Burrows-Wheeler-Transform)

  usage: 
    > bwt <String>
    > invBwt <String>
  使用条件:
    ・"$"を文字列の終わりとして使用しているので、"$"を含む文字列には
      使用できない。
  使用例:
    > bwt "mississippi"
    Just "ipssm$pissii"
    > bwt "mississippi" >>= invBwt
    Just "mississippi"
    > bwt "mississippi$" >>= invBwt
    Nothing
  -}

  module Bwt where


  import Data.List

  -- BWT変換

  getSA :: Ord a => [a] -> [Int]
  getSA str = map snd $ sort $ map (\n -> (drop n str, n)) [0..(length(str)-1)] 

  bwt' :: Ord a => [a] -> [a]
  bwt' str = map (\sa -> str!!(mod (sa-1) $ length(str))) $ getSA str

  bwt :: String -> Maybe String
  bwt str = if checkInput then Just (bwt' (str ++ "$")) else Nothing
      where
          checkInput = not $ elem '$' str


  -- BWT逆変換

  lfm :: Ord a => [a] -> [Int]
  lfm str = map snd $ sort $ zip str [0..]

  invBwt' :: Ord a => [a] -> Int -> [a]
  invBwt' str n = map (str!!) . take (length str) . tail 
      $ iterate ((lfm str)!!) n

  invBwt :: String -> Maybe String
  invBwt str = if checkInput then Just (init (invBwt' str endPoint)) else Nothing
      where
          checkInput = elem '$' str
          endPoint = length $ takeWhile (/='$') str

使用した環境

• ghci： version 8.8.3

---

2020/09/18 初稿: