bisect를 사용하여 선의 내용을 인쇄 할 수 있습니까?

Question

각 줄의 알파벳순으로 정렬 된 파일이 있습니다. 파일은 12Gb이며, 이는 단순히 한 행씩 읽을 수는 없다는 것을 의미합니다. 데이터는 다음과 같습니다.

brown 0 1 0 1 2 
fox  3 5 0 0 1 
jumped 2 0 6 1 0 

각 줄의 시작 부분에있는 단어는 고유합니다. 각 줄의 단어와 숫자는 탭으로 구분됩니다. 특정 키워드에 대해 파일을 쿼리 할 수 ​​있기를 원합니다. 예를 들어, "fox"를 쿼리하면 프로그램은 "fox 3 5 0 0 1"을 리턴해야합니다.

https://docs.python.org/3.0/library/bisect.html 내가 키워드의 행 번호를 알아 내기 위하여 양분 사용하는 게시물을 발견 :

그것은 이것에 대한 좋은 후보가 양분 모듈 될 것으로 보인다 것은 How do I perform binary search on a text file to search a keyword in python?

이 무엇 코드입니다 모양은 다음과 같습니다.

import bisect 
import os 

class Query(object): 
    def __init__(self, query, index=5): 
     self.query = query 
     self.index = index 

    def __lt__(self, comparable): 
     return self.query < comparable[self.index:] 

class FileSearcher(object): 
    def __init__(self, file_pointer, record_size=35): 
     self.file_pointer = file_pointer 
     self.file_pointer.seek(0, os.SEEK_END) 
     self.record_size = record_size + len(os.linesep) 
     self.num_bytes = self.file_pointer.tell() 
     self.file_size = (self.num_bytes // self.record_size) 

    def __len__(self): 
     return self.file_size 

    def __getitem__(self, item): 
     self.file_pointer.seek(item * self.record_size) 
     return self.file_pointer.read(self.record_size) 

with open('myfile') as file_to_search: 
    query = 'fox\t' #token to query 
    wrapped_query = Query(query) 
    searchable_file = FileSearcher(file_to_search) 
    linepos = bisect.bisect(searchable_file, wrapped_query) 
    print "Located @ line: ", linepos 
    #print content of line? 

그러나 실제로 줄의 내용을 인쇄하는 방법을 알 수는 없습니다. 최소한 어딘가에 진술을 추가해야하지만, 나는 어디 있는지 모른다.

bisect 모듈을 사용하여 선의 내용을 인쇄 할 수 있습니까?

Answer 1

해당 줄에 seek을 시도하고 readline을 사용하십시오. 이 linepos 가정된다

print "Located @ line: ", linepos 
file_to_search.seek(linepos) 
line = file_to_search.readline() 

---

은 파일의 선두로부터의 바이트 카운트 선의 위치이다. 행 번호에서 계산 된 위치 인 경우 찾기 전에 행당 바이트 수를 곱해야합니다. 파이썬 솔루션을 이동하려면

print "Located @ line: ", linepos 
file_to_search.seek(linepos * searchable_file.record_size) 
line = file_to_search.readline() 

Answer 2

, 당신은 다음을 수행 할 수 MAX_LINE 바이트의 작은 덩어리로

• 읽기 파일을 수정하여 전진 할 때마다 오프셋
• 블록을 결정 오프셋 (offset) 크기
• 이러한 각 읽기에 대해 키 (첫 번째 단어)를 결정하십시오.
• 이러한 키는 블록의 구분자로 사용됩니다.
• 이러한 키의 목록을 구성하십시오. 키가 정렬 될 때 목록이 정렬됩니다.
• pickle/json.dumps /를 통해 어딘가에 이러한 목록을 유지할 수 있습니다.

  abc 4 
  bar 2 
  baz 3 
  egg 6 
  foo 1 
  god 8 
  ham 5 
  sex 7 
  

  :
• quering 때 키를 완전히 차단하고 데이터 여기

로 키를 찾을 수

읽기 위치한 블록의 인덱스 양분을 통해 찾을 수는 예제 파일 bigfile입니다

코드 : 나는 블록을 사용하는이 장난감의 예에서

import os 
from bisect import bisect 

MAX_LINE = 7 
BLOCK_SIZE = 10 

def parse_chunks(filename): 

    size = os.path.getsize(filename) 
    chunks = [] 

    with open(filename, 'rb') as file: 
     block = str(file.read(MAX_LINE*2)) 
     first_line = block[:block.find('\n') + 1] 
     chunks.append(first_line.split()[0]) 

     pos = BLOCK_SIZE 
     while pos < size: 
      file.seek(pos) 
      block = str(file.read(MAX_LINE*2)) 
      first_eol = block.find('\n') 
      second_eol = block.find('\n', first_eol + 1) 
      if first_eol == -1 or second_eol == -1: 
       break 

      line = block[first_eol + 1:second_eol] 

      key = line.split()[0] 
      chunks.append(key) 

      pos += BLOCK_SIZE 

    return chunks 


if __name__ == '__main__': 
    BLOCK_SIZE = 10 
    filename = 'bigfile' 
    chunks = parse_chunks(filename) 

    query = 'abc' 
    pos_before = bisect(chunks, query) - 1 

    with open(filename, 'rb') as file: 
     file.seek(pos_before*BLOCK_SIZE) 
     block = str(file.read(BLOCK_SIZE + MAX_LINE)) 
     line_start = block.find(query) 
     line_end = block.find('\n', line_start + 1) 
     line = block[line_start:line_end] 

     print(line) 

크기가 10 바이트인데, 12GB 파일의 경우 1M으로 시작하는 것이 좋습니다.

Answer 3

다음 재귀 함수는 검색 간격을 좁힐 수 있어야합니다. 일치하는 항목이 없도록 None을 반환하도록 수정할 수 있는지 확신 할 수 없습니다. 여기

def bisearch(f, word, i, j) 
    if (j-1)<1E6: return i,j 

    k = (i+j)/2 
    f.seek(k) 


    while k<j: 
     c = f.read(1) 
     k = k+1 
     if c == '\n': break 
    else: 
     # ??? no match ??? I'm not sure 

    w = [] 
    while 1: 
     c = f.read(1) 
     if c == '\t': break 
     w.append(c) 

    w = "".join(w) 
    if w == word: 
     return k, k 
    if w < word: 
     return bisearch(f, word, k, j) 
    else: 
     return bisearch(f, word, i, k) 

및 사용의 예

word = ... 
f = open(...) 

i,j = bisearch(f, word, 0, len_f) 

f.seek(i) 
if i==j: 
    line = f.readline() 
else: 
#################### EDIT ################ 
# OLD 
# buffer = f.read(1E6) 
# NEW 
    buffer = f.read(j-i) 
    lenw = len(word) 
    for line in buffer.split('\n'): 
     if line[:lenw] == word: break 
    else: 
     # no matches, SOS 

result = process(line)