Oct-29-2017, 04:37 PM
(This post was last modified: Oct-29-2017, 07:43 PM by sparkz_alot.)
Hi everyone !
I'd like to write the lz77 algorithm in Python step by step.
Those are the functions I'm going to write to put them together in the lz77 function (inspired by the Wikipedia pseudo-code) :
1st function : A(L,i,d) where L is a list, i the current position, d another position i L where d<i ; it should return t the max length of the identical strings beginning in position d and i.
(as an example : with L=[0,1,0,0,1,0,1] and i=3, d=0, A returns 2)
This is what I propose (and it works !):
def A(L,i,d):
t=0
for j in range(0,len(L)):
if L[i+j]==L[j+d]:
t=t+1
else:
return t
return t
2nd function : B(L,i) where L is the list, i the current position ; it should return tuple (d,t) where d is the position of the same string beginning in i and t the maximal length of the identical strings for d<i.
Then I got a problem when I wrote this :
def B(L,i):
d=0
for j in range(0,i):
if L[j]==L[j+i]:
d=j
t=A(L,i,d)
return (d,t)
I doesn't work for all values of i... Where's the problem ?
Next and last step : I can write lz77 by combining the two functions A and B, but to do that ? The pseudo code I found on Wikipedia isn't so clear regarding the functions A and B I wrote...
Thanks for you help !!!
Dob1