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

lz77在真正的归档器（如zip和rar）中的工作方式如下：所有具有相同前3-4个字节的位置都插入到同一个哈希桶中，然后我们只在这些条目中搜索最长的匹配，通常将serarch限制在8-32个位置

Answer 2

在问这样的问题之前，您应该对代码进行概要分析，找出哪一部分最耗时。

但无论如何，我看到您已经实现了一个子字符串搜索功能。相反，使用find字符串方法应该会大大加快速度。

还要注意，在Python中实现的压缩算法不会像在例如C中实现的那样快，甚至不会接近。