如何合并相似的字符串并显示最常见的字符

Question

在一个数据框中，我有一列字符串，它们彼此之间非常相似，只是通过%的差异来区分。我想将这些共同点字符串组合成一个单一的字符串，在每个位置上具有最常见的字符。

数据框如下：

pattern  Freq     score rank
DT%E 37568 1138.4242    1
%TGE 37666 1018.0000    2
D%GE 37641 1017.3243    3
DTG% 37665  965.7692    4
%VGNE 34234  684.6800    5
SVGN% 34281  634.8333    6
SV%NE 34248  634.2222    7
SVG%E 34265  623.0000    8
%LGNE 41098  595.6232    9
SL%NE 41086  595.4493   10
SLGN% 41200  564.3836   11
SPT%AYNE 35082  539.7231   12
SP%AAYNE 35094  531.7273   13
SPTA%YNE 35061  531.2273   14
SPTAA%NE 35225  518.0147   15
SPTAAYN% 35144  516.8235   16
%PTAAYNE 35111  516.3382   17
S%TAAYNE 35100  516.1765   18
SPTAAY%E 35130  509.1304   19
SLG%E 41467  450.7283   20

我试图添加另一列，其中包含来自Pattern列最可能的字符串。

pattern  Freq     score rank  true_string
DT%E 37568 1138.4242    1  DTGE
%TGE 37666 1018.0000    2  DTGE
D%GE 37641 1017.3243    3  DTGE
DTG% 37665  965.7692    4  DTGE
%VGNE 34234  684.6800    5  SVGNE
SVGN% 34281  634.8333    6  SVGNE
SV%NE 34248  634.2222    7  SVGNE
SVG%E 34265  623.0000    8  SVGNE
%LGNE 41098  595.6232    9  SLGNE
SL%NE 41086  595.4493   10  SLGNE
SLGN% 41200  564.3836   11  SLGNE
SPT%AYNE 35082  539.7231   12  SPTAAYNE
SP%AAYNE 35094  531.7273   13  SPTAAYNE
SPTA%YNE 35061  531.2273   14  SPTAAYNE
SPTAA%NE 35225  518.0147   15  SPTAAYNE
SPTAAYN% 35144  516.8235   16  SPTAAYNE
%PTAAYNE 35111  516.3382   17  SPTAAYNE
S%TAAYNE 35100  516.1765   18  SPTAAYNE
SPTAAY%E 35130  509.1304   19  SPTAAYNE
SLG%E 41467  450.7283   20  SLGNE

- El David

---

这似乎相当困难。使用任何标准距离度量来分离SVGNE和SLGNE似乎特别棘手。 - thelatemail

是的，你没有提供可能出现且不容易分配的示例S％GNE。 - Calum You

Answer 1

这是一个棘手但有趣的问题。

以下内容可以给您一些思路（并重现了您的预期输出）；请注意，这是一种经验性方法，其假设如下：

1. 总是有属于同一个true_string的>=2个模式; 这对于（分层）聚类方法的工作是必要的（见下文）。如果您只有<2个定义true_string的模式，则无法使用此方法，这是有意义的，因为您会在相同位置获得两个字符出现的相等频率。

2. 所有pattern具有相同的长度； 即，我们仅考虑单个字符替换而不是插入/删除。

方法

我们利用库stringdist来计算字符串相似性。 stringdistmatrix提供各种距离度量（Levenshtein，Hamming等），有关详细信息请参见?stringdist::stringdistmatrix。在这种情况下，我们使用method = "qgram"，因为它产生与您的预期输出一致的分组（因此早先的“经验性”警告）。我不知道这对于您的实际数据是否适用，因此重要的是要记住，您可能需要尝试不同的方法来找到与您的预期相符的距离相似性度量。

在计算了字符串距离矩阵之后，我们使用分层聚类对字符串进行聚类；我们基于将垂直距离设置为v = 2来添加grp标签，并使用自定义的get_consensus_string函数来推断每个grp的共识字符串；正如开头所述，该函数假设一个grp中的所有字符串具有相同的长度，并针对字符串中的每个位置选择具有最大出现频率的字符。

代码

首先是自定义的get_consensus_string函数

library(tidyverse)
get_consensus_string <- function(x) {
    map_dfc(x, str_split, "") %>%
        rowid_to_column("pos") %>%
        gather(k, v, -pos) %>%
        group_by(pos, v) %>%
        add_count() %>%
        group_by(pos) %>%
        filter(n == max(n)) %>%
        arrange(pos, desc(v)) %>%
        dplyr::slice(1) %>%
        pull(v) %>%
        paste0(collapse = "")
}

