Proposal and study of statistical features for string similarity computation and classification

In plain words

Deciding how alike two strings are is a common task: checking a scanned word against a dictionary, spotting copied text, or comparing a sentence to a source. The usual tools count shared letters in order, or count the edits needed to turn one string into the other. This paper takes two tools from image analysis instead. One is a co-occurrence table, which counts how often the same character sits at a set offset in both strings. The other is a run-length table, which counts how often each short chunk of one string appears in the other. Both turn into plain numbers that a standard classifier can read, with no dictionary and no grammar, so the same method works for any language.

The authors also tweak mutual information so it notices character order, and they test many such numbers as inputs to classifiers. On made-up word pairs, the new numbers did better than several classic ones. On a plagiarism corpus, the run-length numbers did best. These are the authors' own results, and the authors do not endorse this card.

TL;DR

• Proposes string-similarity features from adapted co-occurrence (COM) and run-length (RLM) matrices, plus a shift-weighted mutual information (WMI) §1 §3.
• Each string pair becomes a feature vector that feeds a classifier; the paper uses Weka learners §4.1.1.
• On synthetic pairs, COM and RLM were statistically stronger than the distance group in 3 of 4 settings §4.1.2.
• On a plagiarism corpus, the reported accuracy is 84.21%, above the dataset's published baselines, but the selection setup leaves room for doubt §4.2.

Problem

Standard string comparisons such as LCS, edit distances and mutual information work without a language model §1 §2. The authors say that semantic measures need a new taxonomy or dictionary for each language, while statistical and rule-based measures can work on any language §2. The proposed features are said to be insensitive to language information [abstract].

Method

Strings are sequences of characters w = c0 … c(n-1). Helper operators are substring extraction, removal of one character, character intersection, and concatenation §1.1 eq. 1–eq. 5. Count helpers are qnt, rep, add and addr eq. 6–eq. 8.

Step 1: baseline features §2. The paper lists these baselines, all used later as comparisons:

• Normalised LCS, with the squared LCS length over the product of the two lengths eq. 9.
• Normalised maximal consecutive LCS (MCLCS), with start offsets n1 and n2 eq. 10–eq. 11.
• Mutual information, whose joint probability counts equal characters at equal positions eq. 12 §2.
• Modified Hamming distance, where the longer string is cut to the shorter one's length eq. 13.
• Levenshtein distance eq. 14–eq. 15 and Damerau distance with adjacent transposition eq. 16.
• Dice coefficient eq. 17.

Step 2: weighted mutual information (WMI) §3. Each character pair is scored with its pointwise mutual information. The score is multiplied by a constant m > 1 when the two characters are equal eq. 18. A shift by d moves the first d characters of a string to its end eq. 19. The score PWMIS sums this weighted value over all shifts d of both strings eq. 20. Table 4 defines the WMI group as PWMI at d = 0, PWMI at d = 1, PWMI at a general d, and PWMIS tab. 4.

Step 3: COM features §3.1. The co-occurrence count at reference position p and shift d is the number of positions k where w1[p] equals w1[k] and also equals w2[k+d] eq. 21. Only identical characters count; this is the paper's change from image-domain COMs fig. 2 fig. 3. Divided by |w1| it becomes the co-occurrence probability COP, per shift eq. 22 or summed over all shifts eq. 23. A probability score (PS) per shift eq. 24 is summed over shifts into TPS eq. 25. COD subtracts a shifted COM sum from another and raises the difference to power g eq. 26.

Step 4: RLM features §3.2. For each run length l, the RLM value counts how often each substring of w1 of length l appears in w2, overlaps included eq. 27. Figure 5 shows that each distinct substring is counted once fig. 5. Features derived from the RLM vector: SO, the sum over l eq. 28; WSO, the same sum with weight l^g eq. 29; MO, the maximum over l eq. 30; MORL, the l at which MO occurs eq. 31; MOML, a weighted maximum eq. 32; MLMO, the smallest l at which the maximum occurs eq. 33; and RLMMCLCS, the largest l with a non-zero count eq. 34.

Step 5: synthetic data §4.1. Words are drawn from the characters 'A' to 'z' (ASCII 65–122) eq. 43 and distorted by five steps that run in a fixed order and are gated by R eq. 35–eq. 42, fig. 6. Half of the pairs get a freshly drawn second word (label FALSE), and the other half get a distorted copy of the first word (label TRUE) eq. 44 tab. 2.

