So...
Let's say that we're going to encode numeric vectors as fibonacci bit
lists, and we take advantage of the "never are two 1s adjacent in the
bit representation of a fibonacci number" to distinguish adjacent
members of the original list. Also, we insist that we only encode
positive integers. That means that a 1 1 in our bit list represents
the end of the representation of an integer.
So, using
fencb=: [: ;(1 1,~[: ({.~ i:&1)Fibs e.fsum)&.>
fenca=: a. {~ [: #.@($~ 0 8>.0 8#:#) ],(6#0)"_
modelencode=: fenca@fencb
fdeca=: (8#2),@:#:a. i.]
basedelim=: _1 |.1 1 E. ]
delims=: (* -.@basedelim)@basedelim
fdecb=: (+/@# Fibs{.~#);._2~ delims
modeldecode=: fdecb@fdeca
modeldecode modelencode p:i.10
2 3 5 7 11 13 17 19 23 29
(= modeldecode@modelencode) 449239438124834384923493383837734733747181x
1
Anyways, that's how I think I would approach the problem, given what
I understand of it, so far.
Interestingly:
(modelencode -: encode) 449239438124834384923493383837734733747181x
1
(modelencode -: encode) 449239438124834384923493383837734733747181x
1
So I don't know where I was stalled, earlier.
That said, at some point in this I also changed genfibs, so that it
would give extended numeric results instead of floating results. I
didn't look too closely at that issue, though...
Thanks,
--
Raul
On Fri, Jul 19, 2019 at 11:36 AM Raul Miller <[email protected]> wrote:
>
> 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
