☰

정렬된 텍스트 파일의 이진 검색

tag-icon • tag-icon text-processing search
정렬된 텍스트 파일의 이진 검색

가변 길이의 수십억 줄이 포함된 대규모 정렬 파일이 있습니다. 새 줄이 주어지면 해당 줄이 이미 정렬된 파일에 포함되어 있는 경우 얻을 수 있는 바이트 수를 알고 싶습니다.

예

a\n
c\n
d\n
f\n
g\n

입력 "foo"가 주어지면 출력 9를 얻습니다.

전체 파일을 반복하여 이 작업을 수행하는 것은 쉽지만 가변 길이의 줄이 수십억 개 있으므로 이진 검색을 수행하는 것이 더 빠릅니다.

그러한 텍스트 처리 도구가 이미 존재합니까?

편집하다:

이제 이것이다:https://gitlab.com/ole.tange/tangetools/blob/master/2search

답변1

(이것은 귀하의 질문에 대한 정답이 아니며 단지 시작점일 뿐입니다.)

나는 사용했다스그레프(정렬된 grep) 비슷한 상황에서.

불행하게도(현재 상태가 필요함) 바이트 오프셋 출력이 없지만 쉽게 추가할 수 있다고 생각합니다.

답변2

나는 이것을 할 수 있는 어떤 표준 도구도 모른다. 하지만 직접 쓸 수도 있습니다. 예를 들어 다음 Ruby 스크립트가 작업을 수행해야 합니다.

file, key = ARGV.shift, ARGV.shift
min, max = 0, File.size(file)

File.open(file) do |f|
  while max-min>1 do
    middle = (max+min)/2
    f.seek middle
    f.readline
    if f.eof? or f.readline>=key
      max = middle
    else
      min = middle
    end
  end
  f.seek max
  f.readline
  p f.pos+1
end

조회 후에는 일반적으로 줄 중간에 있기 때문에 약간 까다롭습니다. 따라서 다음 줄의 시작 부분으로 이동하려면 readline을 수행해야 하며, 이를 읽고 키와 비교할 수 있습니다.

답변3

Michas의 솔루션을 기반으로 한 보다 완전한 프로그램은 다음과 같습니다.

https://gitlab.com/ole.tange/tangetools/-/tree/master/2search

답변4

나는 매우 큰 정렬 로그 파일에서 특정 날짜 이후의 모든 기록을 추출하고 싶은 경우가 많습니다. 선형 방식으로 날짜를 찾기 위해 전체 파일을 읽는 데 시간이 너무 오래 걸립니다.

10여년 전에 급하게 수정했어요바라보다이를 쉽게 수행할 수 있는 두 가지 새로운 옵션이 있습니다.

-a: print all lines after the target line
-n: print nearest match if target is not found

로그 파일이 정렬되어 있다고 가정하면 look -b -a -n특정 날짜(또는 해당 날짜에 가장 가까운 행)에 대해 매우 빠른 이진 검색을 수행한 다음 해당 지점부터 파일 끝까지 모든 레코드를 출력할 수 있습니다.

분명히 지난 10여 년 동안 나보다 더 잘한 사람이 있을 겁니다. 그렇죠?

관련 정보