sub repeated_substring {
  my $size     = length $_[0];    # total size of the dataset
  my $maxsize  = int ($size / 2); # maximum possible length of the match
  my $f_index  = 0;               # index of the current best match
  my $f_offset = 0;               # offset of the current best match

OUTER:
  for (my $index=0; $index < $size; $index++) {

    # The big optimizer (explained below)
    if ($f_offset > 20) {
      for (my $t_index = $index + $f_offset - 15; $t_index >= $index; $t_index =
$t_index - 10) {
        if (index($_[0], substr($_[0], $t_index, $index+$f_offset-$t_index),
$index+$f_offset) == -1) {
          $index = $t_index;
          next OUTER;
        }
      }
    }

    # The brute force algorithm
    # Keep looking for a match that is one bigger than the last match and stop once
    # we don't find a match
    for (my $offset=$f_offset+1; $offset <= $maxsize && $index + $offset <=
$size; $offset++) {
      if (index($_[0], substr($_[0], $index, $offset), $index+$offset) >= 0) {
        $f_index  = $index;
        $f_offset = $offset;
      } else {
        last;
      }
    }
  }
  return substr($_[0], $f_index, $f_offset);
}


__END__


My basic algorithm seems to be similar to several others, but I found a way to
make it go quite fast.

Some simple techniques I used to speed things up:
- access the string inside the function as $_[0] (I never change it, so why make
a local copy)
- don't use regexps (substr and index suffice)
- when a match is found, store the index and offset instead of the found string.
 At the end we can pull out the string and return it.
- only accept strings that are bigger than the current biggest match
- Never look for a match that is more than half the length of the entrire string

But these are only minor tweaks.  The big optimization came from an observation
I made while watching my algorithm search.  I added copious amounts of deb
ug statements and noticed that my algorithm did a lot of the following:

880, match(45): [e who shall not have attained to the Age of t]
880, 46 M45:    [e who shall not have attained to the Age of tw]
881, 46 M45:    [ who shall not have attained to the Age of twe]
882, 46 M45:    [who shall not have attained to the Age of twen]
883, 46 M45:    [ho shall not have attained to the Age of twent]
884, 46 M45:    [o shall not have attained to the Age of twenty]
885, 46 M45:    [ shall not have attained to the Age of twenty ]
886, 46 M45:    [shall not have attained to the Age of twenty f]
887, 46 M45:    [hall not have attained to the Age of twenty fi]
888, 46 M45:    [all not have attained to the Age of twenty fiv]
889, 46 M45:    [ll not have attained to the Age of twenty five]
890, 46 M45:    [l not have attained to the Age of twenty five ]

This is a snippet of debug output of the Constitution file.  We have just found
a match of 45 characters long at position 880 and are now looking for one
that is 46 characters long starting again at position 880.  Each time it shifts
one character over and checks the file for the next string.  What I notice
d is that in all these 11 tests, it is searching for basically the same string
with only a minor change at the front and back.

Now if I am lucky, I can prove that all 11 of these tests will fail of I can
prove that a smaller substring like the string [ined to the Age of tw] does n
ot appear multiple times in the rest of the document.  Because if the short
string [ined to the Age of t] doesn't appear multiple times, then we can be su
re  that a longer string containing that snippet will also not appear twice in
the document.  So by doing one test, we can throw away all of the other tes
ts...

That is a simplified explaination of the optimization my code performs.  This
techniques will only work once a significantly large match has been found.
In my code I have chosen a minimum match of 20 characters before it kicks in. 
When it kicks in, it checks for small substrings in 15 character blocks, st
arting at the end of the current test string.  So if we used the above example
again, the code would do the following:

880, match(45): [e who shall not have attained to the Age of t]
880, 46 M45:    [e who shall not have attained to the Age of tw]
Check for this small substring first            ^^^^^^^^^^^^^^^
If that small substring is not found in the rest of the document, then we can
skip to position 911 and we have saved at least 30 extra tests

911, 46 M45: [o the Age of twenty five Years, and been seven]
912, 46 M45: [ the Age of twenty five Years, and been seven ]


If we did find the string [o the Age of tw], then we can't skip quite as far
ahead so we check the last 30 characters instead and repeat

880, match(45): [e who shall not have attained to the Age of t]
880, 46 M45:    [e who shall not have attained to the Age of tw]
Check last 30 chars              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
If we didn't find this string, then we can still skip ahead just not as far (we
still saved 15 tests or so)

896, 46 M45: [have attained to the Age of twenty five Years,]
897, 46 M45: [ave attained to the Age of twenty five Years, ]


If again we found the string, then the optimization failed for this section and
we would go into the normal search routine, and we would check the entire
string for a match.

So you can see that this optimization has the potential to greatly reduce the
number of string tests that need to be done.  Also, the longer a match that is
found, the quicker it will skip ahead.  There is a lot of room to play with the
numbers here.  I picked a string length of 20 before it kicks in, and a minimum
substring size of 15 to start with.  It might be insteresting to do some
analysis to try to optimize these two numbers in some way.  I didn't have enough
time to do the experimenting required though.

I appologize for the length of this post, but I wanted to explain how I got my
speed improvements, since it is probably not immediately obvious from the c
ode.  With this code I am able to parse the Tristram file in 2 minutes 17
seconds on my 366Mhz laptop.

If anyone finds a test case that fails with my code, please let me know.  I have
tried to come up with edge cases, but I probably missed a couple possibil
ities.


Cheers,

Cees