The generator and the distortion pipeline:

# Synthetic word generator  [§4.1] [eq. 43]
# Alphabet: ASCII codes 65 ('A') to 122 ('z') inclusive  [tab. 1]
# M: maximum length (14 or 200); R: randomness in [0, 1]
def random_char():
    # one random character from the alphabet  [eq. 43]
    return chr(randint(65, 122))

def random_word(max_len):
    # length drawn uniformly from 1..max_len  [eq. 43]
    length = randint(1, max_len)
    return "".join(random_char() for _ in range(length))

def make_pair(M, R):
    # Base word  [eq. 43]
    w1 = random_word(M)
    # Half the pairs: fresh unrelated word, label FALSE  [eq. 44]
    if random() > 0.5:
        return w1, random_word(M), False
    # Other half: distorted copy of w1, label TRUE  [eq. 44]
    return w1, distort(w1, R), True

# Distortion pipeline C_F  [eq. 42] [fig. 6]
# Order: C1 once, C2 N times, C3 once, C4 N times, C5 N times
# N = |w| // 2 as printed; see Pitfalls for when N is measured
def distort(w, R):
    w = c1_truncate(w, R)                    # [eq. 35]
    for _ in range(len(w) // 2):             # N times  [eq. 42]
        w = c2_replace(w, R)                 # [eq. 36]
    w = c3_move_to_front(w, R)               # [eq. 37]–[eq. 38]
    for _ in range(len(w) // 2):             # N times  [eq. 42]
        w = c4_add_at_edge(w, R)             # [eq. 39]–[eq. 40]
    for _ in range(len(w) // 2):             # N times  [eq. 42]
        w = c5_move_to_end(w, R)             # [eq. 41]
    return w

def c1_truncate(w, R):
    # Keep a random-length prefix if random() >= 0.9 - R  [eq. 35]
    if random() >= 0.9 - R:
        return w[0 : randint(0, len(w))]
    return w

def c2_replace(w, R):
    # Replace one character if random() >= 1 - R  [eq. 36]
    if random() >= 1 - R:
        pos = randint(0, len(w) - 1)
        return w[:pos] + random_char() + w[pos + 1 :]
    return w

def c4_add_at_edge(w, R):
    # Gate 1: random() >= 0.4 - R  [eq. 40]
    if random() < 0.4 - R:
        return w
    # Gate 2: random() >= 0.9 - R; add at start or end, 50/50  [eq. 39]
    if random() >= 0.9 - R:
        return random_char() + w if random() < 0.5 else w + random_char()
    return w

def c5_move_to_end(w, R):
    # Gate: random() >= 0.4 - R; remove one character and append it  [eq. 41]
    if random() >= 0.4 - R:
        pos = randint(0, len(w) - 1)
        return w[:pos] + w[pos + 1 :] + w[pos]
    return w

The C3 step is not written as code. Its printed rule (eq. 37–38) returns the string unchanged when its test fails, so a loop that runs "until no elements are left" would never end. The implementer must choose the loop bound (see Pitfalls).

Step 6: COM code. These functions implement COM, COP, TPS and COD exactly as printed eq. 21–eq. 26.

# Co-occurrence count at position p and shift d  [eq. 21]
# Counts k where w1[p] == w1[k] == w2[k + d]
def com(w1, w2, p, d):
    count = 0
    for k in range(len(w1)):                  # k = 0 .. |w1| - 1
        # Guard k + d: its range is not stated [eq. 21]
        if k + d >= len(w2):
            continue
        if w1[p] == w1[k] and w1[k] == w2[k + d]:
            count += 1
    return count

# Co-occurrence probability at p and d  [eq. 22]
def cop_at_shift(w1, w2, p, d):
    return com(w1, w2, p, d) / len(w1)

# Co-occurrence probability at p summed over all shifts  [eq. 23]
def cop(w1, w2, p):
    total = sum(com(w1, w2, p, d) for d in range(len(w1)))
    return total / len(w1)

# Probability score for one shift d  [eq. 24]
def ps(w1, w2, d):
    score = 0.0
    for p in range(len(w2)):                  # p = 0 .. |w2| - 1  [eq. 24]
        if w2[p] in w1:
            # Position in w1 of the matching character (first match assumed)
            p_w1 = w1.index(w2[p])
            score += cop_at_shift(w1, w2, p_w1, d)
        else:
            score += -1.0                     # penalty [eq. 24]
    return score

# Total probability score: PS summed over d  [eq. 25]
def tps(w1, w2):
    return sum(ps(w1, w2, d) for d in range(len(w2)))

# Co-occurrence difference over distances  [eq. 26]
def cod(w1, w2, g=1):
    half = len(w1) // 2
    total = 0.0
    for d in range(half):                     # upper limit as printed
        first = sum(com(w1, w2, p, d) for p in range(len(w2)))
        second = sum(
            com(w1, w2, p, d + ceil(len(w1) / 2)) for p in range(len(w1))
        )
        total += (first - second) ** g        # g = 1 in experiments
    return total

Step 7: RLM code. These functions implement RLM and its aggregates eq. 27–eq. 34. The counting rule follows fig. 5.

# Occurrences of s in w, overlapping ones included  [eq. 6]
def occurrences(w, s):
    return sum(1 for p in range(len(w) - len(s) + 1)
               if w[p : p + len(s)] == s)

# RLM value for run length l  [eq. 27]
# Each distinct substring of w1 of length l counts once  [fig. 5]
def rlm(w1, w2, l):
    total = 0
    seen = set()
    for p in range(len(w1) - l + 1):          # 0 <= p < |w1|, l <= |w1| - p
        s = w1[p : p + l]
        if s in seen:
            continue
        seen.add(s)
        total += occurrences(w2, s)
    return total

# Run-length features  [eq. 28]–[eq. 34]
def rlm_features(w1, w2, g=1):
    lengths = range(1, len(w1) + 1)           # l > 0 assumed  [eq. 27]
    values = {l: rlm(w1, w2, l) for l in lengths}
    so = sum(values.values())                 # [eq. 28]
    wso = sum(l ** g * values[l] for l in lengths)   # [eq. 29]
    mo = max(values.values())                 # [eq. 30]
    # First maximum wins; tie rule not stated  [eq. 31]
    morl = max(lengths, key=lambda l: values[l])
    # Pick the length by the weighted value, then undo the weight
    # [eq. 32] [§3.2]
    best = max(lengths, key=lambda l: values[l] / (l ** g + 1))
    moml = values[best]                       # weight multiplied back in
    mlmo = min(l for l in lengths if values[l] == mo)   # [eq. 33]
    rlmmclcs = max(
        (l for l in lengths if values[l] >= 1), default=0    # [eq. 34]
    )
    return {"SO": so, "WSO": wso, "MO": mo, "MORL": morl,
            "MOML": moml, "MLMO": mlmo, "RLMMCLCS": rlmmclcs}

Step 8: WMI code. Equation 18 uses a ratio of joint to marginal probabilities. The paper defines the joint as co-occurrence at the same position §2, the marginals as the character frequencies in each string §2, and the shift as in eq. 19.

# Shift a string: move its first d characters to the end  [eq. 19]
def shift(w, d):
    return w[d:] + w[:d]

# Pointwise weighted MI for one character pair  [eq. 18]
# joint: rho(c1, c2); marg1: rho(c1); marg2: rho(c2)  [§2]
def pwmi(c1, c2, joint, marg1, marg2, m=2, g=None):
    # log_base(x, g) is log to base g; g is not stated for WMI
    ratio = joint / (marg1 * marg2)
    if c1 == c2:
        return m * log_base(ratio, g)         # weighted when equal  [eq. 18]
    return log_base(ratio, g)                 # otherwise  [eq. 18]

# PWMIS: sum over shifts d of PWMI on both shifted strings  [eq. 20]
def pwmis(w1, w2, m=2, g=None):
    total = 0.0
    for d in range(max(len(w1), len(w2))):   # d = 0 .. max(...) - 1  [eq. 20]
        s1 = shift(w1, d)
        s2 = shift(w2, d)
        # joint and marginal probabilities are recomputed on s1, s2
        # (assumption; not stated in [§3])
        for c1 in s1:
            for c2 in s2:
                total += pwmi(c1, c2, *probs(s1, s2, c1, c2), m, g)
    return total

Table 4 gives the complete feature list for each group. Every group also has the four length features (|w1|, |w2|, |w2| − |w1|, abs(|w2| − |w1|)) tab. 4. The six groups and their feature names are:

Step 9: classification. Nine Weka learners were used, with ZeroR as the null baseline: LMT, random forest, REPTree, multilayer perceptron, IBk (k-NN), Hoeffding tree, decision table, RBF network and naive Bayes §4.1.1 tab. 3. The text calls these "ten distinct classifiers", counting ZeroR §4.1.1. Evaluation is stratified 10-fold cross-validation on 100,000 instances per setting §4.1.1. Each learner's parameters were tuned by a Weka grid search, run for about one hour on a reduced dataset per learner and setting §4.1.1.

Hyperparameters

Results

Author-reported. Setup: synthetic word and sentence pairs, Weka learners, 10-fold cross-validation §4.1. The LMT row is shown for each setting with ZeroR as the baseline (accuracy, %) tab. 3 tab. 5 tab. 6 tab. 7.

• Averaged over the nine learners, the best group at M = 200, R = 0 is the distance group (97.81) followed by RLM (96.17) tab. 6.
• At M = 200, R = 0.15, RLM has the highest group average (66.74) tab. 7.
• The paper reports LMT as the best learner on average in the synthetic settings (76.84 at M = 14, R = 0.5) tab. 3 §4.1.1.
• The paper reports that COM and RLM were statistically stronger than the distance group under LMT in 3 of 4 settings; at R = 0 the RLM group ties with the distance group §4.1.2.
• Timing (Weka, Java, unoptimised): LMT trains in 722.79 s on all features and classifies in 0.81 s on the same data; k-NN trains in 0.05 s on all features and classifies in 720.05 s tab. 8 tab. 9.
• Feature extraction on 200-character strings at R = 0.15 (ns per instance): COM group 12,079 including 4,552 to build the matrix; RLM group 20,272 including 16,705 to build the matrix; WMI 26,278; MI 28,029; distance 9,566; LCS 2,048; length 1,306 tab. 10 §4.1.4.
• Top attributes by Weka ranking (LMT, accuracy). For 14 characters at R = 0.9: TPS/|w2| (COM), NLCS (LCS), NMCLCS(∀,∀) (MCLCS), SO/|w2| (RLM) tab. 11. For 200 characters at R = 0.15: MORL (RLM), RLMMCLCS (RLM), NMCLCS(∀,∀) (MCLCS), Dice (distance) tab. 12.

Plagiarism corpus §4.2. The corpus has four classes: near copy, light revision, heavy revision and non-plagiarism §4.2. The paper reports 84.21% accuracy with a four-learner vote, against 66.31% for Clough and Stevenson (2011) and 70.52% for Chong et al. (2014) tab. 13. Under the vote, the confusion matrix has 80 correct of 95 tab. 14. Per-class recall is 1.0 for non-plagiarism, 0.789 for light and heavy revision, and 0.632 for cut-and-paste tab. 15. The top-ranked feature group is RLM, with MCLCS(w1, w2), MORL and Dice next tab. 16.

Paper vs code

No official code. The paper's conclusion and reference list point to a GitHub repository (Oyatsumi/StringSimilarity) for "the datasets and source codes" §5 [ref. Rodrigues 2020]. That repository holds only dataset files and result text or ARFF outputs, with no source code and no LICENSE file, and its owner is not verified as an author. A GitHub repository search for "StringSimilarity" (first 18 of 65 results) and a search for the method names found no repository that belongs to the authors. Searches are not exhaustive. Nothing from the data or result files is used on this card.

Pitfalls

• Co-occurrence needs equal characters. The paper defines a co-occurrence as the same character at the same position in both strings §2. Under that definition the joint probability of two different characters is zero. Eq. 18 takes the log of that ratio for c1 ≠ c2, which is log(0). The paper does not state a rule for zero probabilities, and the MI sum's 0·log 0 convention is also unstated eq. 12 eq. 18.
• The example denominator is not the count of equal positions. Under the paper's example, ρ(c1, c1) = 2/4, with four total positions. Only three positions hold equal characters there. The normalisation (positions, or equal-position pairs) is not stated §2.
• RLM counts distinct substrings once. Eq. 27 as printed sums over every position p, which would count repeats. Figure 5 counts each distinct substring once. Overlapping occurrences in w2 are counted (for example aa occurs twice in aaabc). Follow fig. 5 unless code shows otherwise.
• The l range varies across equations. RLM is defined for l > 0 eq. 27, but the sum in eq. 28 and the MOML maximum in eq. 32 start at l = 0. The upper limit l_f in eq. 30 is not defined beyond "the maximal possible length". Ties in MORL and MLMO are not resolved. The implementation in this card uses l = 1 .. |w1| and resolves MORL ties to the first maximum.
• MOML is printed ambiguously. The text says the division by (l^g + 1) is undone after the maximal length is chosen §3.2, so the value returned equals the RLM at the chosen length. Eq. 32 renders this unclearly. The implementation follows the text.
• Shift semantics differ between features. Table 4 says MI_d shifts w2 only tab. 4. Eq. 20 shifts both strings for PWMIS, and it is not stated whether ρ is recomputed on the shifted strings. The meaning of "d" in PWMI_d and MI_∀d is not defined.
• COD upper bound and indices. The outer sum's limit is read from the scan as ⌊|w1|/2⌋ − 1; check against the PDF. Its inner sum over p ranges to |w2|, but COM uses w1[p], so p can exceed |w1| − 1. The printed form has no guard.
• COM index range. Eq. 21 does not say what happens when k + d leaves w2. The implementation skips those k (assumed). PS uses the first occurrence of a character in w1 when there are repeats; the paper does not say which occurrence.
• Distortion counts and gates. Eq. 42 uses N = |w|/2 for C2, C4 and C5, but the prose says C2 and C5 run "|w| = 2" times and that C4 runs for |w| = 2. The implementation uses N = |w| // 2, measured when each loop starts (assumed). C2 draws its index from ran(0, |w|), which can point past the end; the implementation uses 0..|w|−1. C3 has two gates (0.6 − √R and 0.6) and no stated loop bound. C4 has two gates (0.4 − R and 0.9 − R). Both are coded as printed.
• Label semantics. The TRUE label goes with the distorted copy, not the fresh word eq. 44 tab. 2.
• Alphabet. Random characters are drawn from ASCII 65–122, which includes punctuation such as [, , ], ^, _ and `. Table 1 shows examples such as "cakE_Cg_kakG[h" tab. 1 eq. 43.
• Plagiarism strings are word tokens. Each distinct word is mapped to one character (UTF-16), so the strings compared are word sequences, not text characters §4.2. The paper calls this problem "multi-label" but reports a four-class confusion matrix §4.2 tab. 14.
• The 84.21% result has selection risk. The four-learner vote was chosen by Auto-Weka, then adjusted by hand. A feature reduction step (keeping rlmMCLCS, rlm-MORL and Dice) runs before classification. The paper does not say whether that step, or the Auto-Weka search, used held-out data. Treat the 84.21% as optimistic §4.2.
• The baseline was not reproduced. The authors could not reproduce the 80% accuracy that Clough and Stevenson (2011) reported and found 70%. They report 66.31% from that paper's confusion matrix §4.2 tab. 13.
• Text and table disagree in places. The text quotes 71.66% for the COM group in Table 5, while the table's COM mean reads 71.62 §4.1.1 tab. 5. The text says "LWT" for the single-learner plagiarism result, which is almost certainly LMT §4.2. Table 12 labels TPS/|w2| as RLM, while TPS belongs to COM tab. 4 tab. 12. Check these against the PDF before relying on them.
• Significance test not named. The tables give thresholds of 0.01 and the text gives 0.001. The test and multiple-comparison handling are not stated tab. 3 §4.1.2. ZeroR is the null.
• Timing comparisons are not optimised. Weka runs in Java, and the authors say optimised C would be faster §4.1.3. Compare groups within this paper, not against other systems.
• Venue and dates. The PDF header gives a 2020 journal reference (Int. J. Data Mining, Modelling and Management, 12(3), 277–307), while arXiv v1 is dated 2026-05-14. Cite the arXiv version with its date.

Lineage

• Builds on: Rodrigues et al. (2016) for the weighted MI measure §3; the co-occurrence matrix from visual computing, as in Rodrigues et al. (2014) §3.1; the run-length matrix from Tang (1998) §3.2.
• Compared against: normalised LCS and MCLCS, mutual information, modified Hamming, Levenshtein, Damerau and Dice §2 §4; plagiarism results from Clough and Stevenson (2011) and Chong et al. (2014) tab. 13.
• Superseded by: not known from this wiki.