3
$\begingroup$

Let $s_a$ and $s_b$ be two strings over a $q$-ary alphabet. For each character $(c_1,...c_q)$ in the alphabet, I'd like to return a pair of values $(r,k)$ where $r$ represents the count for the character in $s_a$ and $k$ represents the number of instances where this character is in the same position in $s_a$ and $s_b$.

For example, if we have two binary strings:

sa="00011001";
sb="11001001";

For the character $0$, we'd return the value $(r_0,k_0) = (5,3)$. For the character $1$, we'd return $(r_1,k_1) = (3,2)$.

What is the fastest way to carry out these string operations? Should we be using arrays instead of strings?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Related: How to find the distance of two lists?. $\endgroup$
    – Artes
    Jan 21, 2014 at 2:28
  • $\begingroup$ @Artes Thanks - I looked up the string distance functions in the help, and I couldn't find a way to compute this specific metric (where the strings are the same for a given character). $\endgroup$
    – user11875
    Jan 21, 2014 at 2:30
  • $\begingroup$ If the first string does not have a character from the alphabet, do you require a zero count returned, or are you only interested in characters present? $\endgroup$
    – ciao
    Jan 21, 2014 at 2:31
  • $\begingroup$ @rasher If the first character is not present in $s_a$ we'd just return $(0,0)$, or at least something indicating this happened. $\endgroup$
    – user11875
    Jan 21, 2014 at 2:38

3 Answers 3

Reset to default
2
$\begingroup$

This does the trick:

s1 = {0, 0, 0, 1, 1, 0, 0, 1};
s2 = {1, 1, 0, 0, 1, 0, 0, 1};
alphabet = {0, 1};

With[{ss = Transpose[{#1, #2}], s1 = #1, s2 = #2, alp = #3},
{#, {Count[s1, #], Count[ss, {#, #}]}} & /@ 
alp] &[s1, s2, alphabet]

(* {{0, {5, 3}}, {1, {3, 2}}} *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ @user11875: Thanks for accept, might want to wait for other ideas in the future. Also, updated my post to use lists matching your example (I chose lists as a better generalization) and to fix a gotcha with numeric strings (equal threads, so matches get collapsed), and made it into a function, so just fill in the blanks for s1,s2, and alphabet at the end. $\endgroup$
    – ciao
    Jan 21, 2014 at 3:53
3
$\begingroup$

I would do it by converting the strings to numbers, then using fast numeric functions BitXor, Unitize, etc.

A definition for one-at-a-time applications:

rkfn[a_String, b_String, x_String] /; Equal @@ StringLength /@ {a, b} :=
  Module[{na, nb, nx, f},
    {na, nb, {nx}} = ToCharacterCode[{a, b, x}];
    f[z_, c_: 1] := Subtract[1, Unitize @ BitXor[z, c na]];
    Tr /@ {f[nx], f[nx, f[nb]]}
  ]

And one for all counts at once with somewhat better efficiency:

rkfn[a_String, b_String] /; Equal @@ StringLength /@ {a, b} :=
  Module[{na, nb, ut, xab},
    {na, nb} = ToCharacterCode[{a, b}];
    ut = Subtract[1, Unitize @ BitXor[##]] &;
    xab = na * ut[na, nb];
    Table[
      {FromCharacterCode @ nx, Tr @ ut[nx, na], Tr @ ut[nx, xab]},
      {nx, Union[na, nb]}
    ]
  ]

Test:

{sa, sb} = {"abbabdaaac", "ababbaaccc"};

rkfn[sa, sb, "b"]

{3, 2}

rkfn[sa, sb]

{{"a", 5, 2}, {"b", 3, 2}, {"c", 1, 1}, {"d", 1, 0}}

This method is very fast; comparing two strings of 15 million characters each:

{sa, sb} = StringJoin /@ RandomChoice[CharacterRange["a", "z"], {2, 15*^6}];

rkfn[sa, sb, "j"] // Timing

{0.312, {576135, 22210}}

rkfn[sa, sb] // Timing // First  (* timing for full alphabet *)

6.162
Improve this answer
$\endgroup$
2
  • $\begingroup$ @Mr.Wizard I just need to say that this answer is very cool. $\endgroup$
    – user11875
    Jan 21, 2014 at 19:50
  • $\begingroup$ @user11875 Thanks. :-) By the way, I modified the "all at once" code for better efficiency by eliminating some redundancy. $\endgroup$
    – Mr.Wizard
    Jan 22, 2014 at 3:05
2
$\begingroup$

For one-at-a-time queries :-

sa = "00011001";
sb = "11001001";

pairs = Transpose[{a, b} =
    ToCharacterCode /@ {sa, sb}];

f = Function[x, {Count[a, x],
      Count[pairs, {x, x}]}]@
    First@ToCharacterCode@# &;

f["0"]

{5, 3}

Improve this answer
$\endgroup$
1
  • $\begingroup$ Clean. I'd way over-thought this, ended up with something similar to do all-at-once. +1 $\endgroup$
    – ciao
    Jan 21, 2014 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.