我们现在可以根据来自 stringdist::stringdistmatrix 的字符串相似度距离矩阵的分层聚类结果添加基于 grp 标签；我在此处经验性地在垂直距离上剪切了树，使其为 v = 2（这是可能需要调整的参数）；一旦我们有了 grp 标签，我们就添加共识字符串。

library(stringdist)
df %>%
    mutate(grp = cutree(hclust(stringdistmatrix(df$pattern, method = "qgram")), h = 2)) %>%
    group_by(grp) %>%
    mutate(true_string = get_consensus_string(pattern)) %>%
    ungroup()
## A tibble: 20 x 6
#   pattern   Freq score  rank   grp true_string
#   <fct>    <int> <dbl> <int> <int> <chr>
# 1 DT%E     37568 1138.     1     1 DTGE
# 2 %TGE     37666 1018      2     1 DTGE
# 3 D%GE     37641 1017.     3     1 DTGE
# 4 DTG%     37665  966.     4     1 DTGE
# 5 %VGNE    34234  685.     5     2 SVGNE
# 6 SVGN%    34281  635.     6     2 SVGNE
# 7 SV%NE    34248  634.     7     2 SVGNE
# 8 SVG%E    34265  623      8     2 SVGNE
# 9 %LGNE    41098  596.     9     3 SLGNE
#10 SL%NE    41086  595.    10     3 SLGNE
#11 SLGN%    41200  564.    11     3 SLGNE
#12 SPT%AYNE 35082  540.    12     4 SPTAAYNE
#13 SP%AAYNE 35094  532.    13     4 SPTAAYNE
#14 SPTA%YNE 35061  531.    14     4 SPTAAYNE
#15 SPTAA%NE 35225  518.    15     4 SPTAAYNE
#16 SPTAAYN% 35144  517.    16     4 SPTAAYNE
#17 %PTAAYNE 35111  516.    17     4 SPTAAYNE
#18 S%TAAYNE 35100  516.    18     4 SPTAAYNE
#19 SPTAAY%E 35130  509.    19     4 SPTAAYNE
#20 SLG%E    41467  451.    20     3 SLGNE

您可以看到最终代码非常干净，并且能够重现您所期望的输出。

---

进一步的注释/评论

可能值得讨论两个问题：（1）如何选择适当的距离度量以及（2）在哪里截断树。

关于第一个问题，实证方法是尝试不同的度量标准并在对pattern进行分层聚类后可视化树状图。

例如，对于method =“qgram”，您可以执行以下操作：

mat <- as.matrix(stringdistmatrix(df$pattern, method = "qgram"))
rownames(mat) <- df$pattern
colnames(mat) <- df$pattern
plot(hclust(as.dist(mat)))

在您对聚类结果感到满意后，我们可以继续进行。

关于裁剪树的问题，一个实用/务实的方法是检查树形图并找到一个适当的高度来裁剪树（在我们的例子中，v = 2）；或者，如果您知道独特的true_string数量，您可以使用k指定群组的数量以在cutree中完成。

在更技术性的术语中，树形图的高度与完全链接使用的组之间的距离相关（即基于最不相似配对测量距离）。由于组之间的距离又基于pattern之间的q-gram距离，因此可以将高度与两个pattern之间的q-gram距离联系起来，即两个pattern的N-gram向量的绝对差异。

- Maurits Evers

---

这非常有帮助！不幸的是，更大的数据集有一些小于2的模式。有没有一种方法可以在一个步骤中将小于2的模式移动到单独的数据框中，并在最终步骤中与大于等于2的数据集合并在一起？ - El David

@ElDavid：“不幸的是，更大的数据集有一些模式<2。”嗯，这对我来说并没有太多意义；如果您只有<2个“模式”，那是否意味着您只有一个单一的“模式”定义了一个“true_string”？在这种情况下，就没有什么可以合并的了，整个聚类和识别共识字符串的过程都是无意义的。您能详细说明一下吗？ - Maurits Evers

Answer 2

我查看了Maurits的答案，但是当我添加新行时。

新输入

D%GT    12434   12421   22      DXGT
DX%T    31242   2221.2  21      DXGT

使用的数据

