extra/math/transforms/bwt/bwt.factor

   1 ! Copyright (C) 2012 John Benediktsson
   2 ! See http://factorcode.org/license.txt for BSD license
   3 USING: accessors assocs kernel sequences sequences.rotated
   4 sorting ;
   5 IN: math.transforms.bwt
   6
   7 ! Semi-efficient versions of Burrows-Wheeler Transform
   8
   9 :: bwt ( seq -- i newseq )
  10     seq all-rotations natural-sort
  11     [ [ n>> 0 = ] find drop ] keep
  12     [ last ] seq map-as ;
  13
  14 : ibwt ( i newseq -- seq )
  15     [ length ]
  16     [ <enumerated> sort-values '[ _ nth first2 ] ]
  17     [ replicate-as ] tri nip ;