regex - 使用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 正则表达式没有反向引用，反向引用的使用大大简化了方法。

对于多个最长单词的情况，我在示例输入文件中添加了一行:

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 - 参数将 stdin 作为文件读取:

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

限制

虽然这可以处理评论中提到的 bbwelcomewelcome 情况，但它会遇到重叠模式，例如 welcomewelcomewelcome，它只能找到 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 命令，或者不跟踪多个longest matches with awk in the second solution), 获得的时间仅在几秒的范围内。

便携性说明

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