☰

선분의 동일하지 않은 부분만 가져오기

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 알고리즘을 구현해야 합니다. 먼저 Google에서 "가장 긴 공통 시퀀스"(또는 "가장 긴 공통 부분 문자열")를 검색하고 두 가지를 모두 살펴봐야 합니다.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는 하이엔드 럭셔리에 대한 답을 드립니다. 덜 방탄해야 하는 경우 몇 가지 가정을 하면 더 쉽습니다. 예에서와 같이 동일한 키워드가 있는 모든 줄이 동일한 공통 텍스트를 공유하고 두 줄이 추가 공통 텍스트 문자( Not 및 foo1) 를 공유하지 않는 경우, 간단한 스크립트로 이 작업을 수행할 수 있습니다.foo21foo22sed

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 스크립트로 만들었습니다. 파일은 메모리로 읽혀지므로 5GB 이상의 로그 파일에 넣지 않는 것이 좋습니다 ;-)

처리를 위해 파일을 매개변수로 전달하거나 스크립트에 파이프하십시오.

$ 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;
}

관련 정보