Как получить случайную строку из сжатого gzip файла в python, не считывая его в память - PullRequest
Новая
       23

Как получить случайную строку из сжатого gzip файла в python, не считывая его в память

4 голосов
/ 16 февраля 2012

Допустим, у меня есть сжатый текстовый файл на 531 гигабайт с ровно 512 548 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

«Алгоритм резервуара» Уотермана в переводе Алекса Мартелли из книги Кнута «Искусство компьютерного программирования»

Не могли бы вы адаптировать это для сжатых файлов? Я попытался установить сжатый файл как файл, но это не сработало. Или есть другой (более простой) способ добиться этого?

Ответы [ 3 ]

5 голосов
/ 17 февраля 2012

Монте-Карло

Как альтернатива чтение файла строка за строкой *

(* используйте метод Дэвида Робинсона, чтобы прочитать файл gzip как стандартный файл):

Если все строки примерно одинакового размера, вы можете перейти к произвольной позиции в файле, возвращаться символ за символом, пока не дойдете до новой строки и не прочитаете всю строку с этой точки. Если линии имеют одинаковый размер, этот метод является точным.

Если, однако, строки имеют разный размер, но вы знаете, что распределение имеет строку с длиной x - вы можете сделать метод, как описано выше, но отклонить избыточный x ' s с вероятностью P(x) такой, что вероятность захвата случайной строки в файле постоянна.

Пример:

Для простоты предположим, что у вас есть 5-строчный файл длиной X={2,3,5,5,5}. Выбрав случайную точку в файле, вы получаете 10% (2 / (2 + 3 + 5 + 5 + 5)) шанс получить x1, 15% получить x2, 50% шанс 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)?

Я признаю, что точное распределение длин строк может показаться ограничительным, однако существует много процедурно сгенерированных файлов (файлов журналов, считывания аппаратных данных и т. Д.), Где распределение точно известно. Кроме того, если распределение известно только приблизительно, мы можем использовать метод, описанный выше, для определения критерия отклонения выборки в качестве наилучшего предположения и оттуда.

Монте-Карло?

Возможно, это не лучший метод (кто может конкурировать с Кнутом?), Но он может дать некоторое представление о решении проблемы совершенно другим способом. Для тех, кто незнаком, вышеописанный метод - это выборка по важности, метод Монте-Карло .

Как искать в файле gzip?

В соответствии с запросом OP здесь приведен учебник по seek через объект файла Python. 

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']
2 голосов
/ 16 февраля 2012

Вы можете просто использовать подход «чтение случайной строки из одного файла в Python», но открыть файл как файл gzip, а не как обычный файл, используя пакет gzip . 

import gzip
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

afile = gzip.open("myfile.zip")
print random_line(afile)
afile.close()
0 голосов
/ 06 февраля 2016

Простите за (очень) поздний ответ, но вы можете использовать метод seek() для позиционирования в файле, если вы знаете размер файла из gunzip -l.
Затем отбросьте следующее чтение, так как оно, вероятно, будет частичной строкой, и используйте последующее чтение в качестве случайных данных.

Печать 10 случайных строк из сжатого текстового файла. 

import random
import gzip, os
f = gzip.open("some.txt.gz","r")
unc_size = os.popen('gunzip -lq some.txt.gz').read()
unc_size = unc_size.strip().split(" ",1)
unc_size = unc_size[1].strip().split(" ",1)
for x in range(1,11):
    f.seek(random.randint(0,int(unc_size[0])))
    dump = next(f)
    print "Random line from byte pos ",f.tell(), next(f)
f.close()
...