Поиск и извлечение строки из большого файла, соответствующей строкам другого большого файла

Question

Я позволил себе создать новый вопрос, поскольку некоторые параметры резко изменились по сравнению с моим первым вопросом при оптимизации моего сценария bash (оптимизация моего сценария, который выполняет поиск в большом сжатом файле )

Вкратце: я хочу найти и извлечь все строки, где переменная первого столбца файла (1) (файл bam) соответствует первому столбцу текстового файла (2). Для биоинформатики это фактически извлечение совпадающего идентификатора чтения из двух файлов. Файл 1 представляет собой сжатый двоичный файл размером 130 ГБ. Файл 2 представляет собой TSV-файл из 1 миллиарда строк.

Недавно пользователь пришел с очень элегантной строкой, сочетающей распаковку файла и поиск с помощью awk, и это сработало очень хорошо. С размером файлов сейчас ищет более 200 часов (многопоточность).

1. Есть ли у этой «проблемы» имя в алгоритмике?
2. Что может быть хорошим способом справиться с этой задачей? (Если возможно, с помощью простых решений, таких как sed, awk, bash..)

Большое тебе спасибо

Редактировать: извините за код, так как он был по ссылке, я думал, что это будет «дублон». Вот один использованный лайнер:

      #!/bin/bash

samtools view -@ 2 /data/bismark2/aligned_on_nDNA/bamfile.bam | awk -v st="$1" 'BEGIN {OFS="\t"; while (getline < st) {st_array[$1]=$2}} {if ($1 in st_array) {print $0, st_array[$1], "wh_genome"}}' 

Answer 1

Думайте об этом как о длинном комментарии, а не как об ответе. Метод «сортировки слиянием» можно резюмировать следующим образом: если две записи не совпадают, продвиньте одну запись в файле с меньшей записью. Если они совпадают, запишите совпадение и переместите одну запись в большой файл.

В псевдокоде это выглядит примерно так:

      currentSmall <- readFirstRecord(smallFile)
currentLarge <- readFirstRecord(largeFile)
searching <- true
while (searching)
  if (currentLarge < currentSmall)
    currentLarge <- readNextRecord(largeFile)
  else if (currentLarge = currentSmall)
    //Bingo!
    saveMatchData(currentLarge, currentSmall)
    currentLarge <- readNextRecord(largeFile)
  else if (currentLarge > currentsmall)
    currentSmall <- readNextRecord(smallFile)
  endif

  if (largeFile.EOF or smallFile.EOF)
    searching <- false
  endif
endwhile

То, как вы переводите это в awk или bash, выходит за рамки моих скудных знаний.