Masking part of a string

citromatik has asked for the wisdom of the Perl Monks concerning the following question:

Hi all, monks

I'm trying to mask part of a string based on a bit vector. i.e:

Str:  AGACGAGTA
Mask: 001111100
---------------
Res:  AGxxxxxTA
[download]

To do that I wrote the following script (to deal with a dummy example):

use strict;
use warnings;

my $seq = "AGACGAGTA";
my $mask=''; vec ($mask,$_,1)=1 for (2..6);
print "Str:  $seq\n";
print "Mask: ", unpack ("b*",$mask),"\n";
[download]

At this point the output of the program is:

Str:  AGACGAGTA
Mask: 00111110
[download]

To apply the mask I found two possible solutions:

#Solution 1:
my @mask = split "",unpack ("b*",$mask);
my @seq = split "",$seq;
print "Res:  ";
print map {! shift @mask ? $_ : "x"} @seq;
print "\n";
[download]

and...

# Solution 2:
my $s_mask = unpack ("b*",$mask);
my $pos=0;
print "Res:  ";
while ($pos < length($seq)){
  no warnings;  ## $s_mask could be shorter than $seq
  print ! substr($s_mask,$pos,1) ? substr($seq,$pos,1) : "x";
  $pos++;
}
print "\n";
[download]

Both outputs as expected:

Res: AGxxxxxTA
[download]

But I do not feel to taste with any of the two: In real examples (strings to mask having lengths ~10e5), step through both strings or arrays (the string to mask and the bit vector) could be very inefficient and one of the reason to use bit vectors is efficiency building them ($mask1 | $mask2, $mask1 & $mask2, etc...).

Is there any way to do the masking without having to traverse all the sequence? Am I in the wrong direction for doing the job?

Thanks in advance!

citromatik

Comment on Masking part of a string Select or Download Code

Replies are listed 'Best First'.
Re: Masking part of a string by ikegami (Patriarch) on Jun 27, 2007 at 13:31 UTC
You're dealing with characters (or octects), not bits, so you need to set 8 bits in the mask instead of 1 for each letter. `substr` is a good alternative to `vec` for doing that. Perl even has Bitwise String Operators (see perlop) that allow you to do bit operations on entire strings "at once". `my $str = 'AGACGAGTA'; my $mask = "\xFF" x length($str); substr($mask, $_, 1, "\x00") for 2..6; my $res = $str & $mask; $res =~ s/\x00/x/g; print("$res\n");` [download] You can avoid the regexp call: `my $str = 'AGACGAGTA'; my $mask = "\xFF" x length($str); substr($mask, $_, 1, "\x00") for 2..6; my $x = 'x' x length($str); my $res = ($str & $mask) \| ($x & ~$mask); print("$res\n");` [download] Of course, you really don't need the mask at all. `my $str = 'AGACGAGTA'; my $res = $str; substr($res, $_, 1, "x") for 2..6; print("$res\n");` [download] Update: Added the last two snippets.	[reply] [d/l] [select]
Re^2: Masking part of a string by johngg (Canon) on Jun 27, 2007 at 14:36 UTC
I've had a go at running a benchmark. If I've not made a mess of it, the pure masking solution seems to be by far the quickest. use strict; use warnings; use Benchmark q{cmpthese}; my $str = q{AGACGAGTA} x 12000; my $mask = qq{\xFF} x length $str; my $x = q{x} x length $str; my @toMask = ( 2 .. 6, 78, 506 .. 1473, 4863, 26290 .. 37907, 107889 .. 107996); substr $mask, $_, 1, qq{\x00} for @toMask; my $resAndOrAndNot = andOrAndNot(); my $resAndRegex = andRegex(); my $resSubstrList = substrList(); die qq{Inconsistent\n} unless $resAndOrAndNot eq $resAndRegex and $resAndOrAndNot eq $resSubstrList; cmpthese (-3, { andOrAndNot => \&andOrAndNot, andRegex => \&andRegex, substrList => \&substrList, }); sub andOrAndNot { my $masked = ($str & $mask) \| ($x & ~ $mask); return $masked; } sub andRegex { my $masked = $str & $mask; $masked =~ s{\x00}{x}g; return $masked; } sub substrList { my $masked = $str; substr $masked, $_, 1, q{x} for @toMask; return $masked; } [download] produces `Rate substrList andRegex andOrAndNot substrList 26.0/s -- -8% -91% andRegex 28.3/s 9% -- -90% andOrAndNot 278/s 969% 884% --` [download] Cheers, JohnGG	[reply] [d/l] [select]
Re^3: Masking part of a string by ikegami (Patriarch) on Jun 27, 2007 at 15:02 UTC
A relevant benchmark would factor in the time to build the mask while preserving the real application's ratio of mask rebuilds to the number of operations found. Right now, you ignore the time to build the mask in two tests, while including it in the third test. Depending on that ratio, `substrList` is faster than `andOrAndNot`.	[reply] [d/l] [select]
Re^4: Masking part of a string by johngg (Canon) on Jun 27, 2007 at 16:20 UTC
Re: Masking part of a string by ferreira (Chaplain) on Jun 27, 2007 at 19:44 UTC
I could not resist giving a functional and expensive solution to the problem with `pairwise` function from List::MoreUtils. `my $mask = '001111100'; my $str = 'AGACGAGTA'; my @mask = split( '', $mask ); my @str = split( '', $str ); my $masked = join '', pairwise { $a ? 'x' : $b } @mask, @str; print "Masked: $masked\n";` [download] And now using regexes: `my $mask = '001111100'; my $str = 'AGACGAGTA'; my $masked = ''; while ( $mask =~ /\G(.)/gc ) { # walk the mask my $bit = $1; if ( $str =~ /\G(.)/gc ) { # walk the string to be masked $masked .= $bit ? 'x' : $1; } } print "Masked: $masked\n";` [download] Probably it could be improved in space if mask is represented as a bit vector and there is an iterator to walk the mask just like `$mask =~ /\G(.)/gc` is doing.	[reply] [d/l] [select]


Perl-Sensitive Sunglasses
	PerlMonks