Editing Longest common subsequence (section)

=== Reduce strings to hashes ===
A [[hash function]] or [[checksum]] can be used to reduce the size of the strings in the sequences.  That is, for source code where the average line is 60 or more characters long, the hash or checksum for that line might be only 8 to 40 characters long.  Additionally, the randomized nature of hashes and checksums would guarantee that comparisons would short-circuit faster, as lines of source code will rarely be changed at the beginning.

There are three primary drawbacks to this optimization.  First, an amount of time needs to be spent beforehand to precompute the hashes for the two sequences.  Second, additional memory needs to be allocated for the new hashed sequences.  However, in comparison to the naive algorithm used here, both of these drawbacks are relatively minimal.

The third drawback is that of [[hash collision|collisions]].  Since the checksum or hash is not guaranteed to be unique, there is a small chance that two different items could be reduced to the same hash.  This is unlikely in source code, but it is possible.  A cryptographic hash would therefore be far better suited for this optimization, as its entropy is going to be significantly greater than that of a simple checksum.  However, the benefits may not be worth the setup and computational requirements of a cryptographic hash for small sequence lengths.