Performance - Extract parts of a large xml file based on a list of hits using sed

Question

I have this large xml file (>10 GB) coming from something called blast (genomics). My goal is to produce a smaller xml file by extracting parts of it based on a list of hits (hits.txt).

hits.txt
object1
object2
object130
object958

I want to extract all those hits and therefore build a smaller xml file.

The method I used will extract, for every object in hits.txt, blocks that starts with <Iteration_query-def>objectxxx and that ends with <Iteration> (i.e. the block dedicated to objectxxx in the large xml file).

Here is my code. It works well ($1 is the large xml file, $2 is hits.txt, and $3 is my output xml file):

NAME=$2
while read NAME
do
    sed -n -e '/<Iteration_query-def>'"$NAME"'/,/<Iteration>/p' $1 >> $3
    echo -e "$NAME information has been extracted"   
done  < <(grep . "$2")

NOW, it is extremely slow! It'll take 11 days to process only 5000 objects (around 3 minutes per object in hits.txt file). Would you have a better method???

Answer 1

Processing XML using non-XML-aware tools is always going to lead to grief. Especially when the file is so large that you can't visibly inspect it to see what's going on. For example, a Gb or two into the file there might be data in a CDATA section that happens to match the expression you are searching on; the resulting errors would be very hard to diagnose.

I would tackle this one using SAX. SAX can often be difficult, but here there is very little state to maintain: one bit to say "the last event was an Iteration-query-def start tag", one bit to say "switch copying on/off". You write an XMLFilter implementation that switches copying on for a text node that matches one of your keywords provided the last event was an Iteration-query-def start tag, and that switches copying off when it sees an Iteration start tag; for every other event you just copy it to the result if copying is switched on.

Answer 2

You will want to process the entire file just once instead of once for each hit you are searching for. You can use awk,python,perl,etc, but you want to read your list of hits just once and read your large file just once.

Assuming the iteration objects cannot be nested using perl you can do something like this

#!/usr/bin/perl -w
use strict; use English;
use IO::Handle;

sub run
{
   my $outputFile = ‘output.xml’;
   my $largeFile = ‘laregInput.xml’;

   open(my $hitsfile, ‘<’, ‘hits.txt’) or die “could not open hits.txt: $!”;
   my @hits = <$hitsfile>;
   close($hitsfile) or warn “error closing hits.txt: $!”;
   my $hitsRegex = buildHitsRegex(@hits);

   my $iterationStopRegex = qr/<Iteration>/;

   open(my $infile, ‘<’, $largeFile) or die “could not open $largeFile: $!”;
   open(my $outfile, ‘>’, $outputFile) or die “error opening $outputFile for writing: $!”;
   $outfile->autoflush; # enable auto flushing to see output in the file it is written not just at after closing the handle

   my $printlines = 0;
   while(my $line = <$infile>)
   {
      if(!$printlines && $line =~ $hitsRegex)
      {
         $printlines = 1;
      }
      if($printlines)
      {
         print $outfile $line;
      }
      if($printlines && $line =~ $iterationStopRegex)
      {
         $printlines = 0;
      }
   }
   close($infile);
   close($outfile);
}

sub buildHitsRegex
{
   my @hits = @ARG;
   my $firstHit = shift(@hits);
   my $hitsRegexStr = '<Iteration_query-def>(?:' . $firstHit;
   for my $hit (@hits)
   {
      $hitsRegexStr .= "|$hit"
   }
   $hitsRegexStr .= ')';
   return qr/$hitsRegexStr/;
}

sub matchesHit
{
   my ($line, $hits) = @ARG;
   my $iterationStartRegex = qr/<Iteration_query-def>/;
   for my $hit (@{$hits})
   {
      if($line =~ /$iterationStartRegex$hit/)
      {
         return 1;
      }
   }
   return 0;
}

run();

If you are only trying to match each hit once you could also remove the hit from the list or regex after matching it.

If <Iteration_query_def> is always at the beginning of the line then you can also optimize some by adding ^ to the beginning of the regex indicating the line must begin with <Iteration_query_def>. Such as

my $hitsRegexStr = '^<Iteration_query-def>(?:' . $firstHit;

The same applies for <Iteration>

my $iterationStopRegex = qr/^<Iteration>/;

If <Iteration> is always on its own line you can also add a $ to match the end of line.

my $iterationStopRegex = qr/^<Iteration>$/;

Answer 3

Assuming there is whitespace following <Iteration_query-def>objectxxx, then try this:

gawk '
    NR==FNR {name[$1]; next}
    ENDFILE {RS="<Iteration_query-def>"}
    $1 in name {print RS $0}
' hits.txt large.xml

Requires GNU awk version 4.

Answer 4

I would check out perl's XML::Twig. It's initialized with a set of xpath expressions and corresponding subroutine refs to call for each xpath match. Here an example:

#!/usr/bin/perl -w

use XML::Twig;

my $hits_path = shift;
my $xml_path = shift;

open HITS, "<$hits_path" || die "could not open $hits_path: $!";
my @hits = <HITS>;
close HITS;

my $twig = new XML::Twig(TwigHandlers => {
    '//Iteration_query-def' => \&process_query_def
});

print "<?xml version=\"1.0\"?>\n<smaller>\n";
# parse the xml
if (defined $xml_path) {
    $twig->parsefile($xml_path);
} else {
    # if no path, parse stdin
    $twig->parse(\*STDIN);
}
print "</smaller>\n";

sub process_query_def {
    my ($tree, $elem) = @_;
    my $text = $elem->text;
    my $first_word = $text;
    $first_word =~ s/\s*([^\s]+).*/$1/s;
    if (grep(/$first_word/, @hits)) {
        print "<Iteration_query-def>$text</Iteration_query-def>\n";
    }
}

Sample usage:

genomics.pl ~/tmp/hits.txt ~/tmp/genomics.xml > ~/tmp/smaller.xml