如何从python中的gzip压缩文件中获取随机行而不将其读入内存

Question

假设我有一个531 gig gzip压缩文本文件,其中512 5448 457 601 475行被'\n'分割,并希望在没有文件分割的情况下从中获取随机行.(别担心,它不是那么大;只是想说它是一个巨大的文件,我知道它有多少行.)

我通常如何使用较小的压缩文件:

import fileinput
import gzip
import random

list = []

for line in fileinput.input(file, openhook=gzip.open):
    list.append(line)

listLength = len(list)
randomListLineOne = line[random.randint(0, listLength)]
randomListLineTwo = line[random.randint(0, listLength)]
...

我在这个主题上发现了什么:

如何从python中的一个文件中读取随机行？

import random

def random_line(afile):
    line = next(afile)
    for num, aline in enumerate(afile):
      if random.randrange(num + 2): continue
      line = aline
    return line

Waterman的"水库算法"由Alex Martelli翻​​译,来自Knuth的"计算机编程艺术"

你能为压缩文件调整吗？我尝试将压缩文件设置为文件但是没有用.或者还有另一种(更简单的)方法来实现这一目标吗？

Answer 1

蒙特卡洛

作为逐行读取文件的替代方法*

(*使用David Robinson的方法将gzip文件作为标准文件读取):

如果所有行的大小大致相同,则可以跳转到文件中的随机位置,逐个字符地回溯,直到到达换行符并从该点读取整行.如果线条大小完全相同,则此方法是精确的.

但是如果线条的大小不一样,但你知道有一条长度线的分布x - 你可以按照上面的方法进行,但是x有可能拒绝过多的概率P(x),以便在文件中抓取随机线的概率是不变的.

例:

为了简单起见,假设你有一个5行文件,有长度X={2,3,5,5,5}.在文件中选择一个随机点你有10%(2 /(2 + 3 + 5 + 5 + 5))获得的机会,获得x115%,获得x250%的机会x3.你想要的是一个20%/20%/60%概率.相应的权重,我们是W=(3/2, 1, 6/5),这些都是使得数字x1*w1 = 20%,x2*w2 = 20%,x3*w3=60%.归一化因子是这些权重的总和Z = w1+w2+w3 = 37/10.从这里我们知道每条线的概率:

 P(w1) = w1/Z = 30/68
 P(w2) = w2/Z = 20/68
 P(w3) = w3/Z = 18/68

请注意,P(w1)+P(w2)+3*P(w3)=1应该如此.

对于您的算法,请在文件中选择一个随机点.如果关联的行长度为2,则在两者之间选择一个随机数q=[0,1].如果q>(30/68)拒绝该位置并再试一次.如果停止较少并返回该行.

你什么时候知道的X(w)？

我承认知道线条长度的确切分布似乎是限制性的,但是有很多程序生成的文件(日志文件,硬件数据读数等等),其中分布是确切的.此外,如果仅近似知道分布,我们可以使用上述方法将样本拒绝标准确定为最佳猜测并从那里开始.

蒙特卡洛？

这可能不是最好的方法(谁可以与Knuth竞争？),但它可能提供一些以完全不同的方式解决问题的见解.对于那些不熟悉的人,上述方法是重要抽样的一种形式,蒙特卡罗方法.

如何在gzip文件中查找？

根据OP的要求,这里是一个关于seekPython文件对象的入门读物.

import gzip, random

# Helper function to create some test data
def line(char,n): 
    return ''.join([("%s"%char)*n,"\n"])

# Create the test data as in the example
filename = "test.zip"
FOUT = gzip.open(filename,'wb')
FOUT.write(line('a',2))
FOUT.write(line('b',3))
FOUT.write(line('c',5))
FOUT.write(line('d',5))
FOUT.write(line('e',5))
FOUT.close()

# Since we know the distribution, we know the length
length = 2+3+3*5+5 # 5 newlines

# Print 7 random points in the file
FIN = gzip.open(filename,'rb')
for n in xrange(7):
    FIN.seek(random.randrange(length),0)
    print "Position %3i, char: %s" %(FIN.tell(), [FIN.read(1)])

这样可以将样本的输出运行为:

Position   8, char: ['c']
Position  23, char: ['e']
Position  15, char: ['d']
Position  10, char: ['c']
Position   4, char: ['b']
Position  16, char: ['d']
Position   2, char: ['\n']