Extract the indexes of rows that are swapped in order between two files

Question

I have two large tab-delimited files (>10GB) and I know that when they're sorted, they're identical in content.

However, I'm interested in the order of rows and the index of the swapped ones when they share the same "key" (key here being defined as rows grouped based on Source and Location columns).

In other words, rows between these two files should be only compared against each other when they come from the same group (i.e. when they share the same Source and Location).

So for example, in the example below, rows 4, 5, 6 from file1.tsv should be compared against 4, 5, 6 from file2.tsv

Note: files are normal TSV. Additional spaces are only added here to make columns center- and right-aligned for better visibility. These spaces are not part of the original files

file1.tsv

     Identifier  Position Source  Location
     AY1:2301        87    ch1        14
    BC1U:4010       105    ch1        14
    AC44:1230        90    ch1        15
    AJC:93410        83    ch1        16
    ABYY:0001       101    ch1        16
       ABC:01        42    ch1        16
      HH:A9CX       413    ch1        17
      LK:9310         2    ch1        17
    JFNE:3410       132    ch1        18
    MKASDL:11        14    ch1        18
   MKDFA:9401        18    ch1        18
  MKASDL1:011       184    ch2        50
   LKOC:AMC02        18    ch2        50
     POI:1100       900    ch2        53
    MCJE:09HA        11    ch2        53
   ABYCI:1123        15    ch2        53
     MNKA:410         1    ch2        53

file2.tsv

     Identifier  Position Source  Location
     AY1:2301        87    ch1        14
    BC1U:4010       105    ch1        14
    AC44:1230        90    ch1        15
       ABC:01        42    ch1        16
    ABYY:0001       101    ch1        16
    AJC:93410        83    ch1        16
      HH:A9CX       413    ch1        17
      LK:9310         2    ch1        17
    MKASDL:11        14    ch1        18
    JFNE:3410       132    ch1        18
   MKDFA:9401        18    ch1        18
  MKASDL1:011       184    ch2        50
   LKOC:AMC02        18    ch2        50
     MNKA:410         1    ch2        53
     POI:1100       900    ch2        53
   ABYCI:1123        15    ch2        53
    MCJE:09HA        11    ch2        53

I want to do something similar to a "diff" but at the 'group' level (where rows are only compared when they share the same Source and Location)

I want to extract the original "row numbers" when the order of rows are 'swapped' within the same "Source/Location" "group" (or key).

The whole row should match in terms of content.

But I have no idea how to go about this. I can only think of writing a for loop which would be extremely inefficient when my original dataset has millions of rows.

Expected result:

Group_Source:Location  df1.index  df2.index

ch1:16                         4          6
ch1:16                         6          4
ch1:18                         9         10
ch1:18                        10          9
ch2:53                        14         15
ch2:53                        15         17
ch2:53                        17         14

Assumptions:

• Both dataframes have the same number of rows
• Both dataframes are identical (only order of rows are swapped, so if both are sorted by Source, then Location and then Position and then Identifier, then they will be exactly identical)
• 'Swapped' rows always match exactly in terms of content in all columns

Answer 1

This is one of those rare occasions when I'd probably use getline due to the size of your input files so we only save a handful of lines in memory at a time instead of >10G:

$ cat tst.awk
BEGIN {
    OFS = "\t"
    print "Group_Source:Location", "df1.index", "df2.index"
}
NR != FNR { exit }
{ srcLoc = $3 ":" $4 }
srcLoc != prevSrcLoc {
    if ( NR > 1 ) {
        diff()
    }
    prevSrcLoc = srcLoc
}
{
    file1[$1,$2] = FNR - 1
    if ( (getline < ARGV[2]) > 0 ) {
        file2[$1,$2] = FNR - 1
    }
}
END { diff() }

function diff(          idPos) {
    for ( idPos in file1 ) {
        if ( file1[idPos] != file2[idPos] ) {
            print prevSrcLoc, file1[idPos], file2[idPos]
        }
    }
    delete file1
    delete file2
}

$ awk -f tst.awk file1.tsv file2.tsv
Group_Source:Location   df1.index       df2.index
ch1:16  6       4
ch1:16  4       6
ch1:18  10      9
ch1:18  9       10
ch2:53  17      14
ch2:53  15      17
ch2:53  14      15

For more info on getline, please read http://awk.freeshell.org/AllAboutGetline.

The above would work even if an Identifier and/or Position was repeated within the input since it's comparing all 4 fields between the 2 files. It does assume that the Source and Location values are in the same order between the 2 files as shown in the sample input.

Answer 2

This is relatively straightforward in awk. For example:

$ awk '{ 
        if(FNR==1){
            next
        }
        else if(FNR==NR){
            a[$1]=FNR-1;
        } 
        else if ( a[$1] != FNR-1 ){
            print $3":"$4, FNR-1, a[$1]
        }
    }' file1.tsv file2.tsv 
ch1:16 4 6
ch1:16 6 4
ch1:18 9 10
ch1:18 10 9
ch2:53 14 17
ch2:53 15 14
ch2:53 17 15

Explanation

• if(FNR==1){ next }: FNR holds the line number (record number) of the file currently being read. So if this is the first line of either input file, just skip it since we don't want to process the header.
• else if(FNR==NR){ ... }: NR holds the current input line number, irrespective of which file is being read. So if FNR is equal to NR, that means we are reading the first file.
• a[$1]=FNR-1: so, if this is the first file, store the first field as an index (key) in an associative array whose value will be the current file's line number (FNR), but minus one because we don't want to be counting the header.
• else if ( a[$1] != FNR-1 ){: this else if is linked to the previous one, so we will only enter this one if FNR is not equal to NR, so only when we are reading the second file. So, if we are reading the second file and the value stored in the a array for this line's first field is not equal to the current file's line number minus one, then we want to print.
• print $3":"$4, FNR-1, a[$1]: so we print the 3rd field, a : and the 4th field, and then the FNR minus one and the value stored in the a array for this first field.

Finally, to have it pretty printed with padding and the header, use:

$ awk 'BEGIN{
            printf "%-26s%-12s%-12s\n", \
                "Group_Source:Location","df1.index","df2.index"
        } 
        { 
            if(FNR==1){ next }
            else if(FNR==NR){ a[$1]=FNR-1 } 
            else if ( a[$1] != FNR-1){
                printf "%-26s%-12s%-12s\n", $3":"$4, FNR-1, a[$1]
            }
        }' file1.tsv file2.tsv 
Group_Source:Location     df1.index   df2.index   
ch1:16                    4           6           
ch1:16                    6           4           
ch1:18                    9           10          
ch1:18                    10          9           
ch2:53                    14          17          
ch2:53                    15          14          
ch2:53                    17          15          

---

Important: this approach requires you to keep an albeit small amount of data in memory for every line of the first file (bar the header). This could be an issue for huge files, although probably not on most machines where you're likely to do this sort of operation. If this is a problem, I recommend Ed's answer which should both significantly faster and not have any memory issues.