---
kind: concept
slug: string-similarity
title: String similarity
summary: >-
  Scoring how alike two strings are, for matching, deduplication, plagiarism checks or as classifier inputs. Classic measures (LCS, edit distance, Dice) need no language resources. One study turns character co-occurrence and run-length counts into features for a classifier. Its results are author-reported and mostly synthetic, and its real-data gain is not independently checked.
tags: [nlp, text-similarity, feature-engineering, plagiarism-detection]
papers: ["2605.15110"]
related: [gray-level-co-occurrence-matrix, text-classification, random-forest, structural-similarity, text-embedding]
status: draft
updated_at: 2026-11-09
---

## 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 [arxiv: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
[arxiv:2605.15110 tab. 4]. The Dice coefficient is listed with the distances in
the paper's table but is not a distance [arxiv: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 [arxiv:2605.15110 §2] [arxiv: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 [arxiv:2605.15110 §2] [arxiv:2605.15110 eq. 13–16]. The Dice
coefficient is a set-overlap score in the same group [arxiv:2605.15110 eq. 17].

### Information-theoretic measures

Mutual information over characters at the same position, with a variant that
shifts one string first [arxiv:2605.15110 §2] [arxiv: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 [arxiv:2605.15110 §3] [arxiv: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](/concepts/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
[arxiv:2605.15110 §3.1] [arxiv:2605.15110 eq. 21]. Probability, summed-probability
and difference forms are built from this count [arxiv: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 [arxiv:2605.15110 §3.2] [arxiv: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
[arxiv:2605.15110 eq. 28–34].

### Length features

The two string lengths, their difference and its absolute value. They are added
to every feature group [arxiv: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.

| Situation | Use | Why |
|---|---|---|
| Short strings (14 characters) with moderate distortion, labelled pairs available | Co-occurrence, distance or LCS features | In that setting these three sit within about one point of each other, and RLM is about three points lower [arxiv:2605.15110 tab. 3] |
| Long strings (200 characters), few edits | Distance group | Best group average in the synthetic setting, with RLM close behind [arxiv:2605.15110 tab. 6] |
| Long strings with more random edits | RLM group | Highest group average in that setting; all groups still score near 65–70% [arxiv:2605.15110 tab. 7] |
| Tight per-pair latency | LCS or distance features | Feature extraction at 200 characters was about 2,000 ns for LCS, 9,600 ns for distance and 20,300 ns for RLM in the paper's implementation [arxiv:2605.15110 tab. 10] [arxiv:2605.15110 §4.1.3] |
| Word sequences, such as plagiarism of text | RLM and MCLCS features, with Dice | The top-ranked group on the authors' corpus was RLM [arxiv:2605.15110 tab. 16] |
| Need a fast classifier at inference | Tree or rule learners over these features | Classification time for k-NN was about 720 s on the full feature set, against 0.81 s for LMT, in the paper's Weka runs [arxiv:2605.15110 tab. 8] [arxiv:2605.15110 tab. 9] |
| No labelled pairs | Not covered | Every result in the paper uses labelled data for training |

On real data, the paper reports 84.21% accuracy for a four-classifier vote on
a 95-instance plagiarism corpus [arxiv: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
[arxiv: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 [arxiv:2605.15110 §4.1].

```pseudocode
# 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 [arxiv:2605.15110 eq. 18] [arxiv:2605.15110 §2].
- **Counting in RLM.** Count each distinct substring once, as the figure shows,
  not at every position as the equation prints [arxiv:2605.15110 fig. 5]
  [arxiv: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 [arxiv:2605.15110 eq. 21].
- **Ties in the maximum.** The rule for choosing among equal maxima is not
  stated [arxiv:2605.15110 eq. 31] [arxiv:2605.15110 eq. 33].

No official code was found. The companion repository the paper names holds
only datasets and result files [arxiv: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) [arxiv:2605.15110 tab. 6]. At 200 characters
  with randomness 0.15, RLM has the highest average (66.74) [arxiv: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 [arxiv: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) [arxiv:2605.15110 §4.2] [arxiv: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 [arxiv:2605.15110 §4.1.1] [arxiv: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 [arxiv:2605.15110 tab. 3] [arxiv:2605.15110 §4.1.2].

## Papers

- [Proposal and study of statistical features for string similarity computation and classification](/papers/2605.15110): 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.