The BWT by definition HAS to pass extra data to track the beginning of the string.
Here's a similar transform that doesn't: http://arxiv.org/abs/1201.3077 No, I don't understand it at all, sorry. -Wm On Sat, Feb 2, 2013 at 7:08 PM, Raul Miller <[email protected]> wrote: > Here's a slightly flawed implementation of Burrows-Wheeler Transform > (which is useful when compressing text, because the result tends to be > easy to compress): > > bwt0=: (_1 {"1 [: /:~ (|."0 1~ i.@#)) :. ibwt0 > bwt0 'this is a test' > ssa tt hiie ts > ibwt0=: (_1 { ((,. /:~)^:(#@[) (#,0:) $ ''"_)) :. bwt0 > ibwt0 bwt0 'this is a test' > stthis is a te > > As you can see, the inverse does not quite work right -- it has been rotated. > > Here's a fixed implementation: > > bwt=: bwt0@,&EAV :.ibwt > ibwt=: }.@(|.~ i.&EAV)@ibwt0 :.bwt > ibwt bwt 'this is a test' > this is a test > > This fixed implementation might fail if the original data contained EAV. > > It seems like we ought to be able to implement the transform without > this flaw (perhaps using a boxed representation). > > Allowing arbitrary treatments of how the transformed result tracks the > original location of the beginning/end of text, do we have a more > efficient way of computing the inverse (or the transform)? > > Thanks, > > -- > Raul > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
