如何在 Linux 中的文本文件的特定字段中找到相同和相似的字符串？

Question

我提前道歉 - 我不确定仅使用 Linux 命令行 fu 是否有这个问题的答案。请注意我不是程序员，但在过去几年里我一直在玩 bash 和 python。

我有一个大文本文件，其中的行和列类似于以下内容（注意 - 字段用制表符分隔）：

1074    Beetle  OOB11061MNH 12/22/16    Confirmed   
3430    Hightop 0817BESTYET 08/07/17    Queued  
3431    Hightop 0817BESTYET 08/07/17    Queued  
3078    Copland 2017GENERAL 07/07/17    Confirmed   
3890    Bartok  FOODS   09/11/17    Confirmed
5440    Alphapha    00B1106IMNH 01/09/18    Queued

我想要做的是仅查找并输出第三个字段与列表中的另一个字段相同或相似的那些行。我真的不在乎其他字段是否相似，但它们都应该包含在输出中。类似地，我的意思是在该特定字段中不超过 [n] 个字符不同（例如，不超过 3 个字符不同）。所以我想要的输出是：

1074    Beetle  OOB11061MNH 12/22/16    Confirmed   
3430    Hightop 0817BESTYET 08/07/17    Queued  
3431    Hightop 0817BESTYET 08/07/17    Queued  
5440    Alphapha    00B1106IMNH 01/09/18    Queued

从1074开始的行有第三个字段与5440相差3个字符，所以它们都包括在内。包括 3430 和 3431，因为它们完全相同。 3078和3890因为不相似被淘汰

通过谷歌搜索论坛，我设法将这个相当长的管道拼凑在一起，以便能够找到字段 3 完全相同的所有实例：

cat inputfile.txt | awk 'BEGIN { OFS=FS="\t" } {if (count[] > 1) print [=13=]; else if (count[] == 1) { print save[]; print [=13=]; } else save[] = [=13=]; count[]++; }' > outputfile.txt

我必须承认我不太了解 awk；我只是从网上复制和改编。但这似乎非常适合查找精确的重复项（即，它只会输出上面的 3430 和 3431）。但是我不知道如何尝试找到不相同但不超过 3 个地方不同的字符串。

例如，在我上面的示例中，它应该匹配 1074 和 5440，因为它们都符合模式： ??B1106?MNH

但我希望它也能够匹配任何其他随机匹配模式，只要差异不超过三个，如下所示： 20?7G?N?RAL

这些差异可以任意出现在任何位置。

需要这个的原因是我们正在尝试找到一种方法来自动查找类似序列号的字段中的印刷错误。可能有一个错误的键，或者一个字母 "O" 被数字“0”替换，等等。

所以...有什么想法吗？感谢您的帮助！

Answer 1

你可以使用这个脚本

 $ more hamming.awk

  function hamming(x,y,xs,ys,min,max,h) {
    if(x==y) return 0;
    else {
      nx=split(x,xs,"");
      mx=split(y,ys,"");
      min=nx<mx?nx:mx;
      max=nx<mx?mx:nx;
      for(i=1;i<=min;i++) if(xs[i]!=ys[i]) h++;
      return h+(max-min);     
    }
  }  
  BEGIN   {FS=OFS="\t"}
  NR==FNR {
      if( in a) nrs[NR];
      for(k in a)
        if(hamming(k,)<4) {
           nrs[NR];
           nrs[a[k]];
        }
      a[]=NR;
      next
  }

  FNR in nrs

用法

$ awk -f hamming.awk file{,}

这是一种双扫描算法，可以找到键之间的汉明距离（您描述的距离）。请注意它是 O(n^2) 算法，因此可能不适合非常大的数据集。但是，不确定是否有其他算法可以做得更好。

注意基于我在 post 中遗漏的评论的附加说明。该算法逐字符比较键，因此不会识别位移。例如 123 和 23 将给出距离 3.

Answer 2

Levenshtein 距离又名 "edit distance" 最适合您的任务。下面的 Perl 脚本需要安装模块 Text::Levenshtein（对于 debian/ubuntu 执行：sudo apt install libtext-levenshtein-perl）。

use Text::Levenshtein qw(distance);                                                                                                                                                  

$maxdist = shift;                                                                
@ll = (<>);                                                                      
@k = map {                                                                       
    $k = (split /\t/, $_)[2];                                                    
    # $k =~ s/O/0/g;                                                             
} @ll;                                                                           
for ($i = 0; $i < @ll; ++$i) {                                                   
    for ($j = 0; $j < @ll; ++$j) {                                               
        if ($i != $j and distance($k[$i], $k[$j]) < $maxdist) {                  
            print $ll[$i];                                                       
            last;                                                                
        }                                                                        
    }                                                                            
}

用法：

perl lev.pl 3 inputfile.txt > outputfile.txt

算法与@karakfapost中的算法相同O(n^2)，但匹配更灵活。

另请注意注释行 # $k =~ s/O/0/g;。如果取消注释，key 中的所有 O 将变为 0，这将修复 O->0 转换损坏的 key。在处理损坏的数据时，我总是使用这样的小规则来逐步修复数据，将规则从运行运行细化到数据几乎完美的程度，不再需要模糊匹配。

如何在 Linux 中的文本文件的特定字段中找到相同和相似的字符串？

How can I find both identical and similar strings in a particular field in a text file in Linux?

bash

awk

grep

sed

uniq