比较字符串向量并量化差异

Question

比较字符串向量并量化差异

4

这段文字的意思是比较两个字符串向量，例如：

df <- data.frame(a = c("New York 001", "Orlando 002", "Boston 003", "Chicago 004", "Atlanta 005"),
                 b = c("NEW YORK  001", "Orlando", "Boston (003)", "Chicago 005", "005 Atlanta"))

我会尽力为您翻译。这段内容涉及编程，需要添加一列具有数字值的c列，以提供某种程度的精确度。

我的思路：

我们有这个：

> df
             a             b
1 New York 001 NEW YORK  001
2  Orlando 002       Orlando
3   Boston 003  Boston (003)
4  Chicago 004   Chicago 005
5  Atlanta 005   005 Atlanta

首先，去除空格，忽略大小写并同时删除所有特殊字符。

df$a <- gsub("[[:space:]]|[[:punct:]]", "", toupper(df$a))
df$b <- gsub("[[:space:]]|[[:punct:]]", "", toupper(df$b))

我们得到的是：

> df
           a          b
1 NEWYORK001 NEWYORK001
2 ORLANDO002    ORLANDO
3  BOSTON003  BOSTON003
4 CHICAGO004 CHICAGO005
5 ATLANTA005 005ATLANTA

所以现在我们来到了问题的核心。

第一行是100%匹配。第二行在a列中有10个字符中的7个匹配，因此为70%。第三行现在完全匹配。第四行有90%的匹配。第五行比较棘手。人类的大脑告诉我它们匹配，但是顺序有问题。但这不是计算机的工作方式。实际上，可以将它们测量为70%的匹配，因为两个字符串中有7个连续字符重复。

所以问题是：

如何进行字符串比较的定量度量？

也许有更好的方法来做到这一点，因为我从未经历过在部分匹配上比较字符串集。而且想出这种特定的可量化的度量只是我直觉上做事情的方式。如果R已经有一个库/函数以更好的方式完成所有这些工作，而我只是不知道，那我不会感到惊讶。

- statespace

在你的实向量中，我们可以假设两个字符串之间唯一不同的是数字？如果是这种情况，你只需要比较数字，这样会更快更容易，只需将它们剥离出来进行比较或计算差异。 - grrgrrbla

不，其实不是。文本字符串可以是任何内容，因此通用解决方案更可取。我在考虑一些连续匹配[0-9a-zA-Z]的数量除以最长字符串的方法。 - statespace

不做更多假设，我想不出其他方法，只能通过循环逐渐比较a和b的部分并在它们不匹配时退出，认真思考你想比较的两个向量，并寻找简化问题的模式，否则循环是你唯一的选择。当然，有很多人比我聪明，也许其中有人能想出更好的解决方案。 - grrgrrbla

哦，我的天啊。好的，谢谢你的建议。我会尽力进行更多的研究，但是我很确定这个问题在其他地方已经出现过，并且有一个准备好的工具可以正确地解决它。我会更新我的进展情况。 - statespace

如果在R中无法实现，我也会尝试其他语言，比如Python。 - grrgrrbla

显示剩余3条评论

3个回答

7

我已经得出了自己问题的相对简单的答案。它是莱文斯坦距离。或者在R中用adist()函数。

长话短说：

df$c <- 1 - diag(adist(df$a, df$b, fixed = F)) / apply(cbind(nchar(df$a), nchar(df$b)), 1, max)

这很有用。

> df
           a          b   c
1 NEWYORK001 NEWYORK001 1.0
2 ORLANDO002    ORLANDO 0.7
3  BOSTON003  BOSTON003 1.0
4 CHICAGO004 CHICAGO005 0.9
5 ATLANTA005 005ATLANTA 0.7

更新：

在我的一个数据集上运行该函数返回了有趣的结果（让我的内心小宅男有些笑了）：

Error: cannot allocate vector of size 1650.7 Gb

所以，我猜这是另一个apply()循环用于adist()，取整个矩阵的对角线...嗯，效率相当低下。

