Return to Answer

Duh.

Source Link

edited Jun 13, 2012 at 14:30

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, c), std::min(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.

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, c), std::min(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.

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.

Source Link

answered Apr 18, 2012 at 10:01

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, c), std::min(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.