OS X / Linux one-liner / script para encontrar o maior grupo recorrente de linhas em um arquivo de texto?

Question

Eu tenho um log contendo um rastreamento de execução, onde há recursão infinita, eventualmente, terminando quando a pilha é muito profunda. Existem linhas suficientes e recursão incluída válida dentro do bloco maior de linhas que é difícil identificar o maior bloco que é recorrente. Não há nada de exclusivo que me obrigue a filtrar parte da linha para fazer essa determinação.

O que é um bom liner / script (no POSIX / OS X, mas é melhor se funcionar no Linux e no OS X) que, dado um nome de arquivo / nome de caminho, pode produzir apenas o maior conjunto de linhas que se repetem sequencialmente mais de uma vez?

Clarificação: no meu caso, o arquivo de log é 432003 linhas e 80M:

$ wc -l long_log.txt 
432003 long_log.txt
$ du -sm long_log.txt
80  long_log.txt

Para criar um arquivo de entrada similar, tente isso, graças ao post aqui para o método criar um arquivo contendo palavras aleatórias.

ruby -e 'a=STDIN.readlines;200000.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > head.txt
ruby -e 'a=STDIN.readlines;2.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > recurrence1.txt
ruby -e 'a=STDIN.readlines;20.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > recurrence2.txt
ruby -e 'a=STDIN.readlines;200000.times do;b=[];22.times do; b << a[rand(a.size)].chomp end; puts b.join(" "); end' < /usr/share/dict/words > tail.txt
cat head.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt tail.txt > log.txt
cat recurrence1.txt recurrence1.txt recurrence2.txt > expected.txt

Para resultar em:

$ wc -l log.txt 
400050 log.txt
$ du -sm log.txt
89  log.txt

Então você deve ser capaz de fazer:

$ recurrence log.txt > actual.txt
$ diff actual.txt expected.txt
$

Também está ok se reconhecer o outro bloco de comprimento igual, ou seja,

$ cat recurrence1.txt recurrence2.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt > expected2.txt
$ diff actual.txt expected2.txt
$

Gostaríamos realmente de encontrar o resultado esperado em < 10 seg. No OS X / Linux com um processador Intel Core i7 quad-core de 2,6 GHz e 16 GB de memória.

    

Answer 1

Solução na linguagem TXR .

@(next :args)
@(bind rangelim nil)
@(block)
@  (cases)
@filename
@    (maybe)
@rlim
@      (set rangelim @(int-str rlim))
@    (end)
@    (eof)
@  (or)
@    (output)
arguments are: filename [ range-limit ]
@    (end)
@    (fail)
@  (end)
@(end)
@(do
   (defun prefix-match (list0 list1)
     (let ((c 0))
       (each ((l0 list0)
              (l1 list1))
         (if (not (equal l0 l1))
           (return c))
         (inc c))
       c))

   (defun line-stream (s)
     (let (li) (gen (set li (get-line s)) li)))

   (let* ((s (line-stream (open-file filename "r")))
          (lim rangelim)
          (s* (if lim s nil))
          (h (hash :equal-based))
          (max-len 0)
          (max-line nil))
     (for ((ln 1)) (s) ((set s (rest s)) (inc ln))
       (let ((li (first s)))
         (let ((po (gethash h li))) ;; prior occurences
           (each ((line [mapcar car po])
                  (pos [mapcar cdr po]))
             (let ((ml (prefix-match pos s)))
               (cond ((and 
                        (= ml (- ln line))
                        (> ml max-len))
                      (set max-len ml)
                      (set max-line line))))))
         (pushhash h li (cons ln s))
         (if (and lim (> ln lim))
           (let* ((oldli (first s*))
                  (po (gethash h oldli))
                  (po* (remove-if (op eq s* (cdr @1)) po)))
             (if po*
               (sethash h oldli po*)
               (remhash h oldli))
             (set s* (cdr s*))))))
     (if max-line
       (format t "~a line(s) starting at line ~a\n" max-len max-line)
       (format t "no repeated blocks\n"))))

