Как быстро сопоставить поля двух файлов, которые отсортированы, но один является подмножеством другого

Question

У меня есть два отсортированных файла, и я хочу объединить их, чтобы получить третий, но мне нужно отсортировать вывод. Один столбец во втором файле является подмножеством первого, и любое место, в котором второй файл не соответствует первому, должно быть заполнено символом NA. Файлы имеют большие (~ 20 000 000) записей, поэтому загрузка файлов в память является сложной задачей, а скорость - проблемой.

Файл 1 выглядит следующим образом:

1 a
2 b
3 c
4 d
5 e

Файл 2 выглядит так:

1 aa
2 bb
4 dd
5 ee

И вывод должен быть таким

1 a aa
2 b bb
3 c NA
4 d cc
5 e ee

Answer 1

join ваш друг здесь.

join -a 1 file1 file2

должен сделать трюк.Единственное отличие вашего примера в том, что негодные строки печатаются непосредственно из file1, т.е. без NA.

Edit : вот версия, которая также обрабатывает NA с:

join -a 1 -e NA -o 1.1 1.2 2.2 file1 file2

Answer 2

Если я вас правильно понимаю:

• Файл № 1 и файл № 2 будут иметь одинаковые строки
• Однако некоторые строки будут отсутствовать в файле № 2, который находится вfile # 1.
• И, самое главное, строки будут отсортированы в каждом файле.

Это означает, что если я получу строку из файла # 2, и продолжу читать черезфайл # 1, я найду подходящую строку рано или поздно.Поэтому мы хотим прочитать строку из файла № 2, продолжаем просматривать файл № 1, пока не найдем подходящую строку, а когда мы ее найдем, мы хотим распечатать оба значения.

Я бы мог представитькакой-то алгоритм вроде этого:

Read first line from file #2
While read line from file #1
    if line from file #2 > line from file #1
        write line from file #1 and "NA"
    else
        write line from file #1 and file #2
        Read another line from file #2
    fi
done

Должна быть какая-то форма проверки ошибок (что если вы обнаружите, что строка из файла # 1 больше, чем строка из файла # 2? Это означает, что строка #1 пропускает строку.) И, должна быть некоторая проверка границ (что, если у вас закончатся строки из файла # 2, прежде чем вы закончите файл # 1?)

Это звучит как школьное задание, поэтому ядействительно не хочу давать фактический ответ.Тем не менее, алгоритм есть.Все, что вам нужно сделать, это реализовать его на вашем любимом языке.

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

---

Биологу ДНК

#! /usr/bin/env perl

use warnings;
use strict;
use feature qw(say);

use constant {
    TEXT1 =>        "foo1.txt",
    TEXT2 =>        "foo2.txt",
};


open (FILE1, "<", TEXT1) or die qq(Can't open file ) . TEXT1 . qq(for reading\n);
open (FILE2, "<", TEXT2) or die qq(Can't open file ) . TEXT2 . qq(for reading\n);

my $line2 = <FILE2>;
chomp $line2;
my ($lineNum2, $value2) = split(/\s+/, $line2, 2);
while (my $line1 = <FILE1>) {
    chomp $line1;
    my ($lineNum1, $value1) = split(/\s+/, $line1, 2);
    if (not defined $line2) {
        say "$lineNum1 - $value1 - NA";
    }
    elsif  ($lineNum1 lt $lineNum2) {               #Use "<" if numeric match and not string match
        say "$lineNum1 - $value1 - NA";
    }
    elsif ($lineNum1 eq $lineNum2) {
        say "$lineNum1 - $value1 - $value2";
        $line2 = <FILE2>;
        if (defined $line2) {
            chomp $line2;
            ($lineNum2, $value2) = split(/\s+/, $line2, 2);
        }
    }
    else {
        die qq(Something went wrong: Line 1 = "$line1" Line 2 = "$line2"\n);
    }
}

Он не был тщательно протестирован, но работал с некоторыми короткими файлами примеров.

Answer 3

Вот решение Python: "" "объединить два файла на основе совпадения первых столбцов" ""

def merge_files(file1, file2, merge_file):
    with (open(file1) as file1,
          open(file2) as file2,
          open(merge_file, 'w')) as merge:
        for line2 in file2:
            index2, value2 = line2.split(' ', 1)
            for line1 in file1:
                index1, value1 = line1.split(' ', 1)
                if index1 != index2:
                    merge.write(line1)
                    continue
                merge.write("%s %s %s" % (index1, value1[:-1], value2))
                break
        for line1 in file1:  # grab any remaining lines in file1
            merge.write(line1)

if __name__ == '__main__':
    merge_files('test1.txt','test2.txt','test3.txt')

Answer 4

Вы можете сделать все это в оболочке:

sort file.1 > file.1.sorted
sort file.2 > file.2.sorted
join -e NA file.1.sorted file.2.sorted > file.joined