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
$

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

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 行。此外，内存使用与范围大小成正比，而不是与文件大小成正比，所以我们以另一种方式获胜。