Provided by: similarity-tester_3.0.2-1_amd64 
NAME
sim - find similarities in C, Java, Pascal, Modula-2, Lisp, Miranda, 8086 assembler code
or in text files
SYNOPSIS
sim_c [ -[adefFiMnOpPRsSTuv] -r N -t N -w N -o F ] file ... [ [ / | ] file ... ]
sim_text ...
sim_c++ ...
sim_java ...
sim_pasc ...
sim_m2 ...
sim_lisp ...
sim_mira ...
sim_8086 ...
DESCRIPTION
Sim_c reads the C files file ... and looks for segments of text that are similar; two
segments of program text are similar if they only differ in layout, comment, identifiers,
and the contents of numbers, strings and characters. If any runs of sufficient length are
found, they are reported on standard output; the number of significant tokens in the run
is given between square brackets.
Sim_c++ does the same for C++, sim_java for Java, sim_pasc for Pascal, sim_m2 for
Modula-2, sim_mira for Miranda, sim_lisp for Lisp, and sim_8086 for 8086 assembler code.
Sim_text works on arbitrary text and it is occasionally useful on shell scripts.
The program can be used for finding copied pieces of code in purportedly unrelated
programs (with -s or -S), or for finding accidentally duplicated code in larger projects
(with -f or -F).
If a separator / or | is present in the list of input files, the files are divided into a
group of "new" files (before the / or |) and a group of "old" files; if there is no / or
|, all files are "new". Old files are never compared to other files. See also the
description of the -s and -S options below.
Since the similarity tester needs file names to pinpoint the similarities, it cannot read
from standard input.
The similarity tester takes ASCII or UTF-8 text as input, and produces a sorted list of
runs in text form (default or with the -d or -n options) or in percentage form (with the
-p option). Input in other formats, e.g. .pdf or .doc needs to be converted to ASCII or
UTF-8 by preprocessing. Aggregated similarity results can be obtained by doing
postprocessing on one of the forms of output.
There are the following options:
-a All new files are compared to all files. See the section `Calculating Percentages'
below.
-d The output is in a diff(1)-like format instead of the default 2-column format.
Recommended for text in languages with non-Latin alphabets.
-e Each file is compared to each file in isolation. This will find all similarities
between all texts involved, regardless of repetitive text, but may be slow for
large numbers of files. See also `Calculating Percentages' below.
-f Runs are restricted to segments with balancing parentheses, to isolate potential
routine bodies (not in sim_text).
-F The names of routines in calls are required to match exactly (not in sim_text).
-i The names of the files to be compared are read from standard input, including a
possible separator / or |; the file names must be one to a line. This option
allows a very large number of file names to be specified; it differs from the @
facility provided by some compilers in that it handles file names only, and does
not recognize option arguments.
-M Memory usage information is displayed on standard error output.
-n Similarities found are summarized by file name, position and size, rather than
displayed in full.
-o F The output is written to the file named F.
-O The option settings used are shown at the beginning of the output.
-p The output is given in similarity percentages; see `Calculating Percentages' below;
implies -s.
-P When reporting percentages, only the main contributor for each file is shown.
-r N The minimum run length is set to N units; the default is 24 tokens, except in
sim_text, where it is 8 words.
-R Directories in the input list are entered recursively, and all files they contain
are involved in the comparison.
-s The contents of a file are not compared to itself (-s for "not self").
-S The contents of the new files are compared to the old files only - not between
themselves.
-t N In combination with the -p option, sets the threshold (in percents) below which
similarities will not be reported; the default is 1, except in sim_text, where it
is 20.
-T Suppresses the printing of information about the input files.
-u The output is not buffered and not sorted (only when reporting percentages).
-v Prints the version number and compilation date on standard output, then stops.
-w N The page width used is set to N columns; the default is 80.
-- (A secret option, which prints the input as the similarity checker sees it, and
then stops.)
The -p option results in lines of the form
F consists for x % of G material
meaning that x % of F's text can also be found in G. Note that this relation is not
symmetric; it is quite possible for one file to consist for 100 % of text from another
file, while the other file consists for only 1 % of text of the first file, if their
lengths differ enough. The -P (capital P) option shows the main contributor for each file
only. This simplifies the identification of a set of files A[1] ... A[n], where the
concatenation of these files is also present. A threshold can be set using the -t option.
Note that the granularity of the recognized text is still governed by the -r option or its
default.
The -r option controls the number of "units" that constitute a run. For the programs that
compare programming language code, a unit is a lexical token in the pertinent language;
comment and standard preamble material (file inclusion, etc.) is ignored and all strings
are considered equal. For sim_text a unit is a "word" which is defined as any sequence of
one or more letters, digits, or characters over 127 (177 octal), to accommodate full
Unicode (UTF-8).
The programs can handle Unicode (UTF-16) file names under Windows.
Sim_text accepts s p a c e d t e x t as normal text.
Once sim has read, stored and preprocessed the input, it will no longer run out of memory.
If memory is short it will change automatically to unbuffered, unsorted output (while
issuing a warning message).
HOW SIMILARITY IS RECOGNIZED
Since computers cannot test for similarity, only for equality, all units in the input
files are replaced by 16-bit tokens, such that all units that are regarded as similar are
reduced to the same token. For example in sim_c all identifiers are replaced by the token
IDF and all strings are replaced by the token STR. The secret option -- can be used to see
the resulting token sequence.
In sim_text each word is reduced to a 16-bit token using a hash function. There is a
chance of 1 : 65536 that two different words get the same token value, but because
recognized runs of tokens are usually several tokens long, the chances for accidental
similarities are very low.
The sequence of tokens obtained this way is then processed as follows.
The default operation cycle of sim starts at the beginning of the token sequence of the
first input file or at a position $X$ in file $F$ at which the previous cycle has left
off. Sim then finds the longest segment $S$ such that 1) $S$ is equal to the segment
starting at $X$; 2) $S$ is situated somewhere between position $X$ in $F$ and the end of
all files; 3) $S$ does not overlap with the segment starting at $X$. If the segment is at
least of minimum run size, it is recorded, and the cycle starts again just after the
segment at $X$; otherwise it starts again at $X+1$ .
So if the token sequence at $X$ reads abcabcadefabdabcz, the cycle finds $S$ to be the abc
just before the end; abca at $X+3$ would be longer but overlaps with the abca at $X+0$ .
The cycle then starts at $X+3$, and will find another match with the abc near the end.
Finally the ab after the f will be matched with the ab just before the cz. So the
following matches are found:
$ X[0:2] = X[13:15] =$ abc
$ X[3:5] = X[13:15] =$ abc
$ X[9:10] = X[13:14] =$ ab
This way best matches for the text in a file are found in material to the right of it,
until the end of all files. The results are asymmetric: given files F1, F2, F3, F4, no
matches for F3 are reported from F1 or F2, for example. As explained below under
"Limitations", this avoids duplicate reports of similarity and helps to keep sim fast.
WHAT IS COMPARED TO WHAT
The area that is searched by sim's cycle is called the range. The default range, which as
we have seen above runs from the file under observation to the end of all files, is
excellent for finding similarities in program files, and, when doing percentages, for
getting an impression of which files are related to which files, but sometimes more
control is needed. The following modifications to the range are available:
The -a option includes all text in the range by not stopping the search at the end of the
files but rather looping back to the beginning of the files and continuing to the point
where the search started. Now matches are also found in files before the present one and
the results are symmetric: given files F1, F2, F3, F4, matches for F3 will also be
reported from F1 or F2, if present. But matches may be reported twice, once for file Fa
versus file Fb, and once for file Fb versus file Fa. The -a option allows a more accurate
determination of similarity percentages.
The -a option is the only way to obtain symmetrical results, with information about both
F1 vs. F2 and F2 vs. F1.
The -S option removes the new files from the range, so files are only compared to the old
files.
The -s option removes the file itself from the range, so a file will not be compared to
itself. This is the default when reporting percentages.
In normal operation the whole range is searched as one unit. The -e option divides up the
range into the separate files, and causes sim to compare a file to each of the other files
separately. This produces the most detailed information when reporting text similarities,
and the best possible results when reporting similarity percentages, but can be quite
slow.
A Tabular Representation
Input files are divided into two groups, new and old. In the absence of control options
sim compares the files thus (for 4 new files and 6 old ones):
n e w / o l d <- second file
1 2 3 4 / 5 6 7 8 9 10
|------------/------------
n 1 | c c c c / c c c c c c
e 2 | c c c / c c c c c c
w 3 | c c / c c c c c c
4 | c / c c c c c c
first / / / / / / / / / / / / /
file -> 5 | /
o 6 | /
l 7 | /
d 8 | /
9 | /
10 | /
where a c indicates that the first file is compared to the second file, and the /
represents the demarcation between new and old files. The comparison range of the first
files is clearly visible.
Using the -a option extends this to
n e w / o l d <- second file
1 2 3 4 / 5 6 7 8 9 10
|------------/------------
n 1 | c c c c / c c c c c c
e 2 | c c c c / c c c c c c
w 3 | c c c c / c c c c c c
4 | c c c c / c c c c c c
first / / / / / / / / / / / / /
file -> 5 | /
o 6 | /
l 7 | /
d 8 | /
9 | /
10 | /
Using the -S option instead reduces this to
n e w / o l d <- second file
1 2 3 4 / 5 6 7 8 9 10
|------------/------------
n 1 | / c c c c c c
e 2 | / c c c c c c
w 3 | / c c c c c c
4 | / c c c c c c
first / / / / / / / / / / / / /
file -> 5 | /
o 6 | /
l 7 | /
d 8 | /
9 | /
10 | /
Finally, using the -s option changes the default ranges to
n e w / o l d <- second file
1 2 3 4 / 5 6 7 8 9 10
|------------/------------
n 1 | c c c / c c c c c c
e 2 | c c / c c c c c c
w 3 | c / c c c c c c
4 | / c c c c c c
first / / / / / / / / / / / / /
file -> 5 | /
o 6 | /
l 7 | /
d 8 | /
9 | /
10 | /
and the -a-extended ranges to
n e w / o l d <- second file
1 2 3 4 / 5 6 7 8 9 10
|------------/------------
n 1 | c c c / c c c c c c
e 2 | c c c / c c c c c c
w 3 | c c c / c c c c c c
4 | c c c / c c c c c c
first / / / / / / / / / / / / /
file -> 5 | /
o 6 | /
l 7 | /
d 8 | /
9 | /
10 | /
LIMITATIONS
Repetitive input is the bane of similarity checking. If we have a file containing 4
copies of identical text,
A1 A2 A3 A4
where the numbers serve only to distinguish the identical copies, there are 7 non-
overlapping identities: A1=A2, A1=A3, A1=A4, A2=A3, A2=A4, A3=A4, and A1A2=A3A4. Of
these, only 3 are meaningful: A1=A2, A2=A3, and A3=A4. And for a table with 20 lines
identical to each other, not unusual in a program text, there are 715 non-overlapping
identities, of which at most 19 are meaningful. Reporting all 715 of them is clearly
unacceptable.
This is remedied by sim's search cycle: for each position in the text, the largest segment
is found of which a non-overlapping copy occurs in the text following it. That segment
and its copy are then reported and scanning resumes at the position just after the
segment. For the above example this results in the two identities A1A2=A3A4 and A3=A4,
which is quite satisfactory, and for N identical segments roughly 2 log N messages are
given.
This also works out well when the four identical segments are in different files:
File1: A1
File2: A2
File3: A3
File4: A4
Now combined segments like A1A2 do not occur, and the algorithm finds the runs A1=A2,
A2=A3, and A3=A4, for a total of N-1 runs, all informative.
Calculating Percentages
The above approach is unsuitable for obtaining the exact percentage of a file's content
that can be found in another file, although indicative results can be obtained. Obtaining
exact percentages requires comparing each file pair in isolation; this is what the -ae
options do. Under the -ae options a segment File3:A3, recognized in File4, will again be
recognized in File1 and File2. In the example above it produces the runs
File1:A1=File2:A2
File1:A1=File3:A3
File1:A1=File4:A4
File2:A2=File3:A3
File2:A2=File4:A4
File2:A2=File1:A1
File3:A3=File4:A4
File3:A3=File1:A1
File3:A3=File2:A2
File4:A4=File1:A1
File4:A4=File2:A2
File4:A4=File3:A3
for a total of N(N-1) runs.
When the -e option is used alone. sim will find the following runs:
File1:A1=File2:A2
File1:A1=File3:A3
File1:A1=File4:A4
File2:A2=File3:A3
File2:A2=File4:A4
File3:A3=File4:A4
for a total of ½N(N-1) runs, thus missing half the percentage contributions; in fact,
File4 is found to have 0% in common with the other files.
If, however, the -a option is used alone. sim finds the following runs:
File1:A1=File2:A2
File2:A2=File3:A3
File3:A3=File4:A4
File4:A4=File1:A1
for a total of N runs. This setting misses many of the percentage contributions, but finds
something for every file.
TIME AND SPACE REQUIREMENTS
Care has been taken to keep the time requirements of all internal processes (almost)
linear in the lengths of the input files, by using various tables.
The time requirements are quadratic in the number of files. This means that, for example,
one 64 MB file processes much faster than 8000 8 kB files.
The program requires 6 bytes of memory for each token in the input; 2 bytes per newline
(not when doing percentages); and 80 bytes for each run found.
EXAMPLES
The call
sim_c *.c
highlights duplicate C code in the directory. (It is useful to remove generated files
first.) A call of
sim_c -f -F *.c
can pinpoint the duplicate code further.
A call
sim_text -peu -S new/* "|" old/*
compares each file in new/* to each file in old/*, and if any pair has more that 20% in
common, that fact is reported. Usually a similarity of 30% or more is significant; lower
than 20% is probably coincidence; and in between is doubtful.
The u in -peu causes the output to be unbuffered (and unsorted), so if the program is
stopped for running out of time, any results already found are not lost.
For large data sets, using -pu rather than -peu may do the job much more quickly, but less
accurately.
The | can be used as a separator instead of / on systems where the / as a command-line
parameter gets mangled by the command interpreter.
These calls are good for plagiarism detection.
BUGS
Unbuffered, unsorted output is not available for text output, only for percentage output.
AUTHOR
Dick Grune, Vrije Universiteit, Amsterdam; dick@dickgrune.com.
2017/11/23 SIM(1)