R - Rcpp Math.Min 问题中的 C++ 代码再现

Question

我正在尝试重现我发现 here 关于 LevenshteinDistance 的 C++ 代码。

更准确地说，我正在尝试重现以

开头的部分

static int LevenshteinDistance(string s, string t)

直到

  return d[n, m];
 }

但是，我在使用 Math.Min(Math.Min( 时遇到错误。我不确定 rcpp 中的翻译是什么。我试过 min 但它似乎不起作用。任何线索？

// [[Rcpp::export]]
NumericVector LevenshteinDistance(NumericVector s, NumericVector t) {
    int n = s.size();
    int m = t.size();
    NumericMatrix d(n+1, m+1);

    if (n == 0)
    {
      return m;
    }

    if (m == 0){
      return n;
    }

    for (int i = 0; i < n; i++)
      d(i, 0) = i;
    for (int j = 0; j < m; j++)
      d(0, j) = j;

    for (int j = 1; j < m; j++)
      for (int i = 1; i < n; i++)
        if (s(i - 1) == t(j - 1))
          d(i, j) = d(i - 1, j - 1);  //no operation
        else
            d(i, j) = min(
            d(i - 1, j) + 1,    //a deletion
            d(i, j - 1) + 1),   //an insertion
            d(i - 1, j - 1) + 1 //a substitution
        );
        return d(n, m);
  }

所以

d(i, j) = min(

我收到此错误消息：no matching function。

Answer 1

三个问题真的：

你打错了

d(i, j) = min(
d(i - 1, j) + 1,    
d(i, j - 1) + 1),  //typo here with )
  d(i - 1, j - 1) + 1 
)

std::min() is defined to be between two values e.g. std::min(obj1,obj2)的使用而你的目标是R使用min()。

所以，

min(c(1,2,3,4))

但是，C++ definition of std::min要求写成：

std::min(1, std::min(2, std::min(3,4)));

如果您想忠实于 LevenshteinDistance 的 string 概念，则需要将值进入函数的方式从 NumericVector 类型切换为任何一种以下之一：std::string、std::vector<std::string>（参见 Gallery Post: Strings with Rcpp), Rcpp::StringVector (see Gallery Post: Working with Rcpp StringVector）或 Rcpp::CharacterVector。

以下应该足够了：

#include <Rcpp.h>

// [[Rcpp::export]]
int LevenshteinDistance(std::string s,
                        std::string t) {

  // Number of elements
  int n = s.size();
  int m = t.size();
  Rcpp::IntegerMatrix d(n+1, m+1);
  Rcpp::Rcout << "n:" << n << ", m:" << m << std::endl;

  if (n == 0){
    return m;
  }

  if (m == 0){
    return n;
  }

  for (int i = 0; i <= n; i++){
    d(i, 0) = i;
  }

  // No sense to revisit the (0,0) coordinate
  for (int j = 1; j <= m; j++){
    d(0, j) = j;
  }

  for (int j = 1; j <= m; j++){

    for (int i = 1; i <= n; i++){

      if (s[i - 1] == t[j - 1]){

        d(i, j) = d(i - 1, j - 1);  // no operation

      } else {

        d(i, j) = std::min(d(i - 1, j) + 1,    //a deletion
                           std::min(d(i, j - 1) + 1,   //an insertion
                           d(i - 1, j - 1) + 1)); //a substitution

      } // end if

    } // end inner for

  } // end outer for

  return d(n, m);
}

编写此函数后，我们可以选择编写一个快速包装器来处理不同维度的比较，例如多个源与目标等...

// [[Rcpp::export]]
Rcpp::IntegerVector LevenshteinDistance_Vector(std::vector<std::string> s,
                                               std::string t){

  // Number of Sources
  unsigned int sn = s.size();

  Rcpp::IntegerVector o(sn); // populates automatically with 0.

  for(unsigned int i = 0; i < sn; i++){
    o(i) = LevenshteinDistance(s[i],t);
  }

  return o;
}

R - Rcpp Math.Min 问题中的 C++ 代码再现

R - C++ code reproduction in Rcpp Math.Min issue

rcpp

levenshtein-distance