current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 6 down vote favorite 
#include <cassert>
#include <string>
#include <vector>
using namespace std;

inline size_t min(size_t x, size_t y, size_t z)
{
    if (x < y)
        return x < z ? x : z;
    else
        return y < z ? y : z;
}

size_t edit_distance(const string& A, const string& B)
{
    size_t NA = A.size();
    size_t NB = B.size();

    vector<vector<size_t>> M(NA + 1, vector<size_t>(NB + 1));

    for (size_t a = 0; a <= NA; ++a)
        M[a][0] = a;

    for (size_t b = 0; b <= NB; ++b)
        M[0][b] = b;

    for (size_t a = 1; a <= NA; ++a)
        for (size_t b = 1; b <= NB; ++b)
        {
            size_t x = M[a-1][b] + 1;
            size_t y = M[a][b-1] + 1;
            size_t z = M[a-1][b-1] + (A[a-1] == B[b-1] ? 0 : 2);
            M[a][b] = min(x,y,z);
        }

    return M[A.size()][B.size()];
}

int main()
{
    assert(edit_distance("ISLANDER", "SLANDER") == 1);
    assert(edit_distance("MART", "KARMA") == 5);
    assert(edit_distance("KITTEN", "SITTING") == 5);
    assert(edit_distance("INTENTION", "EXECUTION") == 8);
}
share|improve this question

2 Answers 2

up vote 7 down vote

  • Implementation:

    • It’s generally discouraged to open namespaces (using namespace …;). Instead, import single symbols (using std::vector;) or qualify symbols explicitly.

    • Three-ways min can be written entirely in terms of std::min:

      template <typename T>
T min(T const& a, T const& b, T const& c) {
   return std::min(std::min(a, b), c);
}

  • “Bug”: the edit distance generally defines the cost for a substitution as 1 (since Levenshtein defined three equivalent edit operations), not 2 which you used in your code;

  • Algorithmic: Your code needs O(n * m) space. There’s a not too hard to implement variant which requires just O(min{n, m}) due to the fact that for the computation we only need to save the previous column (or row). In fact, with a bit of trickery you can make do with a single vector and two additional variables to save all the active values.

But apart from that it’s a very clean and efficient implementation.

share|improve this answer
    
In practice using namespace std; is placed in a global header for most C++ projects and code is written to avoid name collisions with the standard library. –  user1131146 account abandoned Apr 19 '12 at 17:09
3  
@user1131467 using namespace std; in a header is unacceptable. That’s effectively a bug, since this declaration cannot be reversed and this will lead to conflict with other libraries over which you have no control, because the effect is nonlocal. This practice precludes every use of 3rd party libraries, and requires very careful coding on your part to boot; I would also discourage avoiding name collisions with the standard library – this makes some obvious names unavailable (which leads to obtuse, non-obvious naming) and this is a problem that’s solved by namespaces. –  Konrad Rudolph Apr 19 '12 at 17:52
3  
@user1131467 The fact that thousands of programmers look at examples of bad legacy code and copy what they see does not magically make it good practice. Konrad makes an excellent point here, but of course you're always free to do with it what you wish. –  Daniel Standage Apr 20 '12 at 3:43
4  
@user1131467 You are wrong if you think this is not a problem in practice. It can cause very common name clashes, it’s definitely not “the very odd occasion”. And I don’t think it’s used in the headers of many modern C++ projects (but 80% of everything is crap according to Sturgeon’s law). And there’s a difference between qualifying names and boilerplate code as the latter would be avoidable with a better language design. But qualifying name happens in every well-designed language. Writing a single using [namespace] declaration at the beginning of a file cannot be too much to ask for. –  Konrad Rudolph Apr 20 '12 at 9:17
3  
@user1131467 No, it's not only a problem when you do that. It's also a problem when you forget to using namespace phoronix and now you're inadvertedly using std::ref when you meant phoronix::ref, but the compiler doesn't help you in the slightest there. It's also a problem when ADL picks up the wrong things because you never intended for ADL to be doing anything here. Wrapping an #include in a namespace is also a bad idea that will probably lead to linker errors down the line. –  R. Martinho Fernandes Apr 20 '12 at 13:08
up vote 5 down vote

I hope you're enjoying the NLP class. I do. :)

Min

inline size_t min(size_t x, size_t y, size_t z)
{
    if (x < y)
        return x < z ? x : z;
    else
        return y < z ? y : z;
}

This could be rewritten as:

size_t min(size_t x, size_t y, size_t z)
{
    return x < y ? min(x,z) : min(y,z);
}

Drop inline since the compiler knows better than you when to inline functions. std::min makes it clearer that you're using the standard library, but since you wrote using namespace std;, I didn't include it. You can further improve it by using a template:

template<class T> T min(T a, T b, T c) {
    return a < b ? std::min(a, c) : std::min(b, c);
}

It now works on all types supporting operator<.

size_t

I think int is more idiomatic than size_t for your M matrix, since you're not storing a size but a distance.

Performance: You could improve memory usage by storing only two rows of M. But this would prevent your from backtracking to print the alignment, and isn't a huge win anyway (except if you're working on very large strings).

General comments Your code is really straightforward and well-written. The algorithm is simply translated, and the rest of the function is simply the initialization: there's nothing complicated, and the code is easy to read. Good job!

share|improve this answer
1  
“isn’t a huge win” – actually it is, even on moderately-sized strings (couple thousand characters each, which is just a short text). On still larger data a linear-space implementation becomes crucial. And note that, using Hirshberg’s algorithm, you can even retrieve the alignment in linear space. –  Konrad Rudolph Apr 18 '12 at 15:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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