O programa consiste quase inteiramente no dialeto incorporado do TXT. A abordagem aqui é manter cada linha do arquivo em uma tabela de hash. Em qualquer posição no arquivo, podemos perguntar à tabela de hash "em que posições já vimos essa linha exata antes, se houver alguma?". Se assim for, podemos comparar o arquivo a partir daquela posição para as linhas começando na posição atual. Se a partida se estender desde a posição anterior a posição atual, significa que temos uma partida consecutiva: todas as N linhas da posição anterior até logo antes da linha atual correspondem às N linhas que começam na linha atual. Tudo o que temos então é encontrar entre todos esses lugares candidatos aquele que produz a correspondência mais longa. (Se houver laços, apenas o primeiro é relatado).

Ei, olhe, há uma sequência repetida de duas linhas em um arquivo de log do Xorg:

$ txr longseq.txr  /var/log/Xorg.0.log
2 line(s) starting at line 168

O que está na linha 168? Estas quatro linhas:

[    19.286] (**) VBoxVideo(0):  Built-in mode "VBoxDynamicMode": 56.9 MHz (scaled from 0.0 MHz), 44.3 kHz, 60.0 Hz
[    19.286] (II) VBoxVideo(0): Modeline "VBoxDynamicMode"x0.0   56.94  1280 1282 1284 1286  732 734 736 738 (44.3 kHz)
[    19.286] (**) VBoxVideo(0):  Built-in mode "VBoxDynamicMode": 56.9 MHz (scaled from 0.0 MHz), 44.3 kHz, 60.0 Hz
[    19.286] (II) VBoxVideo(0): Modeline "VBoxDynamicMode"x0.0   56.94  1280 1282 1284 1286  732 734 736 738 (44.3 kHz)

Por outro lado, o arquivo de senha é único:

$ txr longseq.txr  /etc/passwd
no repeated blocks

O segundo argumento adicional pode ser usado para acelerar o programa. Se sabemos que a seqüência de repetição mais longa é, digamos, não mais de 50 linhas, então podemos especificar isso. O programa não irá olhar para mais de 50 linhas. Além disso, o uso da memória é proporcional ao tamanho do intervalo, não ao tamanho do arquivo, então ganhamos de outra maneira.

    

Answer 2

Acontece que a maneira mais rápida e simples de encontrar grandes blocos de duplicação em um log grande para mim, especialmente quando há muita repetição, é:

sort long_log.txt | uniq -c | sort -k1n

(Reunidos de respostas aqui e aqui .

Isso levou 54 segundos para long_log.txt, que foi o que teve mais repetição, o que parece ser um problema para um script que faria exatamente o que eu estava pedindo, e 47 segundos para o gerado aleatoriamente, log.txt .

As linhas estão fora de ordem, e se houver recursão dentro da recursão, pode agrupar essas linhas separadamente (já que elas podem ter uma contagem ainda maior), mas talvez você possa usar os dados desse método e voltar no log para encontrar e extrair a (s) parte (s) relevante (s).

Este comando pode ser colocado em seu .bashrc / .bash_profile como uma função:

recurrence() {
  sort "$1" | uniq -c | sort -k1n
}

Para que possa ser chamado como:

recurrence long_log.txt

    

Answer 3

Aqui está uma solução no bash para você. Eu realmente tenho um script para isso ; mas aqui é o único forro:

find $PWD -regextype posix-extended -iregex '.*\.(php|pl)$' -type f | xargs wc -L 2> /dev/null | grep -v 'total' | sort -nrk1 | head -n 30 | awk 'BEGIN { printf "\n%-15s%s\n", "Largest Line", "File"; } { printf "%-15s%s\n", $1, $2; }'

Eu uso para encontrar arquivos hackeados em sites invadidos; então você pode remover o -regex .