使用awk来查找包含最长的重复单词

Question

例如一个域名，让我们说有一个叫domains.csv与文件如下：

1,helloguys.ca 
2,byegirls.com 
3,hellohelloboys.ca 
4,hellobyebyedad.com 
5,letswelcomewelcomeyou.org 

我试图用linux awk的正则表达式的表达式来查找包含最长重复字，所以在这种情况下，线，它将返回行

5,letswelcomewelcomeyou.org 

我该怎么办呢？

含义“立即重复”，即abcabc，但不是abcXabc。

Answer 1

由于awk正则表达式没有反向引用，因此纯awk实现会相当冗长，其用法简化了该方法。

I'ved加入一条线，为的多个最长单词的情况下的示例性输入文件：

1,helloguys.ca 
2,byegirls.com 
3,hellohelloboys.ca 
4,hellobyebyedad.com 
5,letswelcomewelcomeyou.org 
6,letscomewelcomewelyou.org 

这得到具有最长重复序列行：

cut -d ',' -f 2 infile | grep -Eo '(.*)\1' | 
awk '{ print length(), $0 }' | sort -k 1,1 -nr | 
awk 'NR==1 {prev=$1;print $2;next} $1==prev {print $2;next} {exit}' | grep -f - infile 

由于这是非常明显的，让我们分开它做什么，并看看在每个阶段的输出：

1. 删除与行号的第一列，以避免线路号码匹配与重复的数字：

   $ cut -d ',' -f 2 infile 
   helloguys.ca 
   byegirls.com 
   hellohelloboys.ca 
   hellobyebyedad.com 
   letswelcomewelcomeyou.org 
   letscomewelcomewelyou.org 
   

2. 获取与重复序列中的所有行，仅提取该重复序列：

   ... | grep -Eo '(.*)\1' 
   ll 
   hellohello 
   ll 
   byebye 
   welcomewelcome 
   comewelcomewel 
   

3. 获取每个这些行的长度：

   ... | awk '{ print length(), $0 }' 
   2 ll 
   10 hellohello 
   2 ll 
   6 byebye 
   14 welcomewelcome 
   14 comewelcomewel 
   

4. 排序的第一列，数值，递减：

   ...| sort -k 1,1 -nr 
   14 welcomewelcome 
   14 comewelcomewel 
   10 hellohello 
   6 byebye 
   2 ll 
   2 ll 
   

5. 打印这些列，其中所述第一柱（长度）具有相同的值作为第一行上的所有线的第二：

   ... | awk 'NR==1{prev=$1;print $2;next} $1==prev{print $2;next} {exit}' 
   welcomewelcome 
   comewelcomewel 
   

6. 管到这一点的grep，使用-f -参数读取标准输入作为一个文件：

   ... | grep -f - infile 
   5,letswelcomewelcomeyou.org 
   6,letscomewelcomewelyou.org 
   

限制

虽然这可以处理意见中提到的bbwelcomewelcome情况下，就会触发这种重叠图案作为welwelcomewelcome，它只有找到welwel，而不是welcomewelcome。

更AWK替代解决方案，以下sort

如由评论tripleee指出的，这可以简化为跳过sort步骤和组合两个AWK步骤和sort步骤到单个AWK步骤，有可能提高性能：

$ cut -d ',' -f 2 infile | grep -Eo '(.*)\1' | 
awk '{if (length()>ml) {ml=length(); delete a; i=1} if (length()>=ml){a[i++]=$0}} 
END{for (i in a){print a[i]}}' | 
grep -f - infile 

让我们看一下详细awk会一步，扩大变量名称为清楚：

{ 
    # New longest match: throw away stored longest matches, reset index 
    if (length() > max_len) { 
     max_len = length() 
     delete arr_longest 
     idx = 1 
    } 

    # Add line to longest matches 
    if (length() >= max_len) 
     arr_longest[idx++] = $0 
} 

# Print all the longest matches 
END { 
    for (idx in arr_longest) 
     print arr_longest[idx] 
} 

标杆

我已经超时的top one million domains file两种解决方案在评论中提到：

• 第一溶液（用sort和两个AWK步骤）：

  964438,abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijk.com 
  
  real 1m55.742s 
  user 1m57.873s 
  sys  0m0.045s 
  

• 第二种解决方案（只需一个awk步骤，不需要sort）：

  964438,abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijk.com 
  
  real 1m55.603s 
  user 1m56.514s 
  sys  0m0.045s 
  

• 而且Perl solution通过Casimir et Hippolyte：

  964438,abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijk.com 
  
  real 0m5.249s 
  user 0m5.234s 
  sys  0m0.000s 
  

我们从中学到了什么：问一个Perl的解决方案下一次;）

有趣的是，如果我们知道只会​​有一个最长的匹配，并相应地简化命令（只是head -1而不是第一个解决方案的第二个awk命令在第二种解决方案中使用awk进行或不跟踪多个最长匹配），所获得的时间仅在几秒钟的范围内。

便携性的话

显然，BSD的grep不能做grep -f -从标准输入读取。在这种情况下，管道的输出必须重定向到临时文件，然后使用此临时文件与grep -f。

Answer 2

用Perl的一种方式：

perl -F, -ane 'if (@m=$F[1]=~/(?=(.+)\1)/g) { 
    @m=sort { length $b <=> length $a} @m; 
    $cl=length @m[0]; 
    if ($l<$cl) { @res=($_); $l=$cl; } elsif ($l==$cl) { push @res, ($_); } 
} 
END { print @res; }' file 

的想法是找到用于在第二字段中的每个位置都最长重叠重复的字符串，则匹配数组进行排序和最长子串变得在第一项阵列（@m[0]）。

完成后，将当前重复子字符串（$cl）的长度与存储的长度（以前最长的子字符串）进行比较。当当前重复子字符串长于存储长度时，结果数组将被当前行覆盖，当长度相同时，当前行将被推入结果数组中。

细节：

命令行选项：

-F,设置字段分隔符,
-ane（e执行下面的代码，n一次读取的线，并把它的内容在$_，a autosplit，使用定义的FS，并将字段放入@F阵列中）

模式：

/ 
(?=   # open a lookahead assertion 
    (.+)\1 # capture group 1 and backreference to the group 1 
)   # close the lookahead 
/g # all occurrences 

这是一个众所周知的模式，用于在字符串中查找所有重叠结果。这个想法是使用这样一个事实，即一个前瞻不消耗字符（一个前瞻只意味着“检查这个子模式是否跟在当前位置”，但它不匹配任何字符）。要获得在前瞻中匹配的字符，您需要的只是一个捕获组。 由于向前看不到任何内容，因此会在每个位置测试该模式（并且不在意这些字符是否已在组1中被捕获）。