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.
#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
add comment

3 Answers

  • 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
2  
@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
2  
@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
3  
@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
show 9 more comments

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
add comment

(This is for the updated code.)

  • Since you’re already using C++11, why not use a variadic template argument list for min rather than an initializer_list? That way, you could invoke it as min(a, b, c) and it might be slightly more efficient (just guessing).

  • I don’t like loops. If you want to get geeky you can replace the initialisation of M0 with

    size_t acc = 0;
    generate(begin(M0), end(M0), [&acc]() { return ++acc; });
    

    But yes, that’s overkill.

  • But actually, using ++ is wrong here (in your code too!) – you need to use b * insert_cost! Your code only works by accident (since that cost happens to be 1). Same for the initialisation of M1[0] inside the main loop.

  • I really dislike multiple declarations on one line (M0 and M1).

  • I would contemplate looping over the strings rather than over the arrays. Having a loop condition of the form b = 1; b <= NB is very unconventional and screams “ERROR” – even though it’s actually correct here.

    But I’ve been conditioned (and that’s a good thing!) to recognise loops over a range, and they always have the form i = 0; i < N and my brain automatically rejects every other form as potential bug. This constitutes a stumbling block in understanding the code – I have to make a conscious effort to parse the loop.

share|improve this answer
1  
min of three parameters means the third is comparitor, that is why std::min(a,b,c) is different from std:min({a,b,c}). There is no difference in compiled code between an initializer_list version and a variadic template version, –  user1131146 account abandoned Apr 20 '12 at 3:32
    
I am looping ( b in [1,NB] ) over the element index of the array item that will be set on each iteration (M1[b]). Looping over a range other than [0,N) is not an error, and you need to read more code if you think it is. –  user1131146 account abandoned Apr 20 '12 at 3:44
    
@user1131467 “loop comment is silly” – no, that comment was silly. And the “personal preference“ is simply a shortcut for saying “I suspect there is an objective advantage but it’s hard to quantify”. I could also have said “it’s more readable”. To say that “functional style is harder to read than an imperative one” is ridiculous and out of sync with the consensus among professional programmers. Finally, you have completely failed to understand my argument about the loop indices. Suggested reading: Making wrong code look wrong –  Konrad Rudolph Apr 20 '12 at 9:21
1  
From the Google Coding Guidelines: '...coding practices [that] can hamper readability [such as] an excessively "functional" style of programming.'. –  user1131146 account abandoned Apr 20 '12 at 12:23
1  
@user1131467 the keyword here is “excessive”. Incidentally, I agree that this particular example is excessive – but only because of the stateful lambda. If C++ had a predefined successor or natural_numbers generator, I would definitely recommend this over the loop. Furthermore, the Google Coding Guidelines recommend some very questionable practices (and some which plainly only apply to Google’s very specific requirements) and are not viewed as unanimously positive by the C++ community (such as the non-use of exceptions). –  Konrad Rudolph Apr 20 '12 at 12:31
add comment

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.