☰

只获取线段的不等部分

tag-icon • tag-icon text-processing
只获取线段的不等部分

我有一个文本文件，例如

foo 123
keyword-a some text I dont know in advance text to show
keyword-a some text I dont know in advance some other arbitrary text
keyword-a some text I dont know in advance 99 more to show
keyword-b loremipsum 1
keyword-b loremipsum 2 3 show me

我使用 grep 来获取所有必需的关键字行。

我怎样才能得到仅匹配线的不相等部分？例如对于关键字-a我想得到：

text to show
some other arbitrary text
99 more to show

为了关键字-b我想得到：

1
2 3 show me

提前致谢！

答案1

这里你需要做的是一个相当常见的任务，称为查找最长公共序列（LCS），也称为“最长公共子串问题”。这通常用于打印一组路径名或 URI 的最长公共目录等任务。在你的情况下，你想做相反的事情，输出每行的部分不是最长序列的一部分。

你可以编写自己的算法来用任何你喜欢的语言来查找 LCS，但是 perl 已经有一个实现它的模块，称为算法::差异。该模块不包含在 perl 标准库中，必须与发行版软件包一起安装cpan或从发行版软件包安装（例如，在 Debian 和 Ubuntu 和 Mint 等衍生产品上，您可以使用 来安装它sudo apt-get install libalgorithm-diff-perl。其他发行版可能会或可能不会打包它）

以下代码读取每个输入行，将其拆分为单词数组，并计算每个关键字（每行上的第一个单词）的最长公共序列的大小。

一旦它读取了所有输入行，它就会再次从头开始重新读取输入并打印每个输入行的非公共部分。如果某个关键字只出现过一次（例如foo在您的输入示例中），它只会按原样打印该行（if如果您希望从输出中排除唯一关键字，请删除或注释掉执行此操作的块）。

#!/usr/bin/perl

use strict;
use Algorithm::Diff qw(LCS_length);

my %keywords;
my %LCS;

# get input filename(s)
my @input_files = @ARGV;

# First read in each line and figure out the longest common
# sequence for each keyword
# NOTE: this code assumes that two samples for each keyword
# is enough (i.e. it compares only the first two input lines
# which have the same keyword)
while(<>) {
  chomp;
  my @words = split;
  my $keyword = $words[0];
  
  if (defined $keywords{$keyword}) {
   if (! defined($LCS{$keyword}) ) {
      $LCS{$keyword} = LCS_length(
         \@{ $keywords{$keyword}->[0] },
         \@words
      );
    };
  } else {
    push @{ $keywords{$keyword} }, \@words;
  };
};

# process the same input file(s) again to print the
# non-common portions of each line
push @ARGV, @input_files;

while(<>) {
  chomp;
  my @words = split;
  my $keyword = $words[0];
  
  # if the keyword is unique, just print the line
  if (! defined($LCS{$keyword})) {
    print $_, "\n";
    next;
  };
  
  my $len = $#words;
  my $lcs = $LCS{$keyword} - 1;
  $lcs++ if $lcs == 1;
  print join(" ", $keyword, @words[$lcs..$len]), "\n";
};

示例输出（将上面的脚本保存为not-equal.pl并使用 使其可执行后chmod）：

$ ./not-equal.pl input.txt 
foo 123
keyword-a text to show
keyword-a some other arbitrary text
keyword-a 99 more to show
keyword-b 1
keyword-b 2 3 show me

注意：因为它正在打印由空格连接的单词数组，任何输入行中 2 个或更多空白字符的序列将被转换为单空格字符。如果这不是您想要的，您必须实现自己的 LCS 算法 - 首先在谷歌上搜索“最长公共序列”（或“最长公共子串”）并查看两者https://en.wikipedia.org/wiki/Longest_common_substring_problem和https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Longest_common_substring。

顺便说一句，正如所写，此脚本无法处理标准输入，因为它需要再次重新读取输入文件，并且标准输入不可查找。它是可以编写一个能够处理 stdin 的版本（事实上，我的该脚本的第一个版本就是这样做的），但是您必须在第一个循环期间将每一行读入数组，然后在第二个循环中迭代数组元素。根据输入文件的大小，这可能会消耗大量内存。

这是我的第一个版本，它继续将每个输入行存储到 %keywords 哈希中（而不是仅存储第一个条目）。它的主要问题是散列本质上是无序的，因此输出的顺序将是半随机的（或者，正如我所做的那样，按关键字排序）。这就是我将其更改为仅读取输入文件两次的原因 - 一次通过找出 LCS，然后第二次通过生成输出（即使您的示例输入已经排序......我不知道您的真实数据是否会出现这种情况）。

#!/usr/bin/perl

use strict;
use Algorithm::Diff qw(LCS_length);

my %keywords;
my %LCS;

while(<>) {
  chomp;
  my @words = split;
  my $keyword = $words[0];

  if (defined $keywords{$keyword} && ! defined($LCS{$keyword}) ) {
    $LCS{$keyword} = LCS_length(
      \@{ $keywords{$keyword}->[0] },
      \@words
    );
  };

  push @{ $keywords{$keyword} }, \@words;
};

