I have a log containing an execution trace where there is infinite recursion eventually terminating when the stack is too deep. There are enough lines and valid included recursion within the larger block of lines that it is difficult to identify the largest block that is recurring. There is nothing unique that would require me to filter out part of the line to make this determination.What is a good one-liner/script (in POSIX/OS X, but best if it can work in Linux and OS X) that, given a filename/pathname, could output only the largest set of lines that recur sequentially more than once?Clarification: in my case the log file is 432003 lines and 80M:$ wc -l long_log.txt 432003 long_log.txt$ du -sm long_log.txt80  long_log.txtTo create a similar input file, try this, thanks to the post here for the method to create a file containing random words.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.txtruby -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.txtruby -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.txtruby -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.txtcat head.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt tail.txt > log.txtcat recurrence1.txt recurrence1.txt recurrence2.txt > expected.txtTo result in:$ wc -l log.txt 400050 log.txt$ du -sm log.txt89  log.txtThen you should be able to do:$ recurrence log.txt > actual.txt$ diff actual.txt expected.txt$It is also ok if it recognizes the other same-length block instead, i.e.$ cat recurrence1.txt recurrence2.txt recurrence1.txt recurrence1.txt recurrence2.txt recurrence1.txt > expected2.txt$ diff actual.txt expected2.txt$Would really like it to find the expected result in < 10 sec in OS X/Linux w/ a 2.6GHz quad-core Intel Core i7 and 16 GB memory.
OS X/Linux one-liner/script to find the largest recurring group of lines in a text file?
linux;command line;text processing;posix
Solution in the TXR language.@(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))))The program consists almost entirely of TXR's embedded Lisp dialect. The approach here is to keep each line from the file in a hash table. At any position in the file, we can ask the hash table, at what positions have we seen this exact line before, if any?. If so, we can compare the file starting from that those position to the lines starting at the current position. If the match extends all the way from the previous position the current position, it means that we have a consecutive match: all the N lines from the previous position to just before the current line match the N lines starting at the current line. All we have to then is then find among all these candidate places the one that yields the longest match. (If there are ties, only the first one is reported).Hey look, there is a repeating two-line sequence in an Xorg log file:$ txr longseq.txr  /var/log/Xorg.0.log2 line(s) starting at line 168What's at line 168? These four lines:[    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 VBoxDynamicModex0.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 VBoxDynamicModex0.0   56.94  1280 1282 1284 1286  732 734 736 738 (44.3 kHz)On the other hand, the password file is all unique:$ txr longseq.txr  /etc/passwdno repeated blocksThe additional second argument can be used to speed up the program. If we know that the longest repeating sequence is, say, no more than 50 lines, then we can specify this. The program will then not look back farther than 50 lines. Furthermore, the memory use is proportional to the range size, not to the file size, so we win in another way. 