200자를 무작위로 추출하는 스크립트에서 shuf를 사용하여 대체 없이 샘플링하는 방법은 무엇입니까?

이것은 awk에서 솔루션을 구현한 것입니다. 데이터는 8GB의 의사 난수 16진수입니다(실제로 16진수 변환 매뉴얼 페이지 약 12개, 3300회 반복). 약 1,100만 개의 행이 있으며 행당 평균 725바이트입니다.

이는 예약된 실행입니다.

Paul--) ls -l tdHuge.txt
-rw-r--r-- 1 paul paul 8006529300 Dec 24 22:38 tdHuge.txt
Paul--) ./rndSelect
inFile ./tdHuge.txt; Size 8006529300; Count 10000; Lth 200; maxIter 50; Db 1;
Iteration   1 needs  10000
Iteration   2 needs   2712
Overlap   9561: 7663038508 to 7663038657
Iteration   3 needs    728
Iteration   4 needs    195
Iteration   5 needs     50
Iteration   6 needs     11
Iteration   7 needs      2
Required 7 iterations
Reporting 10000 samples

real    2m3.326s
user    0m3.496s
sys 0m10.340s
Paul--) wc Result.txt
  20000   20000 2068894 Result.txt
Paul--) head -n 8 Result.txt | cut -c 1-40
>1
5706C69636174656420696E666F726D6174696F6
>2
20737472696E672028696E207768696368206361
>3
20646F6573206E6F742067657420612068617264
>4
647320616E642073746F7265732E204966207468
Paul--) tail -n 8 Result.txt | cut -c 1-40
>9997
6F7374207369676E69666963616E7420646F7562
>9998
7472696E676F702D73747261746567793D616C67
>9999
865726520736F6D652066696C6573206D7573742
>10000
5726E65642E205768656E20746865202D66206F7
Paul--) 

파일을 무작위로 조사하기 때문에 반복이 필요합니다. 프로브가 인접한 프로브나 개행 문자와 겹치는 경우, 프로브는 폐기되고 작은 배치의 새 프로브가 생성됩니다. 평균 라인 길이가 725라인이고 샘플 요구 사항이 200라인인 경우 거의 30%의 프로브가 허용할 수 없을 정도로 라인 끝에 가깝습니다. 실제 데이터의 평균 행 길이를 알 수 없습니다. 행이 길수록 성공률이 높아집니다.

또한 헤더 행(2020년 12월 4일 관련 질문에서 언급된 대로)이 파일에 여전히 존재하는지 여부도 알 수 없습니다. 그러나 모든 헤더 행이 샘플 길이 200보다 작으면 헤더 행이 삭제됩니다(우연히 발생하는 것이 좋음).

코드는 대부분 GNU/awk(최소 bash)이며 일부 주석이 있습니다. 옵션에서 Db=0을 설정하여 숨길 수 있는 잔여 디버깅이 많이 있습니다.

#! /bin/bash

#.. Select random non-overlapping character groups from a file.

export LC_ALL="C"

#.. These are the optional values that will need to be edited.
#.. Command options could be used to set these from scripts arguments.

inFile="./tdHuge.txt"
outFile="./Result.txt"
Count=10000     #.. Number of samples.
Lth=200         #.. Length of each sample.
maxIter=50      #.. Prevents excessive attempts.

Size="$( stat -c "%s" "${inFile}" )"
Seed="$( date '+%N' )"
Db=1

#.. Extracts random non-overlapping character groups from a file.