df$c <- 1 - apply(cbind(df$a, df$b),1, function(x) adist(x[1], x[2], fixed = F)) / apply(cbind(nchar(df$a), nchar(df$b)), 1, max)

这个修改可以得到非常令人满意的结果。

- statespace

4

使用 stringdist 包，计算 Damerau-Levenshtein 距离:

#data
df <- read.table(text="
a          b
1 NEWYORK001 NEWYORK001
2 ORLANDO002    ORLANDO
3  BOSTON003  BOSTON003
4 CHICAGO004 CHICAGO005
5 ATLANTA005 005ATLANTA",stringsAsFactors = FALSE)


library(stringdist)
cbind(df, lavenshteinDist = stringsim(df$a, df$b))
#            a          b lavenshteinDist
# 1 NEWYORK001 NEWYORK001             1.0
# 2 ORLANDO002    ORLANDO             0.7
# 3  BOSTON003  BOSTON003             1.0
# 4 CHICAGO004 CHICAGO005             0.9
# 5 ATLANTA005 005ATLANTA             0.4

编辑：
有许多算法可以量化字符串相似度，您需要在您的数据上进行测试并选择合适的算法。以下是测试所有算法的代码：

#let's try all methods! 
do.call(rbind,
        lapply(c("osa", "lv", "dl", "hamming", "lcs", "qgram",
                 "cosine", "jaccard", "jw", "soundex"),
               function(i)
                   cbind(df, Method=i, Dist=stringsim(df$a, df$b,method = i))
               ))

- zx8754

我看到的主要缺点是ATLANTA，OP希望获得70％而不是40％...（这只是一个旁注） - Tensibai

1

@Tensibai，这是关于选择正确的字符串相似度方法的问题，对于这种情况，“lcs”方法给出了类似的结果- 1.0, 0.8, 1.0, 0.9, 0.7，在我的帖子中我使用了默认的“osa”。 - zx8754

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tensibai · Accepted Answer

使用Rcpp的更加正确的答案：

library(Rcpp)

cppFunction('NumericVector commonChars(CharacterVector x, CharacterVector y) {
  int len = x.size();
  NumericVector out(len);
  double percentage;

  int count=0,k=0;
  std::string compared;
  std::string source;

  for (int i=0; i<len;++i) {
    source = x[i];
    compared = y[i];
    count=0;
    k=0;

    for (int j=0;j<compared.length();j++) {
      if (source[j] == compared[j]) { count++; continue; }

      while(k < source.length()) {
        if (source[j] == compared[k]) { count++; break; }
        k++;
      }
    }
    percentage = (count+0.0)/(source.length()+0.0);
    out[i] = percentage;
  }
  return out;
}')

提供：

> commonChars(df$a,df$b)
[1] 1.0 0.7 1.0 0.9 0.7

我没有将它与其他答案或大型数据框进行对比。

不完全符合你的意愿，但这是一个想法（我会尝试改进它）：

df$r <- gsub("\\w","(\1)?",df$a)
for (i in 1:length(df$a)) {
   df$percentage[i] < ( as.integer( 
                           attr( 
                             regexpr( df$r[i], df$b[i]), 
                             "match.length" 
                           ) 
                       ) / str_length(df$a[i]) * 100) 
}

输出：

               a          b                                        r percentage
1 NEWYORK001 NEWYORK001 (N)?(E)?(W)?(Y)?(O)?(R)?(K)?(0)?(0)?(1)?        100
2 ORLANDO002    ORLANDO (O)?(R)?(L)?(A)?(N)?(D)?(O)?(0)?(0)?(2)?         70
3  BOSTON003  BOSTON003     (B)?(O)?(S)?(T)?(O)?(N)?(0)?(0)?(3)?        100
4 CHICAGO004 CHICAGO005 (C)?(H)?(I)?(C)?(A)?(G)?(O)?(0)?(0)?(4)?         90
5 ATLANTA005 005ATLANTA (A)?(T)?(L)?(A)?(N)?(T)?(A)?(0)?(0)?(5)?         30

缺点：

有一个for循环
ATLANTA005只因为005与订单匹配而返回30%。

我会看看是否能找到一种更好的正则表达式构建方式。