pattern Freq    score   rank        true_string
DT%E    37568   1138.4242   1       DTGE
D%GT    12434   12421   22      DXGT
DX%T    31242   2221.2  21      DXGT
%TGE    37666   1018    2       DTGE
D%GE    37641   1017.3243   3       DTGE
DTG%    37665   965.7692    4       DTGE
%VGNE   34234   684.68  5       SVGNE
SVGN%   34281   634.8333    6       SVGNE
SV%NE   34248   634.2222    7       SVGNE
SVG%E   34265   623 8       SVGNE
%LGNE   41098   595.6232    9       SLGNE
SL%NE   41086   595.4493    10      SLGNE
SLGN%   41200   564.3836    11      SLGNE
SPT%AYNE    35082   539.7231    12      SPTAAYNE
SP%AAYNE    35094   531.7273    13      SPTAAYNE
SPTA%YNE    35061   531.2273    14      SPTAAYNE
SPTAA%NE    35225   518.0147    15      SPTAAYNE
SPTAAYN%    35144   516.8235    16      SPTAAYNE
%PTAAYNE    35111   516.3382    17      SPTAAYNE
S%TAAYNE    35100   516.1765    18      SPTAAYNE
SPTAAY%E    35130   509.1304    19      SPTAAYNE
SLG%E   41467   450.7283    20      SLGNE

莫里茨的回答

df %>%
    mutate(grp = cutree(hclust(stringdistmatrix(df$pattern, method = "qgram")), h = 2)) %>%
    group_by(grp) %>%
    mutate(true_string = get_consensus_string(pattern)) %>%
    ungroup()
> Result 
  pattern   Freq  score  rank   grp true_string
 1 DT%E     37568  1138.     1     1 DT%T       
 2 D%GT     12434 12421     22     1 DT%T       
 3 DX%T     31242  2221.    21     1 DT%T       
 4 %TGE     37666  1018      2     2 %TGE       
 5 D%GE     37641  1017.     3     2 %TGE       
 6 DTG%     37665   966.     4     1 DT%T       
 7 %VGNE    34234   685.     5     3 SVGNE      
 8 SVGN%    34281   635.     6     3 SVGNE      
 9 SV%NE    34248   634.     7     3 SVGNE      
10 SVG%E    34265   623      8     3 SVGNE      
11 %LGNE    41098   596.     9     4 SLGNE      
12 SL%NE    41086   595.    10     4 SLGNE      
13 SLGN%    41200   564.    11     4 SLGNE      
14 SPT%AYNE 35082   540.    12     5 SPTAAYNE   
15 SP%AAYNE 35094   532.    13     5 SPTAAYNE   
16 SPTA%YNE 35061   531.    14     5 SPTAAYNE   
17 SPTAA%NE 35225   518.    15     5 SPTAAYNE   
18 SPTAAYN% 35144   517.    16     5 SPTAAYNE   
19 %PTAAYNE 35111   516.    17     5 SPTAAYNE   
20 S%TAAYNE 35100   516.    18     5 SPTAAYNE   
21 SPTAAY%E 35130   509.    19     5 SPTAAYNE   
22 SLG%E    41467   451.    20     4 SLGNE   

从上面的结果来看，它不起作用。

我的答案

library(dplyr)
library(data.table)

df <- fread(data)

string_pred <- function(x){
  
  x = x %>% mutate(CL=nchar(pattern)) 

  x_1 = x%>% select(pattern,CL)
  Chr.length = unique(x_1$CL)
  final_result = NULL
  for ( len in 1:length(Chr.length)){ 
    x_1_tmp = x %>% filter(CL==Chr.length[len])
    
    RESULT = NULL
    for(i in 1:Chr.length[len]){

      TMP = substr(x_1_tmp$pattern,i,i)
      TMP_GUESS = unique(TMP[!grepl("%",TMP)])
      if(length(TMP_GUESS)==1){
        TMP[grepl("%",TMP)] <- TMP_GUESS  
      } else {
        TMP= TMP
      }
      NAME = sprintf('P%s',i)
      
      RESULT = cbind(RESULT, NAME=TMP) %>% as.data.table()
      names(RESULT)[i] = eval(parse(text='NAME'))
    }
    material = RESULT %>% rowwise() %>% .[apply(.,1,function(x){'%' %in% x}) ,]
    if (nrow(material)==0){
      x_1_tmp =x_1_tmp %>%  mutate( pred = apply(RESULT,1,function(x)paste(as.character(x),collapse = ''))) %>% as.data.table()
    } else {
      mat.loc = RESULT %>% rowwise() %>%apply(.,1,function(x){'%' %in% x}) %>% which(unlist(.)==TRUE)
      
      for (i in 1:nrow(material)){
        ori.loc = mat.loc[i]
        loc = names(material[i,])[material[i,]=='%']
        tmp = material[i,] %>% dplyr::select(-loc)
        RESULT[ori.loc,] = RESULT %>% rowwise()  %>% inner_join(., tmp) %>% .[apply(.,1,function(x){!('%' %in% x)}) ,] %>% unique()
        
      }
      x_1_tmp = x_1_tmp %>%mutate( pred = apply(RESULT,1,function(x)paste(as.character(x),collapse = ''))) %>% as.data.table()
    }
    final_result = rbind(final_result, x_1_tmp)
  }
  return(final_result)
}

