OS X/Linux 单行/脚本查找文本文件中最大的重复行组？

Question

我有一个包含执行跟踪的日志，其中存在无限递归，最终在堆栈太深时终止。在较大的行块内有足够的行和有效的包含递归，因此很难识别重复出现的最大块。没有什么独特之处需要我过滤掉部分行来做出这个决定。

什么是一个好的单行/脚本（在 POSIX/OS X 中，但最好它可以在 Linux 和 OS X 中工作），在给定文件名/路径名的情况下，只能输出连续重复多次的最大行集？

澄清：在我的例子中，日志文件有 432003 行和 80M：

$ wc -l long_log.txt 
432003 long_log.txt
$ du -sm long_log.txt
80  long_log.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 > 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

以导致：

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

那么你应该能够做到：

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

如果它识别另一个相同长度的块也可以，即

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

我真的很希望它能在 10 秒内找到预期的结果，在 OS X/Linux 中使用 2.6GHz 四核 Intel Core i7 和 16 GB 内存。

Answer 1

解决方案在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"))))

该程序几乎完全由 TXR 的嵌入式 Lisp 方言组成。这里的方法是将文件中的每一行保存在哈希表中。在文件中的任何位置，我们都可以询问哈希表，“我们之前在哪些位置看到过这一行（如果有的话）？”。如果是这样，我们可以将从该位置开始的文件与从当前位置开始的行进行比较。如果匹配从前一个位置一直延伸到当前位置，则意味着我们有一个连续的匹配：从前一个位置到当前行之前的所有 N 行都与从当前行开始的 N 行匹配。我们所要做的就是在所有这些候选位置中找到产生最长匹配的位置。 （如果有联系，则仅报告第一个）。

嘿，看，Xorg 日志文件中有一个重复的两行序列：

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

168号线有什么？这四行：

[    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)

另一方面，密码文件都是唯一的：

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

附加的第二个参数可用于加速程序。如果我们知道最长的重复序列不超过 50 行，那么我们可以指定它。然后程序不会回溯超过 50 行。此外，内存使用与范围大小成正比，而不是与文件大小成正比，所以我们以另一种方式获胜。

Answer 2

事实证明，对我来说，在大日志中找到大重复块的最快、最简单的方法，特别是当存在大量重复时，是：

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

（根据答案拼凑而成这里和这里.)

long_log.txt 花了 54 秒，这是重复次数较多的一个，这对于完全按照我的要求执行的脚本来说似乎是一个问题，而随机生成的 log.txt 则花了 47 秒。

这些行是无序的，如果递归中存在递归，它可能会将这些行单独分组（因为它们可能具有更大的计数），但也许您可以使用此方法中的数据，然后返回到日志中查找并提取相关部分。

该命令可以作为函数放入.bashrc/中：.bash_profile

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

这样它就可以被称为：

recurrence long_log.txt

Answer 3

这是 bash 为您提供的解决方案。其实我有一个脚本;但这是唯一的一条：

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

我用它来查找被黑网站上被黑的文件；这样你就可以删除-regex.