Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot

Re^5: Hamming Distance Between 2 Strings - Fast(est) Way?

by BrowserUk (Pope)
on Oct 14, 2005 at 17:58 UTC ( #500396=note: print w/replies, xml ) Need Help??

in reply to Re^4: Hamming Distance Between 2 Strings - Fast(est) Way?
in thread Hamming Distance Between 2 Strings - Fast(est) Way?

This is not my field, but ...
\ | / <<< <<< <<< <<< <<< -- O -- / | \ """""\ """===(° "(O)" \ \u =¯ | \__)

That was your whole second paragraph going right over my head. T'ain't mine ivver! :)

However, you're right that the bio guys do this sort of fuzzy comparison a lot--a lot a lot. And they frequently exhaustively cross compare huge volumes of very large strings. I was involved in a whole other thread here aimed at finding the fastest way to do exactly that in Perl.

So, encoding 4 RAs per char and saving 75% memory and 75% of comparison time would be a huge saver--if you can get the encoding data/decoding results costs down.

Maybe using C, but vec is just too slow, as you have to access every 2-(3-,4-)bit offset individually at the perl level. Maybe a XS/C/asm module that takes a list of numbers and a bit size and returns a fully encoded string.

However, there is still another problem that I hadn't thought about before. This works ok for two equal length strings, but more often than not, the task is to compare relatively short fragments against huge sequences to try and locate (likely) positions at which the fragment matches. In that scenario, the shorter fragment has to be tried at all offsets against the longer. That means you would need to encode each fragment 4 times, and use them cyclically against the sequence in order to test all positions.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://500396]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (3)
As of 2020-11-27 03:37 GMT
Find Nodes?
    Voting Booth?

    No recent polls found