"You mention the possibility of 1 1 1 appearing in an encode result and that
making decode awkward without a loop. My guess is that that can happen if
you encode multiple numbers into a single result where two adjacent
encodings produce the 1 1 1. Is that right?"
This is correct. Simplest example is encode 7 1
Since ' = 2 + 5, this results in
which results in 0101111.
Your idea could work, but seems to not lessen the complexity. I am thinking how
to create
a take-while construction in tacit J.
On Friday, July 19, 2019, 3:54:54 PM GMT+9, Brian Schott
<[email protected]> wrote:
You mention the possibility of 1 1 1 appearing in an encode result and that
making decode awkward without a loop. My guess is that that can happen if
you encode multiple numbers into a single result where two adjacent
encodings produce the 1 1 1. Is that right?
Anyhow, could you produce a workaround using `test` as below in your
decode verb to construct a sort of run length list to break up the 1 1 1
groups and then use Henry's idea in
http://www.jsoftware.com/pipermail/programming/2019-July/053594.html to
extract the pieces?
test =. I. 1 1 1 E. i =. , {:|."1 (8 # 2) ,:|."1 #: a.i. y
On Thu, Jul 18, 2019 at 10:46 AM 'Jon Hough' via Programming <
[email protected]> wrote:
> 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://en.wikipedia.org/wiki/Fibonacci_coding
> https://en.wikipedia.org/wiki/Zeckendorf%27s_theorem
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
>
--
(B=) <-----my sig
Brian Schott
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
