LZ77压缩算法处理速度较慢

Question

我在LZ77压缩程序中工作，当我试图压缩一个116Kb的文件时，它需要太长的时间来处理。我的代码有什么问题吗？我如何才能改进算法的处理时间？

import fileinput

class Assign:

    def pattern(self, data):

        self.skip = []

        self.m = len(data)
        for k in range(256): self.skip.append(self.m)

        for k in range(self.m - 1): self.skip[ord(data[k])] = self.m - k - 1

        self.skip = tuple(self.skip)

        self.data = data
    def find(self, text):
        n = len(text)
        if self.m > n: return -1
        k = self.m - 1
        while k < n:
            j = self.m - 1; i = k
            while j >= 0 and text[i] == self.data[j]:
                j -= 1; i -= 1
            if j == -1: return i + 1
            k += self.skip[ord(text[k])]
        return -1

class LZ77:

    def __init__(self, data):
        self.position = 0
        self.window = ""
        self.stream = data
        self.streamSize = len(self.stream)
        self.search = Assign()
    def Encode(self):
        p = 0
        c = ''
        lastresult = 0
        found = 0
        for i in range(self.streamSize):
            self.search.pattern(self.stream[self.position:self.position+i+1])
            result = self.search.find(self.window)
            if result < 0: break
            lastresult = result
            found = 1
        c = self.stream[self.position+i]
        p = lastresult
        B = 0
        if i > 0: B = self.position - p
        L = i
        if self.streamSize > 0:
            self.position += i + 1
            self.streamSize -= i + 1
            self.window = self.stream[:self.position]
        #print B,L,c
        return ((B, L), c)



    def Encoder(self):

        output = ""

        length = self.streamSize
        while self.streamSize > 0:
            ((B, L), C) = self.Encode()
            output += str(B) +   str(L) +  C
        return (output)

def aiyoo(#filename):

    enter = raw_input("enter the filename to which the original file is to be compressed to")
    enter1 = enter
    fob1 = open(enter,'wb')
    original = ''
    print filename
    #fob = open(filename,'rb')
    #numlines = 0
    """while True:
        c = fob.read(1)
        if not c:
            print "End of file"
            break
        else :"""
    for line in fileinput.input(['hello.txt']): #size of hello.txt is 116kb   
        original = line
        lz = LZ77(original)
        stream = lz.Encoder()#, streamSize = lz.Encoder()
        fob1.write(stream)
    """for i in fob:
        original = i
        lz = LZ77(original)
        stream = lz.Encoder()#, streamSize = lz.Encoder()
        fob1.write(stream)"""
    #fob.close()
    fob1.close()
    return enter

Answer 1

在提出这样的问题之前，您应该对您的代码进行profile，以找出哪个部分花费的时间最多。

但是不管怎样，我看到你已经实现了一个子串搜索函数。取而代之的是使用find string method应该会有显著的速度提升。

还要注意的是，在Python中实现的压缩算法不会像在eg中实现的那样快。C，还差得远呢。

Answer 2

真实的lz77 (如zip和rar)的工作方式如下:所有具有相同前3-4字节的位置被插入到相同的散列桶中，然后我们只在这些条目中搜索最长的匹配，通常将搜索限制在8-32个位置