Tk Library Source Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91

[comment {-*- tcl -*- doctools manpage}] [comment {$Id: $}] [manpage_begin list n 1.2.2] [copyright {2003 by Kevin B. Kenny. All rights reserved}] [moddesc {Tcl Data Structures}] [titledesc {Procedures for manipulating lists}] [require Tcl 8.0] [require struct [opt 1.2.1]] [description] [para] The [cmd ::struct::list] namespace contains several useful commands for processing Tcl lists. Generally speaking, they implement algorithms more complex or specialized than the ones provided by Tcl itself. [section COMMANDS] [list_begin definitions] [call [cmd ::struct::list::longestCommonSubsequence] \ [arg {sequence1 sequence2 ?maxOccurs?}]] Returns the longest common subsequence of [arg sequence1] and [arg sequence2]. If the [arg maxOccurs] parameter is provided, the common subsequence is restricted to elements that occur no more than [arg maxOccurs] times in [arg sequence2]. [nl] The return value is a list of two lists of equal length. The first sublist is of indices into [arg sequence1], and the second sublist is of indices into [arg sequence2]. Each corresponding pair of indices corresponds to equal elements in the sequences; the sequence returned is the longest possible. [call [cmd ::struct::list::longestCommonSubsequence2] \ [arg {sequence1 sequence2 ?maxOccurs?}]] Returns an approximation to the longest common sequence of [arg sequence1] and [arg sequence2]. If the [arg maxOccurs] parameter is omitted, the subsequence computed is exactly the longest common subsequence; otherwise, the longest common subsequence is approximated by first determining the longest common sequence of only those elements that occur no more than [arg maxOccurs] times in [arg sequence2], and then using that result to align the two lists, determining the longest common subsequences of the sublists between the two elements. [nl] As with [cmd ::struct::list::longestCommonSubsequence], The return value is a list of two lists of equal length. The first sublist is of indices into [arg sequence1], and the second sublist is of indices into [arg sequence2]. Each corresponding pair of indices corresponds to equal elements in the sequences. The sequence approximates the longest common subsequence. [list_end] [section {LONGEST COMMON SUBSEQUENCE AND FILE COMPARISON}] [para] The [cmd ::struct::list::longestCommonSubsequence] command forms the core of a flexible system for doing differential comparisons of files, similar to the capability offered by the Unix command [syscmd diff]. While this procedure is quite rapid for many tasks of file comparison, its performance degrades severely if [arg sequence2] contains many equal elements (as, for instance, when using this procedure to compare two files, a quarter of whose lines are blank. This drawback is intrinsic to the algorithm used (see the Reference for details). [para] One approach to dealing with the performance problem that is sometimes effective in practice is arbitrarily to exclude elements that appear more than a certain number of times. This number is provided as the [arg maxOccurs] parameter. If frequent lines are excluded in this manner, they will not appear in the common subsequence that is computed; the result will be the longest common subsequence of infrequent elements. The procedure [cmd ::struct::list::longestCommonSubsequence2] implements this heuristic. It functions as a wrapper around [cmd ::struct::list::longestCommonSubsequence]; it computes the longest common subsequence of infrequent elements, and then subdivides the subsequences that lie between the matches to approximate the true longest common subsequence. [section REFERENCES] J. W. Hunt and M. D. McIlroy, "An algorithm for differential file comparison," Comp. Sci. Tech. Rep. #41, Bell Telephone Laboratories (1976). Available on the Web at the second author's personal site: [uri http://www.cs.dartmouth.edu/~doug/] [keywords list diff differential comparison common subsequence] [manpage_end]