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

Question

例如,假设有一个domains.csv使用以下内容调用的文件:

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

我正在尝试使用linux awk正则表达式来查找包含最长重复^1个单词的行,所以在这种情况下,它将返回该行

5,letswelcomewelcomeyou.org

我怎么做？

¹含义"立即重复",即abcabc,但不是abcXabc.

Answer 1

纯awk实现会相当冗长,因为awk regex没有反向引用,其使用简化了方法.

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

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注释中提到的情况,但它会在重叠模式上跳闸,例如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]
}

标杆

我在评论中提到的前100万个域文件中计算了两个解决方案:

• 第一个解决方案(有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的解决方案由卡西米尔等伊波利特:

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

我们从中学到了什么:下次要求Perl解决方案;)

有趣的是,如果我们知道只有一个最长的匹配并相应地简化命令(只是head -1代替第一个解决方案的第二个awk命令,或者没有跟踪第二个解决方案中与awk的多个最长匹配),获得的时间仅在几秒钟的范围内.

便携性评论

显然,BSD grep不能grep -f -从stdin读取.在这种情况下,管道的输出直到必须重定向到临时文件,然后使用此临时文件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读取一行并将其内容放入$_,aautosplit,使用定义的FS,并将字段放入@F数组中)

模式:

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

这是一个众所周知的模式,可以在字符串中查找所有重叠结果.我们的想法是使用前瞻不消耗字符的事实(前瞻只意味着"检查此子模式是否跟在当前位置",但它与任何字符都不匹配).要获得前瞻中匹配的字符,您需要的只是一个捕获组.由于前瞻不匹配,因此在每个位置测试模式(并且不关心字符是否已经在组1中捕获过).