我的回答结果

> string_pred(df)

     pattern  Freq      score rank CL     pred
 1:     DT%E 37568  1138.4242    1  4     DTGE
 2:     D%GT 12434 12421.0000   22  4     DXGT
 3:     DX%T 31242  2221.2000   21  4     DXGT
 4:     %TGE 37666  1018.0000    2  4     DTGE
 5:     D%GE 37641  1017.3243    3  4     DTGE
 6:     DTG% 37665   965.7692    4  4     DTGE
 7:    %VGNE 34234   684.6800    5  5    SVGNE
 8:    SVGN% 34281   634.8333    6  5    SVGNE
 9:    SV%NE 34248   634.2222    7  5    SVGNE
10:    SVG%E 34265   623.0000    8  5    SVGNE
11:    %LGNE 41098   595.6232    9  5    SLGNE
12:    SL%NE 41086   595.4493   10  5    SLGNE
13:    SLGN% 41200   564.3836   11  5    SLGNE
14:    SLG%E 41467   450.7283   20  5    SLGNE
15: SPT%AYNE 35082   539.7231   12  8 SPTAAYNE
16: SP%AAYNE 35094   531.7273   13  8 SPTAAYNE
17: SPTA%YNE 35061   531.2273   14  8 SPTAAYNE
18: SPTAA%NE 35225   518.0147   15  8 SPTAAYNE
19: SPTAAYN% 35144   516.8235   16  8 SPTAAYNE
20: %PTAAYNE 35111   516.3382   17  8 SPTAAYNE
21: S%TAAYNE 35100   516.1765   18  8 SPTAAYNE
22: SPTAAY%E 35130   509.1304   19  8 SPTAAYNE

方法

1. 按照每个模式的字符长度进行分离

  pattern  Freq      score rank CL
1    DT%E 37568  1138.4242    1  4
2    D%GT 12434 12421.0000   22  4
3    DX%T 31242  2221.2000   21  4
4    %TGE 37666  1018.0000    2  4
5    D%GE 37641  1017.3243    3  4
6    DTG% 37665   965.7692    4  4

2. 逐个检查每个字符。

 TMP = substr(x_1_tmp$pattern,i,i)
[1] "D" "D" "D" "%" "D" "D"

如果 unique(pattern[i] except % ) == 1 --> 那么我们将分配%给unique(pattern[i] except % )

   P1 P2 P3 P4
1:  D  T  G  E
2:  D  %  G  T
3:  D  X  G  T
4:  D  T  G  E
5:  D  %  G  E
6:  D  T  G  %

4. unique(pattern[i] except % ) > 1 我们检查字符长度组中的其他行。然后我们将字符（除了%列）合并到其他字符中。

RESULT[ori.loc,] = RESULT %>% rowwise()  %>% 
                      inner_join(., tmp) %>%
                       .[apply(.,1,function(x){!('%' %in% x)}) ,] %>% unique()
>print
Joining, by = c("P1", "P3", "P4")
Source: local data frame [1 x 4]
Groups: <by row>

# A tibble: 1 x 4
  P1    P2    P3    P4   
  <chr> <chr> <chr> <chr>
1 D     X     G     T    

5. 最后我们可以预测出什么是 %

   pattern  Freq      score rank CL pred
1:    DT%E 37568  1138.4242    1  4 DTGE
2:    D%GT 12434 12421.0000   22  4 DXGT
3:    DX%T 31242  2221.2000   21  4 DXGT
4:    %TGE 37666  1018.0000    2  4 DTGE
5:    D%GE 37641  1017.3243    3  4 DTGE
6:    DTG% 37665   965.7692    4  4 DTGE

我的回答看起来不太花哨，但是它是有效的。

我建议你一步一步地跟着代码走。

- Steve Lee

---

是的，我的方法需要定义true_string的>2个模式; 在你的示例中，你为一个新的true_string添加了2个额外的pattern，所以我的解决方案在这种情况下无法工作。但是，根据OP的样本数据，似乎总是存在>2个模式，因此我不确定你的修改是否现实; 最后，我的方法非常简单、透明和明确定义了字符串操作:计算pattern字符串的相似性，使用得到的距离矩阵来聚类pattern，然后推断一致序列;整个过程可以归结为3-4行代码。 - Maurits Evers

实际上，问题出在 get_consensus_string 上（我已经进行了更改）；现在可以放宽条件，只需要定义一个 true_string 的 >=2 个 pattern 即可（对于分层聚类仍然需要 >=2）。因此，我的方法也适用于您额外添加的两行数据。 - Maurits Evers

你是对的。我同意你的答案。但我只想检查另一种情况。 - Steve Lee