String similarity

Overview

The problem is to turn a pair of strings into a number that says how alike they are, or how far apart. The number is then used directly (a threshold on a match score) or fed to a classifier as one input among several. The invariant shared by the measures is that they need no dictionary, grammar or language model: they work from the symbols themselves 2605.15110 §2.

Two families of measures are in use. Some count shared structure, such as the longest common subsequence or shared characters at the same offset. Others count the operations needed to turn one string into the other, such as Levenshtein or Damerau distance. The sign convention differs between them: a distance is small for close strings, while a similarity is large 2605.15110 tab. 4. The Dice coefficient is listed with the distances in the paper's table but is not a distance 2605.15110 tab. 4.

Variants

Subsequence measures

Normalised longest common subsequence (LCS), and its variant that counts the longest run of consecutive matching characters (MCLCS). Both are normalised by string length 2605.15110 §2 2605.15110 eq. 9–11. These are the baselines the study uses most often.

Edit distances

Modified Hamming distance (the longer string is cut to the shorter length), Levenshtein distance, and Damerau distance, which also allows adjacent transpositions 2605.15110 §2 2605.15110 eq. 13–16. The Dice coefficient is a set-overlap score in the same group 2605.15110 eq. 17.

Information-theoretic measures

Mutual information over characters at the same position, with a variant that shifts one string first 2605.15110 §2 2605.15110 tab. 4. The weighted mutual information (WMI) of the same paper multiplies the pointwise score by a constant m > 1 when the two characters are equal, and sums over cyclic shifts of both strings 2605.15110 §3 2605.15110 eq. 18–20.

Co-occurrence features (COM)

Adapted from grey-level co-occurrence matrices in image analysis (see Gray-level co-occurrence matrix). The count at a reference position and a shift is the number of positions where one character matches the same character in the other string. Only identical characters count, which is the paper's change from the image version 2605.15110 §3.1 2605.15110 eq. 21. Probability, summed-probability and difference forms are built from this count 2605.15110 eq. 22–26.

Run-length features (RLM)

For each run length l, the value counts how often each distinct substring of length l from the first string appears in the second. Overlapping occurrences in the second string are counted 2605.15110 §3.2 2605.15110 fig. 5. Summaries over l include a sum, a weighted sum, a maximum, the length at which the maximum occurs and the longest length with a non-zero count 2605.15110 eq. 28–34.

Length features

The two string lengths, their difference and its absolute value. They are added to every feature group 2605.15110 tab. 4.

When to use which

The study always feeds features to a classifier. It does not test any measure used alone as a score, so the rows below apply to the classifier setting.

On real data, the paper reports 84.21% accuracy for a four-classifier vote on a 95-instance plagiarism corpus 2605.15110 §4.2. The classifier vote was picked by an automated search and then adjusted by hand, and the paper does not say whether held-out data was used for either step, so the number is likely optimistic 2605.15110 §4.2. Use it as a pointer to features worth testing on your own data, not as a result to rely on.

Implementation sketch

The shared core is: build the features for each pair, then train a classifier on labelled pairs. The steps follow the paper's pipeline 2605.15110 §4.1.

# Choose the symbols: characters, or one symbol per distinct word  [§4.2]
def to_symbols(text_a, text_b, unit="char"):
    ...

# Baseline measures: normalised LCS, MCLCS, edit distances, Dice  [§2]
def baseline_features(w1, w2):
    ...

# Run-length aggregates over lengths 1..|w1|  [§3.2] [eq. 27]–[eq. 34]
def rlm_features(w1, w2):
    ...

# Co-occurrence sums over shifts  [§3.1] [eq. 21]–[eq. 26]
def com_features(w1, w2):
    ...

# One vector per pair: all groups plus the length features  [tab. 4]
def pair_vector(w1, w2):
    f = baseline_features(w1, w2)
    f.update(rlm_features(w1, w2))
    f.update(com_features(w1, w2))
    f.update({"len1": len(w1), "len2": len(w2)})  # diff and abs diff too
    return f

# Train on labelled pairs; evaluate with stratified 10-fold CV  [§4.1.1]
# model = train(classifier, [pair_vector(a, b) for a, b, y in pairs], labels)

Points where implementations must choose, because the paper does not fix them:

• Zero probabilities in WMI. The log base is not stated, and the log of zero is undefined for different characters, which the joint definition produces 2605.15110 eq. 18 2605.15110 §2.
• Counting in RLM. Count each distinct substring once, as the figure shows, not at every position as the equation prints 2605.15110 fig. 5 2605.15110 eq. 27.
• Index guards in COM. The equation does not say what happens when the shifted index leaves the second string. One reading is to skip those positions; that choice is an assumption 2605.15110 eq. 21.
• Ties in the maximum. The rule for choosing among equal maxima is not stated 2605.15110 eq. 31 2605.15110 eq. 33.

No official code was found. The companion repository the paper names holds only datasets and result files 2605.15110 §5. Any implementation must be written from the equations.

Contradictions

• Which group wins on synthetic data depends on the setting. At 200 characters with no randomness, the distance group has the highest average (97.81) and RLM is second (96.17) 2605.15110 tab. 6. At 200 characters with randomness 0.15, RLM has the highest average (66.74) 2605.15110 tab. 7. The paper's text says COM and RLM beat the distance group in three of four settings, and that RLM ties with it at zero randomness 2605.15110 §4.1.2.
• Baseline accuracy on the plagiarism corpus. The paper cites 80% for Clough and Stevenson (2011), which its own reproduction did not confirm. It reports 66.31% from that paper's confusion matrix and 70.52% for Chong et al. (2014) 2605.15110 §4.2 2605.15110 tab. 13. Readers should check which figure they compare against.
• Internal inconsistencies. The text gives 71.66% for the COM group where the table gives 71.62 2605.15110 §4.1.1 2605.15110 tab. 5. The significance threshold is 0.01 in the tables and 0.001 in the text, and the test is not named 2605.15110 tab. 3 2605.15110 §4.1.2.

Papers

• Proposal and study of statistical features for string similarity computation and classification: adapts co-occurrence and run-length matrices from image analysis and a shift-weighted mutual information into string features for classifiers. Results are author-reported and mostly synthetic.