foreach my $keyword (sort keys %keywords) {
  foreach my $line (keys @{ $keywords{$keyword} } ) {
    my @words = @{ $keywords{$keyword}[$line] };
    if (!defined($LCS{$keyword})) { 
      print join(" ", @words), "\n"; 
       next
    };

    my $len = $#words;
    my $lcs = $LCS{$keyword} - 1;
    $lcs++ if $lcs == 1;
    print join(" ", $keyword, @words[$lcs..$len]), "\n";
  };
};

答案2

cas给了你高级奢华的答案。对于您需要较少防弹的情况，通过一些假设可以更容易：如果（就像在您的示例中）具有相同关键字的所有行共享相同的公共文本，并且没有两个共享额外的公共文本字符（不是foo1、foo21和foo22），一个简单的脚本就可以这样做sed

sed '/keyword-a/H;$!d;x
  s/^\(\n\)\(.*\)\(.*\n\)\2/\2\1\3\2/;:l
  s/^\(.*\)\(\n.*\n\)\1/\1\2/;tl
  s/^[^[:cntrl:]]*\n//'

第一行收集保留空间中的所有关键字行，第二行标识最长的公共开头并将其放置在开头，第三行循环删除所有出现的关键字，第四行删除仍在开头的公共开头。

答案3

由于 cas 让我走上了正轨，只是为了好玩，我将其制作为 php-cli 脚本。将文件读入内存，因此最好不要将其放入最好的 5+GB 日志文件中；-)

要么传递文件作为参数进行处理，要么通过管道传递到脚本中：

$ grep keyword-a myfile.txt | php drop-longest-leading-common-substring.php
DEBUG: [DROPPED]                                     RESULT
DEBUG: [keyword-a some text I dont know in advance ] text to show
DEBUG: [keyword-a some text I dont know in advance ] some other arbitrary text
DEBUG: [keyword-a some text I dont know in advance ] 99 more to show

text to show
some other arbitrary text
99 more to show

脚本包含一些调试输出，删除 fwrite/DEBUG 行以供“生产使用”。

<?php
// proof-of-concept script to remove longest common leading substring from file or piped input
// result output to STDOUT
// (remove all fwrite(STDERR,...) lines for real world usage)

// Get lines from passed file or STDIN    
if( ! empty($argv[1])) {
    if( ! is_readable($argv[1]) || | is_file($argv[1]) ) {
        fwrite(STDERR, 'Error: ' . $argv[1] . ' not readable. Abort.' . PHP_EOL);
        exit(1);
    }
    $lines = file($argv[1], FILE_IGNORE_NEW_LINES);
} else {
    $lines = stream_get_contents(STDIN); // as string
    $lines = preg_replace("/[\r\n]+$/", '', $lines); // drop final CR|LF as it would add an empty array element with preg_split()
    $lines = preg_split('/(\r\n|\r|\n)/', $lines); // handle CRs and|or LFs
}

if(empty($lines)) {
    fwrite(STDERR, 'Nothing to process' . PHP_EOL);
    exit;
}

// no way the first non-common match is beyond shortest string's end
$strlen_shortest=PHP_INT_MAX;
foreach($lines as $line) {
    $strlen_shortest=min($strlen_shortest, strlen($line));
}
fwrite(STDERR, 'DEBUG: shortest string in input: ' . $strlen_shortest . ' characters' . PHP_EOL);

$last_common_substring_at = $strlen_shortest;

// read n chars from all lines until substring differs
for($c = 1; $c <= $strlen_shortest; $c++) {
    fwrite(STDERR, 'DEBUG: ' . substr($lines[0],0,$c) . ' [' .  substr($lines[0],$c) . ']' . PHP_EOL);
    $line_parts=[];
    $line_part_last=false;
    foreach($lines as $line_key=>$line) {
        if( false !== $line_part_last) {
            if($line_part_last != substr($line,0,$c)) {
                fwrite(STDERR, 'DEBUG: ' . substr($line,0,$c)  . ' [' .  substr($line,$c) . ']' . PHP_EOL);
                fwrite(STDERR, 'DEBUG: ' . str_repeat(' ', $c-1) . '^ first difference at char ' . $c . PHP_EOL);
                $last_common_substring_at = $c-1;
                break 2;
            }
        } else {
            $line_part_last = substr($line,0,$c);
        }
    }
}

fwrite(STDERR, 'DEBUG: ' . PHP_EOL);
fwrite(STDERR, sprintf('DEBUG: %-' . ($last_common_substring_at +2) . 's %s' . PHP_EOL, '[DROPPED]', 'RESULT') );
foreach($lines as $line_key=>$line) {
    fwrite(STDERR, 'DEBUG: [' . substr($line,0,$last_common_substring_at) . ']');
    fwrite(STDERR, ' ');
    fwrite(STDERR, substr($line,$last_common_substring_at) . PHP_EOL);
}
    fwrite(STDERR, PHP_EOL);

// final result:
foreach($lines as $line_key=>$line) {
    echo substr($line,$last_common_substring_at) . PHP_EOL;
}

相关内容