Selector () {

    local Awk='
#.. Seed the random number generation, and show the args being used.
BEGIN {
    NIL = ""; NL = "\n"; SQ = "\047";
    srand (Seed % PROCINFO["pid"]);
    if (Db) printf ("inFile %s; Size %d; Count %d; Lth %d; maxIter %s; Db %s;\n",
        inFile, Size, Count, Lth, maxIter, Db);
    fmtCmd = "dd bs=%d count=1 if=%s iflag=skip_bytes skip=%d status=none";
}
#.. Constructs an array of random file offsets, replacing overlaps.
#.. Existing offsets are indexed from 1 to Count, deleting overlaps.
#.. Additions are indexed from -1 down to -N to avoid clashes.

function Offsets (N, Local, Iter, nSeek, Seek, Text, j) {

    while (N > 0 && Iter < maxIter) {
        ++Iter;
        if (Db) printf ("Iteration %3d needs %6d\n", Iter, N);

        for (j = 1; j <= N; ++j) {
            Seek[-j] = int ((Size - Lth) * rand());
            Text[Seek[-j]] = getSample( Seek[-j], Lth);
            if (Db7) printf ("Added %10d: \n", Seek[-j], Text[Seek[-j]]);
        }
        #.. Reindex in numeric order for overlap checking.
        nSeek = asort (Seek);
        if (Db7) for (j in Seek) printf ("%6d: %10d\n", j, Seek[j]);

        #.. Discard offsets that overlap the next selection.
        N = 0; for (j = 1; j < nSeek; ++j) {
            if (Seek[j] + Lth > Seek[j+1]) {
                if (Db) printf ("Overlap %6d: %10d to %10d\n",
                    j, Seek[j], Seek[j+1]);
                ++N; delete Text[Seek[j]]; delete Seek[j];
            } else if (length (Text[Seek[j]]) < Lth) {
                if (Db7) printf ("Short   %6d: %10d\n",
                    j, Seek[j]);
                ++N; delete Text[Seek[j]]; delete Seek[j];
            }
        }
    }
    if (Iter >= maxIter) {
        printf ("Failed with overlaps after %d iterations\n", Iter);
    } else {
        printf ("Required %d iterations\n", Iter);
        Samples( nSeek, Seek, Text);
    }
}
#.. Returns n bytes from the input file from position p.
function getSample (p, n, Local, cmd, tx) {

    cmd = sprintf (fmtCmd, n, SQ inFile SQ, p);
    if (Db7) printf ("cmd :%s:\n", cmd);
    cmd | getline tx; close (cmd);
    return (tx);
}
#.. Send samples to the output file.
function Samples (nSeek, Seek, Text, Local, j) {

    printf ("Reporting %d samples\n", nSeek);
    for (j = 1; j <= nSeek; ++j) {
        printf (">%d\n%s\n", j, Text[Seek[j]]) > outFile;
    }
    close (outFile);
}
END { Offsets( Count); }
'
    echo | awk -v Size="${Size}" -v inFile="${inFile}" \
        -v outFile="${outFile}" -v Count="${Count}" -v Lth="${Lth}" \
        -v maxIter="${maxIter}" \
        -v Db="${Db}" -v Seed="${Seed}" -f <( printf '%s' "${Awk}" )
}

#.. Test.

    time Selector

편집: 다른 답변과 구현을 추가하겠습니다(수정이 필요할 수 있음). 현재 답변이 부분적으로 대체되었으므로 곧 삭제할 수 있습니다. 아니면 실제 구현을 위한 설계 설명으로 업데이트할 수도 있습니다.

알고리즘의 기본 프레임워크입니다. 통계적으로 엄격하게 무작위 결과를 내보낼 수는 없지만 요구 사항을 충족하는 것으로 보입니다. 나는 이것을 awk로 프로토타입할 수도 있습니다(Cliff RNG를 사용하거나 shuf 파이프에서 읽을 수도 있음).

1. N을 배열 X에 추가할 오프셋 수(예: 10000)로 설정합니다.

2. N > 0이면 2a에서 2d까지 반복합니다.
   2a.N 블록의 임의 오프셋을 X에 추가합니다(기존 스크립트의 범위 사용).
   2b. X를 숫자 오름차순으로 정렬합니다.
   2c. X를 반복하여 각 오프셋을 다음 오프셋과 비교하고 후속 오프셋의 200자 이내 위치를 삭제하도록 표시합니다.
   2d. 마크의 오프셋을 삭제하고 N을 삭제 횟수로 설정합니다.

3. 이 시점에서 우리는 10,000개의 겹치지 않는 무작위 오프셋(오름차순)을 갖게 되었습니다. (2단계가 결국 종료될 만큼 범위가 충분히 희박한지 테스트해야 합니다(예: 최소 3 * 10000 * 200자).)
   3a. 10,000개의 tail head 명령 시퀀스를 실행합니다(각 오프셋에 대해 하나씩).
   3b. bash를 통해 이 명령을 파이프합니다.

이를 위해서는 먼저 2단계가 종료될 만큼 범위가 희박한지 확인해야 합니다(예: 최소 3 * 10000 * 200자). 이에 대해 조사가 필요할 수도 있습니다.

편집: 샘플 간의 겹침을 확인하려면 오프셋만 필요하지만 줄 끝과의 겹침을 확인하려면 데이터가 필요합니다. 따라서 (2a)에서 샘플 자체를 읽고 첫 번째 바이트의 오프셋으로 인덱싱된 배열에 저장합니다. (2c)에서 짧은 샘플을 확인하고 제거합니다.

이는 우리가 이미 모든 유효한 샘플을 메모리에 저장했기 때문에 전체 (3)을 중복하게 만듭니다(그리고 이를 인덱싱할 유효한 오프셋의 정렬된 목록이 있습니다). 따라서 모든 샘플을 오프셋 순서대로 나열할 수 있습니다.