Python Forum

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

In addition to the code tags, you should change all the single character variables and replace them with descriptive names. You will thank yourself later.

Here are both functions A and B and an exemple with a list (you'll see there's a problem with i=6 in the B function but also with i=4 because the result is not correct)

def A(L,i,d):
	t=0
	n=len(L)
	for k in range(0,n):
		if L[i+k]==L[k+d]:
			t=t+1
		else:
			return t
	return t

def B(L,i):
	d=0
	for k in range(0,i):
		if L[k]==L[i+k]:
			d=k-1
	t=A(L,i,d)
	return(d,t)

print(B([0,1,0,0,1,1,0,0,1,0],5))
(1, 4)
>>> print(B([0,1,0,0,1,1,0,0,1,0],4))
(2, 0)
>>> print(B([0,1,0,0,1,1,0,0,1,0],6))
Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    print(B([0,1,0,0,1,1,0,0,1,0],6))
  File "<pyshell#6>", line 4, in B
    if L[k]==L[i+k]:
IndexError: list index out of range