StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It so happens I reinvented this wheel many years ago - in a FORTRAN program on a mainframe :)</p> <p>When I proudly told other people on the Internet about my algorithm, they laughed and pointed me at the two (four?) big names in this area:</p> <ul> <li><a href="http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm" rel="nofollow noreferrer">Needleman-Wunsch</a> and</li> <li><a href="http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm" rel="nofollow noreferrer">Smith-Waterman</a>.</li> </ul> <p>These are algorithms for comparing huge sequences of similar strings. Memory requirement is about <code>m + n</code>, where m and n are the sizes of the strings, and runtime is about <code>m * n</code>.</p> <p>Gunslinger47 mentions Levenshtein, Soundex and Metaphone. Levenshtein is also a powerful means of computing string distances, but it's better suited for "normal" text. Soundex and Metaphone compute a short string intended to encode the sound of the string when spoken by a human... they become ineffective after about 3 syllables, they're really intended for words in human language rather than strings of genomes or such.</p> <p><strong>EDIT</strong></p> <p>Oops, I just found my 4 big names at the bottom of the article you cited. So you're already aware of them. I think that if you search for those names and "Java" should find you implementations. <a href="http://www25.brinkster.com/denshade/NeedlemanWunsch.java.htm" rel="nofollow noreferrer">Here's the first one I found</a>.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload