Looking at an arbitrary example: decode 'cow' 2 5 2 2 1 2 4
It looks like encode and decode are meant to be able to represent lists of integers. But, also there's some inefficiency in the representation which presumably is to make the coding easier: encode decode 'cow' cov FYI, -- Raul On Fri, Jul 19, 2019 at 5:07 AM Linda Alvord <[email protected]> wrote: > > Interseting! > > encode 7 4 1776 > ]��� > > decode encode 7 4 1776 > 7 4 1776 > > Also: > > f2=:13 :'{."1([:+/\|.)^:(i.y)1 1' > > Fibs2=: 13 :'}.f2 y' > > Fibs2 10 > 1 2 3 5 8 13 21 34 55 > > (genfibs 1400)-:Fibs2 1400 > 1 > 1 > 1 > On to understand encode and decode. > > -----Original Message----- > From: Programming <[email protected]> On Behalf Of > 'Jon Hough' via Programming > Sent: Thursday, July 18, 2019 10:46 AM > To: Programming Forum <[email protected]> > Subject: [Jprogramming] Fibonacci Encoding > > Positive integers can be encoded using Fibonacci numbers. > For the sake of easer, assume Fibonacci numbers are 1,2,3,5,... (only one 1). > We can encode a positive integer uniquely using non-consecutive Fibonacci > numbers. For example > > 4 = 1 + 3 (note: 1 and 3 a re non-consecutive) > 5 = 5 (already a Fib number) > 6 = 1 + 5 > 7 = 2 + 5 > 8 = 8 > > These representation can be encoded using bits. 1's where a Fibonacci number > is in the representation, 0s when not. > 4 = 1 + 3 = 101 > 5 = 0001 > 6 = 1001 > 7 = 0101 > 8 = 00001 > ... > > We can append a 1 on the end of the encoding a a delimiter, so that during > decoding we know easily where to stop. This way integers can be packed > together. > > Here are some J verbs for encoding and decoding positive integers. > > > NB. =================================================================== > genfibs=: 3 : 0 > r=. 1 2 > i1=. 1 > i2=. 2 > c=. 2 > while. y > c=. c+1 do. > t=. i1 + i2 > i1=. i2 > i2=. t > r=. r, x: t > end. > ) > > > Fibs=: genfibs 1400 > > encode=: 3 : 0 > d=. > (>@:,&:>)/ (<@encode1)"0 y > r=. d,'0' #~ (#d) -~ 8 * >. 8 %~ # d > pack r > ) > > encode1=: 3 : 0 > n=. x: y > r=. '' > k=: '' > fl=. x: Fibs{~ I. Fibs <: y > i=. <:#fl > while. n do. > r=. r,'1' > n=. n- i{fl > k=: k,i{fl > i=. i-1 > while. (i >: 0) *. (n<i{fl) do. > r=. r,'0' > i=. i-1 > end. > end. > (|.r),'1' > ) > > > > pack=: 3 : 0 > a.{~ #. _8 ] \"."0 y > ) > > decode=: 3 : 0 > i=. , {:|."1 (8 # 2) ,:|."1 #: a.i. y > n=. '' > while. 1 e. 1 1 E. i do. > idx=. {. I. 1 1 E. i > n=. n, +/ Fibs {~ I. i {~ i. >: idx > i=. (2+idx) }. i > end. > n > ) > > NB. =================================================================== > > The encode verb outputs the Fib-representation as bytes. > encode 4 > > > #: a.i. encode 4 > 1 0 1 1 0 0 0 0 > > > decode encode 449239438124834384923493383837734733747181x > 449239438124834384923493383837734733747181 > > > decode encode 1 2 3 4 5 6 7 > 1 2 3 4 5 6 7 > > Fibonacci encoding is not really a good compression encoding, but has some > good error handling properties. > I am not happy with the decode verb, as I wanted to write it without a while > loop. Difficult though as there are some awkaward consecutive bits that might > appear in the encoding, e.g. > ...0 1 1 1 0... > Using 1 1 E. with this breaks decoding unless done carefully. Easier just to > use a while loop and eat the input every iteration. > > refs: > https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FFibonacci_coding&data=02%7C01%7C%7Caa0f5ddb21594beef62008d70b8eadb2%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636990579736889714&sdata=kcs3aC0f7iTcRIMxGWQZR86jnPCYkTd8iCuApVi%2F7H4%3D&reserved=0 > https://eur03.safelinks.protection.outlook.com/?url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FZeckendorf%2527s_theorem&data=02%7C01%7C%7Caa0f5ddb21594beef62008d70b8eadb2%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636990579736889714&sdata=ek%2BmuGj5JjX6ls2x7PFOgSSjjWXu%2FehQouqHabjTjQ8%3D&reserved=0 > ---------------------------------------------------------------------- > For information about J forums see > https://eur03.safelinks.protection.outlook.com/?url=http%3A%2F%2Fwww.jsoftware.com%2Fforums.htm&data=02%7C01%7C%7Caa0f5ddb21594beef62008d70b8eadb2%7C84df9e7fe9f640afb435aaaaaaaaaaaa%7C1%7C0%7C636990579736889714&sdata=9LaJ2RSPcE3LbxIr2XtWQatyJFgMC%2F%2FmOpt2VhsiSrw%3D&reserved=0 > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
