A WEIGHTED ANGLE DISTANCE ON STRINGS
arXiv:2604.20633v1 [math.MG] 22 Apr 2026
GRANT MOLNAR Abstract. We define a multi-scale metric dρ on strings by aggregating angle distances between all n-gram count vectors with exponential weights ρn . We benchmark dρ in DBSCAN clustering against edit and n-gram baselines, give a linear-time suffix-tree algorithm for evaluation, prove metric and stability properties (including robustness under tandemrepeat stutters), and characterize isometries.
1. Introduction This paper was motivated by a simple question: can we define a natural metric on strings for which (ab)4 = abababab and (ab)20 = abababababababababababababababababababab are close? In many symbolic-sequence settings—including text processing, computational biology, and log or trace analysis—repeated use of a short motif is often semantically mild: the string “stutters” without changing its essential type. Classical edit distances (e.g. Levenshtein or Damerau–Levenshtein) treat this as a large change, since inserting additional tandem copies requires many operations, and the distance grows linearly with the number of repeated blocks. When repetition scale is a nuisance factor rather than a signal, this behavior is undesirable. Rather than introducing new edit operations, we take a feature-based, multi-scale approach. Fix a finite alphabet Σ. For each string S ∈ Σ∗ and each length n ≥ 1 we form n the n-gram count vector [S]n ∈ RΣ . We compare these vectors using the angle distance θ (the arccosine of cosine similarity), and we aggregate the discrepancy across all n using an exponentially decaying weight ρn : X (1) dρ (S, T ) := ρn θn (S, T ), θn (S, T ) := θ([S]n , [T ]n ). n≥1
Intuitively, θn (S, T ) measures how similar the local n-gram statistics of S and T are, and the parameter ρ controls how strongly we discount longer-range interactions. Small ρ emphasizes short grams (local structure), while larger ρ assigns more weight to longer grams (global structure). Although (1) is defined for all ρ > 0 (only finitely many terms are nonzero), when 0 < ρ < 1 the series viewpoint is most transparent and yields uniform bounds such as dρ (S, T ) ≤
ρ π · 2 1−ρ
for all S, T ∈ Σ∗ .
In particular, dρ is insensitive to length at large scales: it is designed to compare pattern profiles rather than raw counts. This work was carried out at ARKA. Patent pending. 1
2
GRANT MOLNAR
Contributions. We now summarize the main results of the paper. • A multi-scale cosine geometry on strings. For every ρ > 0 we define the weighted angle distance dρ on Σ∗ and show that it is a metric (Proposition 7.1). The construction is alphabet-invariant: any permutation of Σ induces an isometry of (Σ∗ , dρ ). • Linear-time computation. We give a generalized suffix-tree (or suffix-array) algorithm that computes dρ (S, T ) in time O(|S| + |T |) (Proposition 4.3), by reducing the necessary dot products and norms across all n as aggregates over internal nodes of the generalized suffix tree. • Empirical evaluation. In Section 5 we evaluate dρ inside a fixed DBSCAN clustering pipeline on three labeled sequence benchmarks, comparing against edit distances and fixed-scale k-gram baselines. The results suggest that weighted angle distances can be particularly effective on datasets whose class structure is driven by tandem-repeat statistics, while remaining competitive with classical baselines on more conventional corpora. • Quantitative control of local edits and repetition. We prove explicit Lipschitztype bounds for elementary edits (Theorem 7.3) and for stutter operations (Theorem 7.4), formalizing the idea that repeating a block in place produces only a controlled perturbation in dρ . • Topological and geometric structure. We show that dρ induces the discrete topology on Σ∗ , but that when 0 < ρ < 1 the metric completion is nontrivial. We identify this completion with the disjoint union of finite strings and shift-invariant Borel probability measures on one-sided infinite strings, equipped with a natural extension of dρ (Theorem 7.18). This connects dρ to the geometry of empirical and limiting n-gram distributions. • Rigidity of symmetries. We completely characterize the isometry group of (Σ∗ , dρ ): every isometry is either a symbol permutation or the composition of a symbol permutation with string reversal (Theorem 7.24). Organization. In Section 2 we fix notation and introduce n-gram count vectors and the angle distance on nonnegative vectors. Section 3 places the construction in context with standard edit and n-gram distances. Section 4 gives the linear-time computation via generalized suffix trees. Section 5 reports clustering experiments and discusses the dependence on ρ. Finally, Section 6 summarizes takeaways and directions for future work.
2. Preliminaries and Definitions We begin by recalling some standard notation from formal language theory. Throughout, we let Σ denote a fixed alphabet with finitely many characters, we write Σn F ≤N := n for the length n strings over the alphabet Σ, we write Σ n≤N Σ for the set of strings F of length at most N over Σ, and we write Σ∗ := n≥0 Σn for the set of all strings over Σ. If S ∈ Σm , we write |S| = m. For S1 , S2 ∈ Σ∗ , we write S1 S2 for the concatenation of S1 and S2 . The map |·| : Σ∗ → Z≥0 is a morphism of monoids, so |S1 S2 | = |S1 | + |S2 |. We write ϵ for the empty string, so for any S ∈ Σ∗ we have ϵS = Sϵ = S. Definition 2.1. We say Q is a substring of S if S = P1 QP2 for some P1 , P2 ∈ Σ∗ . We say Q has multiplicity c(S, Q) in S if there are exactly c(S, Q) pairs (P1 , P2 ) such that S = P1 QP2 . If Q is a substring of S and |Q| = n, we say that Q is an n-gram of S.
A WEIGHTED ANGLE DISTANCE ON STRINGS
3
Remark 2.2. In formal language theory, a string is commonly referred to as a “word”; in genomics, a k-gram is typically referred to as a “k-mer”. We opt to retain the phraseology more common in computer science and machine learning. n
We write N = { 1, 2, . . . } for the set of positive integers. We identify RΣ with the space n of real-valued functions on Σn , so that a vector v ∈ RΣ is written as v : X 7→ v(X). n
Definition 2.3. For S ∈ Σ∗ and n ∈ N, we define [S]n ∈ RΣ as follows: [S]n : X 7→ c(S, X). Thus, [S]n counts all length n substrings of S. Example 2.4. Let Σ = { a, b } and let S = abab. Then [S]2 = { aa : 0, ab : 2, ba : 1, bb : 0 }. Omitting 0 entries, we write [S]2 = { ab : 2, ba : 1 }. √ Recall that for v ∈ RN a vector, we write ∥v∥ = v · v for the Euclidean norm of v. N Definition 2.5. For any integer N ≥ 0, we define the angle distance θ : RN ≥0 ×R≥0 → [0, π/2] by u·v arccos if u, v ̸= 0, ∥u∥∥v∥ θ(u, v) := 0 if u = v = 0, π else. 2
The map θ is a pseudometric on its domain, and restricts to a metric on the unit sphere in RM ≥0 . We are now ready to define our main object of study. Definition 2.6. Let Σ be a finite alphabet, and let ρ > 0 be arbitrary. We define the ρ-weighted angle distance dρ : Σ∗ × Σ∗ → R≥0 as X dρ : (S, T ) 7→ ρn θn (S, T ), n≥1
where θn (S, T ) := θ([S]n , [T ]n ). Note that θ([S]n , [T ]n ) = 0 whenever n > max (|S| , |T |), so dρ is well-defined even when ρ ≥ 1. In essence, for each scale n, we embed a string S as its n-gram count vector [S]n , and compare two strings by the angle between these vectors (so we compare patterns, not lengths). Then dρ (S, T ) is given by summing these angular discrepancies across all scales, with an exponential weight ρn that lets you tune how much you care about longer vs. shorter structure. Example 2.7. Let Σ = {a, b}, take S = ab and T = ba, and fix ρ > 0. At scale n = 1, both strings have the same unigram counts, so [S]1 = {a : 1, b : 1} = [T ]1 and thus θ1 (S, T ) = 0. At scale n = 2, the bigram vectors are supported on different coordinates, [S]2 = {ab : 1}, [T ]2 = {ba : 1}, so [S]2 and [T ]2 are orthogonal, and θ2 (S, T ) = π/2. All higher n contribute 0, hence π dρ (S, T ) = ρ2 · . 2 ∗ Proposition 2.8. For any ρ > 0, the map dρ : Σ × Σ∗ → R≥0 is a metric.
4
GRANT MOLNAR
See Proposition 7.1 below for a proof of this fact. The weighted angle distance dρ is built from a standard representation of strings: for each n n ≥ 1, a string S ∈ Σ∗ determines an n-gram count vector [S]n ∈ RΣ encoding its pattern frequencies at scale n. Using the angle (cosine) distance between these vectors is natural because it compares profiles rather than magnitudes, so it is comparatively insensitive to length and to tandem repetition (stutter) while still detecting changes in local structure. Summing these angular discrepancies over all n yields a genuinely multi-scale notion of similarity, with the weight ρn providing a transparent control of how strongly longer-range patterns are emphasized. Moreover, the construction is alphabet-agnostic and admits a linear-time evaluation via generalized suffix trees (or suffix arrays), making it a computationally tractable alternative to edit-based distances when repeated motifs are the dominant signal. 3. Related Work The study of distances on strings has a long history spanning theoretical computer science, information retrieval, and computational biology. Our ρ-weighted angle distance sits at the intersection of two major themes: n-gram feature-space methods and string kernels, and alignment-free approaches for biological sequences. We begin this section, however, with the standard approach to string distances. 3.1. Edit-based distances and stutter resistance. The most classical and widely used metrics on strings are edit-based. Hamming distance measures the number of substitutions between equal-length strings [4]. The Levenshtein (edit) distance extends this to insertions and deletions, and can be computed in quadratic time via the dynamic programming algorithm of Wagner and Fischer [7, 20]. The Damerau–Levenshtein distance further allows transpositions of adjacent characters, capturing common typo patterns [3]. These metrics are fundamental in coding theory, pattern matching, spell correction, and sequence alignment, precisely because they track local, position-sensitive edits. However, edit distances can behave poorly when the main notion of similarity is repetition scale rather than literal edit alignment. For example, (ab)4 and (ab)20 are far apart in Levenshtein distance despite having essentially the same local n-gram structure repeated at different scales. In such settings one would like a metric that treats stutters (repetitive block expansions) as relatively small perturbations. Recent work by Petty et al. proposes a new edit-based distance designed to address some of these weaknesses, with a particular focus on capturing repetition-robust similarity while preserving an operational “editing” interpretation [15]. Their construction augments the edit operations with a family of stutter-like transformations, but requires one to commit in advance to a menu of permissible stutters and to perform substantial precomputation to support them. Our approach is complementary: rather than enriching the suite of permissible edits, we adopt a multi-scale, compositional viewpoint based on weighted angular comparisons of ngram count vectors. This shifts the inductive bias from “minimal edits” to “similar local statistics across scales,” which naturally compresses length inflation caused by repeated blocks. 3.2. n-gram feature spaces, cosine geometry, and string kernels. A large body of work represents strings by their substring statistics and compares the resulting vectors in a feature space. Character n-gram profiles have long been successful in tasks such as language identification and text categorization, especially for short or noisy documents [1]. In classical
A WEIGHTED ANGLE DISTANCE ON STRINGS
5
information retrieval, the vector space model represents documents and queries as weighted term vectors and uses cosine similarity for comparison [16, 10]. This paradigm underlies many modern practices, including readily available string-similarity toolkits that expose cosine distance on n-gram count vectors as a basic primitive [14]. In theoretical and applied work on string kernels, this perspective is formalized in a reproducing-kernel-Hilbert-space framework. The spectrum kernel is essentially the inner product on k-gram count vectors, while mismatch-style kernels allow controlled perturbations of substrings; both families have been highly influential in text and biological sequence classification [9, 5, 6, 18]. From this viewpoint, one typically fixes a scale k and measures similarity in the associated feature space. Related ideas appear in approximate string matching and filtering using q-grams [19]. Our construction differs structurally from most fixed-k approaches. The distance dρ incorporates all n-gram scales via an exponentially decaying weight ρn and uses the angle between raw count vectors at each scale. This produces a bona fide metric on Σ∗ (for any ρ > 0, and uniformly bounded when ρ ∈ (0, 1)), while retaining the interpretability and conditioning benefits associated with cosine geometry. 3.3. Alignment-free sequence comparison and sketching. In genomics and metagenomics, alignment-free methods compare biological sequences using k-mer count or frequency vectors, together with various geometric or information-theoretic dissimilarities [13, 21]. Such methods are particularly attractive when alignment is computationally expensive or conceptually inappropriate, and they often rely on k-mer statistics that are closely analogous to our n-gram counts. Scaling these ideas to very large datasets has led to sketch-based techniques. For example, Mash uses MinHash sketches of k-mer sets to approximate distances between genomes and metagenomes extremely quickly, while still maintaining good empirical accuracy [12]. These approaches demonstrate that compositional statistics can serve as robust fingerprints when explicit alignment is infeasible or undesirable. Our metric shares with alignment-free methods the use of substring statistics as primary features, but differs in several respects: it aggregates all scales n with a principled weighting, is explicitly cosine-derived at each scale, and is provably a metric on the space of finite strings. The suffix-tree-based algorithm we describe in Section 4 ensures that this multiscale construction remains computationally tractable in practice. 3.4. Compression-based distances. Another strand of work compares strings via compression, using compressor behavior as a proxy for shared structure. The normalized compression distance (NCD) of Cilibrasi and Vitányi [2] is a prominent example: it defines a universal, task-agnostic similarity measure derived from the Kolmogorov complexity framework, instantiated with real-world compressors. NCD and related methods can capture very rich regularities without hand-crafted features, but are often sensitive to the choice of compressor and can be less transparent analytically. By contrast, our approach affords explicit combinatorial and geometric control over substring statistics: the metric is built from concrete n-gram counts and the geometry of angles n in RΣ , and admits direct analysis of its stability under edits and stutters. 3.5. Summary. In summary, dρ may be viewed as a metric-level synthesis of ideas that have appeared independently across n-gram feature comparisons [1, 16, 10], string kernels [9, 5, 6, 18], and alignment-free sequence analysis [13, 12, 21], while remaining conceptually distinct from both classical edit distances [4, 7, 20, 3, 15] and compression-based similarities [2]. To the best of our knowledge, none of the existing constructions simultaneously offers
6
GRANT MOLNAR
(i) robustness to stutter-like repetition, (ii) multi-scale n-gram sensitivity, and (iii) provable metric structure together with a linear-time algorithm for exact evaluation on finite strings. 4. Computation In this section, we describe an efficient method for computing dρ (S, T ) for two strings S, T ∈ Σ∗ . Throughout, we write m := |S|, n := |T |, and Lmax := max(m, n). 4.1. Reducing dρ to aggregated n-gram statistics. Recall that X dρ (S, T ) = ρn θn (S, T ), n≥1
where θn (S, T ) = θ([S]n , [T ]n ). For each n ≥ 1, define the aggregated quantities X (2) An (S) := ∥[S]n ∥2 = c(S, W )2 , W ∈Σn
An (T ) := ∥[T ]n ∥2 =
X
c(T, W )2 ,
W ∈Σn
(3)
Bn (S, T ) := [S]n · [T ]n =
X
c(S, W )c(T, W ).
W ∈Σn
Then for n ≤ Lmax we have ! B (S, T ) n arccos p , An (S)An (T ) ̸= 0, An (S)An (T ) (4) θn (S, T ) = 0, An (S) = An (T ) = 0, π , otherwise. 2 Moreover, θn (S, T) = 0 for n > Lmax . Thus computing dρ (S, T ) reduces to computing the sequences An (S) 1≤n≤Lmax , An (T ) 1≤n≤Lmax , and Bn (S, T ) 1≤n≤Lmax . 4.2. Generalized suffix trees. We now explain how to compute the quantities in (2)–(3) in time linear in m + n, using a generalized suffix tree (or, equivalently, a suffix array with LCP-interval processing). Let #, $ ∈ / Σ be two fresh terminal symbols, and set U := S#T $. A generalized suffix tree for S and T is a suffix tree for U in which each leaf is labeled according to whether its suffix begins in the S-block or the T -block. We write depth(v) for the string depth of a node v, i.e. the length of the path label from the root to v. For a node v, define occS (v) := #{leaves in the subtree of v whose suffix begins in S}, occT (v) := #{leaves in the subtree of v whose suffix begins in T }. By standard suffix-tree properties, if a string W ∈ Σ+ labels the path to a point on the edge into v (equivalently, W contains neither # nor $), then c(S, W ) = occS (v) and c(T, W ) = occT (v). In other words, along a single edge, all sentinel-free substrings represented by points on that edge have the same occurrence counts in S and in T . This observation yields a compact formula for the aggregated n-gram statistics.
A WEIGHTED ANGLE DISTANCE ON STRINGS
7
Proposition 4.1. Let S, T ∈ Σ∗ , let U = S#T $, and let T be the generalized suffix tree of U . For each non-root node v of T , let ℓ− v := depth(parent(v)) + 1. denote the largest integer d ≤ depth(v) such that the length-d prefix of the path label Let ℓ+ v d to v lies in Σ (i.e. contains neither # nor $). (If the path label to v contains a sentinel, then ℓ+ v < depth(v).) Then for every integer n ≥ 1, X An (S) = 1ℓ−v ≤n≤ℓ+v occS (v)2 , v̸=root
An (T ) =
X
1ℓ−v ≤n≤ℓ+v occT (v)2 ,
v̸=root
Bn (S, T ) =
X
1ℓ−v ≤n≤ℓ+v occS (v)occT (v).
v̸=root − Nodes with ℓ+ v < ℓv contribute nothing.
Proof. The distinct substrings of U are in bijection with the integer depths of the non-root points on edges of the suffix tree. For a fixed non-root node v, the edge from parent(v) to v + contributes exactly one distinct substring of length n for each integer n with ℓ− v ≤ n ≤ ℓv , namely the prefix of the edge label of length n − depth(parent(v)) appended to the path label of parent(v). Every such substring has multiplicity occS (v) in S and occT (v) in T . Summing c(S, W )2 , c(T, W )2 , and c(S, W ) c(T, W ) over all distinct W ∈ Σn gives the stated formulas. □ 4.3. A linear-time algorithm. Proposition 4.1 suggests a simple range-add implementation. We are ultimately interested only in substrings over Σ. Accordingly, when we speak of a node v and the substrings it represents, we implicitly restrict our attention to those nodes for which every label on the root-v path lies in Σ (i.e. no symbol # or $ appears). Nodes whose path label crosses a sentinel will be ignored in the sums below. If either S or T is empty, then dρ (S, T ) may be computed directly from |S| and |T | using Lemma 7.5 below. Throughout the remainder of this section, we assume S and T are both nonempty. Algorithm 4.2. (1) Build the generalized suffix tree T of U = S#T $. (2) Compute occS (v) and occT (v) for all nodes v by a single post-order traversal: at a leaf, set (occS , occT ) = (1, 0) or (0, 1) depending on its origin, and at an internal node sum the counts of its children. (3) Initialize three difference arrays of length Lmax + 2: DS , DT , DST ∈ RLmax +2 . For each non-root node v whose path label lies in Σ∗ , compute av := occS (v)2 ,
bv := occT (v)2 ,
cv := occS (v)occT (v),
and perform the range additions DS [ℓ− v ] += av ,
DS [ℓ+ v + 1] −= av ,
DT [ℓ− v ] += bv ,
DT [ℓ+ v + 1] −= bv ,
DST [ℓ− v ] += cv ,
DST [ℓ+ v + 1] −= cv ,
ignoring any indices greater than Lmax + 1.
8
GRANT MOLNAR
(4) Convert the difference arrays to prefix sums to obtain An (S), An (T ), Bn (S, T )
(1 ≤ n ≤ Lmax ).
(5) Compute θn (S, T ) from (4) for 1 ≤ n ≤ Lmax and finally evaluate dρ (S, T ) =
L max X
ρn θn (S, T ).
n=1
Proposition 4.3. The algorithm above computes dρ (S, T ) correctly. Moreover, assuming a linear-time suffix-tree (or suffix-array) construction, the total running time is O(m + n) and the memory usage is O(m + n). Proof. Correctness follows from Proposition 4.1 and (4). The post-order computation of (occS , occT ) is linear in the size of T , and the range-add pass performs O(1) work per node. Since a generalized suffix tree for two strings has size O(m+n), the stated bounds follow. □ Remark 4.4. The algorithm above may be implemented purely with suffix arrays. One builds the suffix array of U = S#T $ and its LCP array, then constructs the LCP-interval tree, which is isomorphic (as a compact trie of all suffixes) to the internal-node structure of the suffix tree. The leaf-origin labels and the post-order aggregation of (occS , occT ) are then carried out on this interval tree, and the same range-add formulas apply. The same approach yields a fast method for computing dρ (S, ϵ) and for computing all θk (S, T ) simultaneously. In particular, the computation time does not depend on |Σ|n , avoiding the exponential blow-up inherent in explicit n-gram vector construction. 5. Experiments This section evaluates the ρ-weighted angle distance dρ as a string metric for stutter-heavy data, i.e. datasets where examples often differ by tandem-repeat expansions together with mild local variation. Our goal is not to “tune for wins” on a carefully curated benchmark, but to probe the behavior of dρ under a fixed and label-blind clustering protocol, and to compare it against classical edit distances and common k-gram baselines. 5.1. Experimental philosophy. Two design constraints guided these experiments. • No post-hoc dataset curation. We intentionally did not curate datasets to make dρ look good. We focused on stutter-heavy datasets because stutter-resistance is the intended use-case, but within that scope we report results for every labeled dataset we downloaded and processed during this study. • Methodology fixed before runs. The methodology described in Section 5.4 was chosen before any experiments were run and then applied uniformly to all datasets and all metrics. We did not hand-adjust DBSCAN parameters, random seeds, or sampling settings. 5.2. Datasets. We evaluate clustering quality on three labeled datasets of strings drawn from public genomics repositories. Each dataset is normalized into a uniform three-column schema (label, sample id, sequence), so that the clustering pipeline is agnostic to the data source and only depends on the string distance.
A WEIGHTED ANGLE DISTANCE ON STRINGS
9
• UCI splice-junction gene sequences (splice). This dataset is the UCI Machine Learning Repository “Molecular Biology (Splice-junction Gene Sequences)” corpus. Each sample is a fixed-length (60) DNA-like string with ambiguity codes, labeled by splice-site category (EI, IE, or N). We preserve the original instance identifier as sample id and export the normalized triples. • UCSC hg19 tandem repeats (ucsc trf). We extract tandem-repeat records from the UCSC Genome Browser database table simpleRepeat (hg19), which is derived from Tandem Repeats Finder (TRF) calls. Each record supplies a repeated “unit” (motif) along with its genomic interval. We treat the repeat unit as the class label and subsample motif classes to obtain a balanced labeled dataset; sample id encodes the genomic interval and metadata, and sequence is the repeated string. • NCBI STRSeq locus collections (strseq). We aggregate multiple STRSeq BioProjects from NCBI and download the associated FASTA records through the Entrez E-utilities API. Each record is labeled by locus (e.g., D8S1179, vWA, FGA, etc.), yielding a multi-class dataset with substantial tandem-repeat structure. 5.3. Distances compared. We compare dρ to standard edit-based and k-gram baselines. All distances are computed on raw strings. • Weighted angle distance (dρ ). We evaluate dρ for ρ ∈ {0.1, 0.2, . . . , 1.0}, truncating the sum at max n=60 (which is exact whenever both strings have length ≤ 60 and otherwise is a controlled approximation for ρ < 1). • Fixed-scale k-gram cosine angle. For k ∈ {3, 4, 5, 6} we compute the cosine angle between the k-gram count vectors (this is exactly the θk term of our construction). • k-gram Jensen–Shannon distance. For k ∈ {3, 4, 5, 6} we compute the Jensen– Shannon distance between empirical k-gram distributions. • Edit-distance baselines. We include Levenshtein distance, Damerau–Levenshtein distance, and the LCS distance (rapidfuzz.distance.LCSseq). 5.4. Methodology. For each dataset and each distance d(·, ·) we compute the full pairwise distance matrix Dij := d(xi , xj ) (1 ≤ i, j ≤ N ), and run DBSCAN with metric="precomputed". We tune eps and min samples using Optuna (TPE sampler) for n trials=100. The objective is the silhouette score computed on non-noise points (DBSCAN noise label -1 is removed before silhouette is evaluated). If DBSCAN produces fewer than two non-noise clusters, the silhouette is defined to be −1 to prevent degenerate solutions from being selected. Remark 5.1. We made the decision to tune to the silhouette score because it is available without labels, is inexpensive once D is computed, and it provides a consistent tuning criterion across all datasets and metrics. We emphasize that silhouette is not assumed to correlate perfectly with ground-truth clustering quality; it is used only as a practical, labelfree model-selection heuristic. To avoid dataset-specific hand-tuning of the eps scale, we restrict the search range using quantiles of the observed pairwise distance distribution. Concretely, let D be the multiset of upper-triangular entries of D. We set h i eps ∈ Quantile0.02 (D), Quantile0.20 (D) , with standard numeric guards when the interval degenerates. We search min samples ∈ {3, 5, 8, 13}.
10
GRANT MOLNAR
The selected hyperparameters are the Optuna best trial parameters, and the final DBSCAN labeling is obtained by rerunning DBSCAN with those parameters. After selecting DBSCAN parameters using silhouette alone, we evaluate the resulting clustering against the provided dataset labels using: • Adjusted Rand Index (ARI) and • Normalized Mutual Information (NMI). Noise points (DBSCAN label -1) are treated as an additional cluster label for ARI/NMI computation so that all sampled points are evaluated under a single partition. In addition to ARI/NMI, we record diagnostic quantities including the selected (eps, min samples), the achieved silhouette score (on non-noise points), the number of non-noise clusters, and the fraction of points labeled as noise. All per-run outputs are written to results.csv and corresponding plots are saved for each (dataset, distance) pair. The full experimental pipeline—distance implementations, dataset ingestion, DBSCAN/Optuna harness, and figure generation—is available at [11]. 5.5. Analysis. Table 1 reports, for each dataset, the best ARI/NMI achieved by each distance family (maximizing over its parameter sweep). The main qualitative patterns are: • splice: no method clusters well. All distances collapse to a single dominant cluster and achieve essentially zero ARI/NMI (best ARI ≈ 0.0003). See also the flat weighted-angle sweep in Figure 3. • strseq: edit distances dominate. LCS achieves ARI = 0.8825 and NMI = 0.8970, with the other two edit baselines close behind. The weighted angle distance is competitive with the k-gram baselines (best at ρ = 0.6 with ARI = 0.5060, NMI = 0.7527), but it does not outperform classical edit distances on this dataset. Figure 6 shows a clear “sweet spot” around ρ ∈ [0.5, 0.7]. • ucsc trf: weighted angle dominates. Here the weighted angle distance is the strongest method overall (best ARI at ρ = 0.6: ARI = 0.4596, NMI = 0.8632), while edit distances fail catastrophically (ARI ≈ 0, NMI ≈ 0.02). This is the cleanest evidence in our suite that the weighted angle construction captures repeat-driven structure that is largely invisible to generic edit distances. The ρ-sweep in Figure 9 is stable over a broad plateau, with best NMI attained at ρ = 1.0. These rankings agree with the per-distance “best-to-worst” listings in our run summary. Remark 5.2. The experiments above emphasize clustering quality rather than speed. In our current reference implementation [11], weighted angle distance computations are substantially slower than the baselines, despite being linear-time per pair in principle: the bottleneck is Python-level overhead combined with the need to compute O(N 2 ) pairwise distances for DBSCAN, with no caching across parameter sweeps and no parallelism. We therefore report timing only as a coarse reference (Table 4) and view performance optimization (vectorization, memoization of repeated trigonometric calls, and parallel distance-matrix construction) as future work. Table 2 summarizes how sensitive the weighted angle method is to ρ. Across our three datasets, the choice ρ = 0.6 maximizes ARI in all cases, while ρ = 1.0 slightly improves NMI on ucsc trf. The variability across ρ is largest on strseq (where the task is “easier” for edit distances and weighted angle competes with them), and smallest on ucsc trf (where many ρ values fall on the same high-performing plateau).
A WEIGHTED ANGLE DISTANCE ON STRINGS
11
ARI and NMI are highly consistent as rankings of distances (Table 3), with Spearman correlations above 0.93 for every dataset. By contrast, silhouette has weak (and sometimes negative) rank correlation with ARI/NMI, most notably on strseq. This is an expected consequence of our label-blind DBSCAN tuning: silhouette is used only to choose (ε, min samples) within each distance, and it should be interpreted as an internal “cluster compactness” diagnostic rather than a proxy for label recovery. The scatter in Figure 10 illustrates this mismatch concretely. DBSCAN noise points are a key “escape valve” for distances that induce highly nonuniform neighborhoods. Figure 13 plots ARI against the noise fraction across all tested distances on ucsc trf. On that dataset, high-performing methods achieve good ARI without labeling an extreme fraction of points as noise; on strseq the best weighted-angle setting (ρ = 0.6) yields a noticeably larger noise fraction than edit distances, suggesting a tradeoff between repeat-sensitivity and conservative cluster formation. 6. Conclusion We introduced the ρ-weighted angle distance dρ , a multi-scale metric on Σ∗ obtained by comparing all n-gram count profiles of two strings through angular discrepancies and aggregating these discrepancies with an exponential weight. The resulting geometry is “cosinelike” at every scale and is deliberately designed to be insensitive to repetition magnitude: stutters and changes in motif multiplicity are treated as controlled perturbations rather than as large edit costs. Along the way we established several structural properties: dρ is a genuine metric for every ρ > 0, it has a rigid and explicitly described isometry group, and for 0 < ρ < 1 it admits a nontrivial completion that naturally incorporates shift-invariant probability measures on one-sided infinite strings. This completion viewpoint clarifies that dρ can be interpreted as a metric on empirical and limiting n-gram distributions, not merely as a distance between finite words. From a computational standpoint, we showed that dρ (S, T ) can be computed in O(|S| + |T |) time using generalized suffix trees (or suffix arrays), by reducing the cross-scale dot products and squared norms to aggregates over internal nodes. This makes dρ viable as a primitive for large-scale sequence comparison in principle, though the end-to-end runtime in our current Python reference implementation remains dominated by engineering choices in the surrounding pipeline. In particular, the DBSCAN experiments in Section 5 require constructing full pairwise distance matrices; our implementation does not currently cache repeated computations across parameter sweeps, vectorize the trigonometric calculations, or exploit parallelism. Consequently, the reported wall-clock times should be read as a baseline for a straightforward prototype rather than as an intrinsic limitation of the methodology. Empirically, the experiments suggest the following picture. On datasets whose class structure is driven primarily by tandem-repeat statistics, weighted angle distances can substantially outperform classical edit distances and fixed-scale k-gram baselines, and performance is reasonably stable across a broad range of ρ. On more conventional sequence corpora, edit distances may remain the best choice, and in some settings (such as splice in our suite) DBSCAN itself appears to be a poor model of the ground-truth labeling regardless of the underlying distance. Overall, the weighted angle construction seems most valuable when repetition scale should be discounted but repetition structure should still matter. Several directions look immediately promising. On the algorithmic side, a performant implementation could combine (i) suffix-array based computation of the required aggregates, (ii) memoization of repeated subexpressions across ρ, and (iii) parallel construction of distance matrices or approximate neighborhood queries. On the modeling side, one can consider alternative weighting schemes (beyond geometric weights) to emphasize a chosen range of
12
GRANT MOLNAR
n-gram scales, or learn such weights from unlabeled data. Finally, the completion theorem hints at a broader viewpoint in which dρ is a metric on objects closer to symbolic dynamical systems than to isolated strings; exploiting this structure for tasks such as classification, anomaly detection, or retrieval is an appealing target for future work. 7. Appendix: Geometry In this appendix, we conduct a more careful analysis of the mathematical properties of dρ . We begin with a proof of Proposition 2.8, which we restate here for convenience. Proposition 7.1 (Proposition 2.8). For any ρ > 0, the map dρ : Σ∗ × Σ∗ → R≥0 is a metric. Proof. Symmetry and the triangle inequality both inherit from the pseudometricity of θ, as does the triviality dρ (S, S) = 0 for each S ∈ Σ∗ . It suffices to show that if dρ (S, T ) = 0 then S = T. Let S, T ∈ Σ∗ be arbitrary. Note that dρ (S, T ) = 0 if and only if θ([S]n , [T ]n ) = 0 for all n. If |S| > |T | then letting m = |S| we have θ([S]m , [T ]m ) = π/2 so dρ (S, T ) ̸= 0. Suppose now that dρ (S, T ) = 0. We must have |S| = |T | = m for some m. Then θ([S]m , [T ]m ) = 0, but [S]m = { S : 1 } and [T ]m = { T : 1 }, so S = T as desired. □ Remark 7.2. The proof of Proposition 7.1 in fact shows that dρ is a metric on Σ∗ for every ρ > 0. For each fixed ρ > 0 the induced topology on Σ∗ is discrete (see Proposition 7.9), but when ρ ∈ (0, 1) the metric is still topologically interesting (see Theorem 7.18), and is ρ uniformly bounded by π2 · 1−ρ . We therefore restrict attention to ρ ∈ (0, 1) in the main text. From now on, unless explicitly stated otherwise, we assume ρ ∈ (0, 1). 7.1. Respecting edits. In this subsection, we prove that dρ is well-behaved under insertion, deletion, substitution, and stutter. Our first theorem controls the behavior of dρ under insertions, deletions, and substitutions. Theorem 7.3. Let ρ ∈ (0, 1). Let P, Q ∈ Σ∗ be strings of lengths m and n respectively, and let a, b ∈ Σ be arbitrary. Then √ π ρKedit +1 π Ledit +1 π 2 AMedit (ρ) + · (5) dρ (P aQ, P Q) ≤ √ + ρ 2 1−ρ 2 Ledit and π π ρKedit +1 (6) dρ (P aQ, P bQ) ≤ √ AMedit (ρ) + · , 2 1−ρ Ledit where Ledit := m + n, Kedit := ⌊Ledit /2⌋, Medit := min(m + 1, n + 1), and ∞ X ρ 1 − (M + 1)ρM + M ρM +1 M ρM +1 k := (7) AM (ρ) ρ min(k, M ) = + . (1 − ρ)2 1−ρ k=1 Proof. If x, y ∈ RN are nonzero vectors, then the Cauchy-Schwarz inequality implies ∥x − y∥ ∥x − y∥ (8) θ(x, y) ≤ 2 arcsin min 1, ≤π· . 2 min (∥x∥ , ∥y∥) 2 min(∥x∥ , ∥y∥) Now let ρ ∈ (0, 1), let P, Q ∈ Σ∗ be strings of lengths m and n respectively, and let a, b ∈ Σ be arbitrary, and let Ledit , Kedit , and Medit be as above. We proceed to prove (5) by comparing P Q with P aQ. For k ≤ Ledit , only k-grams that cross the junction between P and Q are removed, and only k-grams that include the inserted a are added. We define (9)
ck := max (0, min(m, k − 1) − max(1, k − n) + 1)
A WEIGHTED ANGLE DISTANCE ON STRINGS
13
to be the number of k-length windows in P Q that cross from P to Q, and define (10)
dk := max (0, min(m, k − 1) − max(0, k − n − 1) + 1)
to be the number of k-length windows in P aQ that include the new a. If m, n ≥ k, these equations simplify to ck = k − 1 and dk = k. Each of the ck removed windows decreases one coordinate of [P Q]k by 1, and each of the dk new windows increases one coordinate by 1. By the triangle inequality, ∥[P aQ]k − [P Q]k ∥ ≤ ck + dk .
(11)
Also θLedit +1 (P aQ, P Q) = π2 . Since [P Q]k has nonnegative integer entries summing to Ledit − √ √ k + 1, we have ∥[P Q]k ∥ ≥ Ledit − k + 1, and similarly ∥[P aQ]k ∥ ≥ Ledit − k + 1. Hence, by (8), ck + d k θk (P aQ, P Q) ≤ π · √ (k ≤ Ledit ). 2 Ledit − k + 1 Therefore X π ck + d k + ρLedit +1 . (12) dρ (P aQ, P Q) ≤ ρk · π √ 2 Ledit − k + 1 2 1≤k≤L edit
For k ≤ Kedit we have Ledit − k + 1 ≥ Ledit /2, hence ck + d k π π √ ≤√ (ck + dk ). 2Ledit 2 Ledit − k + 1 For k > Kedit we use θk (P aQ, P Q) ≤ π/2. Thus X π dρ (P aQ, P Q) ≤ √ 2Ledit 1≤k≤K
∞ π X π ρ (ck + dk ) + ρk + ρLedit +1 . 2 k=K +1 2 k
edit
edit
For k ≤ Kedit , we have ck + dk ≤ 2 min(k, Medit ), so X 1≤k≤Kedit
ρk (ck + dk ) ≤ 2
∞ X
ρk min(k, Medit ) = 2AMedit (ρ).
k=1
P∞
Substituting this and evaluating the tail k=Kedit +1 ρk yields (5). We now turn our attention to dρ (P aQ, P bQ). Define (13)
ek := max (0, min(m, Ledit − k + 1) − max(0, m − k + 1) + 1)
to be the number of length-k windows in the strings P aQ and P bQ that contain a or b respectively. Each such window changes one k-gram into another, so the difference vector is a sum of ek vectors of the form u − v, where u and v are standard basis vectors. Hence, by the triangle inequality, √ (14) ∥[P aQ]k − [P bQ]k ∥ ≤ 2 ek . Since [P aQ]k and [P bQ]k have √ nonnegative integer entries summing to Ledit − k + 2, we have min(∥[P aQ]k ∥ , ∥[P bQ]k ∥) ≥ Ledit − k + 2. Thus, by (8), √ 2 ek θk (P aQ, P bQ) ≤ π · √ (k ≤ Ledit + 1). 2 Ledit − k + 2 Therefore √ X 2 ek (15) dρ (P aQ, P bQ) ≤ ρk · π √ . 2 Ledit − k + 2 1≤k≤L +1 edit
14
GRANT MOLNAR
For k ≤ Kedit we have Ledit − k + 2 ≥ Ledit /2, so √ 2 ek π π √ ≤√ ek . Ledit 2 Ledit − k + 2 For k > Kedit we use θk (P aQ, P bQ) ≤ π/2. Hence X π dρ (P aQ, P bQ) ≤ √ Ledit 1≤k≤K
edit
∞ π X ρ ek + ρk . 2 k=K +1 k
edit
Since ek ≤ min(k, Medit ) for k ≤ Kedit , we obtain X
k
ρ ek ≤
1≤k≤Kedit
∞ X
ρk min(k, Medit ) = AMedit (ρ),
k=1
and evaluating the tail gives (6).
□
Our next theorem controls the behavior of dρ under stutter. Theorem 7.4. Let ρ ∈ (0, 1). Let P1 , P2 , Q ∈ Σ∗ be strings of lengths m1 , m2 and n respectively, and let ℓ be a positive integer. Then (16) π ρKstut +1 π ρLstut +1 (1 − ρr ) π ρ ℓ r + · + · , dρ (P1 QP2 , P1 Q P2 ) ≤ √ 3AMstut (ρ) + 1−ρ 2 1−ρ 2 1−ρ 2Lstut where Lstut := m1 + n + m2 , r := (ℓ − 1)n, Kstut := ⌊Lstut /2⌋, and Mstut := min(m1 + n + 1, m2 + 1). AM (ρ) is defined as in (7). Proof. Write U := P1 QP2 and V := P1 Qℓ P2 , and write p := m1 + n and q := m2 , so that |U | = p + q = Lstut and V is obtained from U by inserting the block B := Qℓ−1 of length r between the prefix of length p and the suffix of length q. Fix k ≤ Lstut . Define (17)
ck := max (0, min(p, k − 1) − max(1, k − q) + 1)
to be the number of length-k windows in U that cross the junction between the prefix of length p and the suffix of length q. Define (18)
dk := max (0, min(p + r, Lstut + r − k + 1) − max(1, p − k + 2) + 1)
to be the number of length-k windows in V that intersect the inserted block B. Only kgrams coming from these windows can change when passing from U to V . By the same triangle-inequality argument as in (11), we have (19)
∥[V ]k − [U ]k ∥ ≤ ck + dk .
Since [U ]k has nonnegative integer entries summing to Lstut − k + 1, we have ∥[U ]k ∥ ≥ √ Lstut − k + 1, and similarly for [V ]k . Therefore, by (8), for k ≤ Lstut we have ck + d k θk (U, V ) ≤ π · √ . 2 Lstut − k + 1 For k > Lstut , we have [U ]k = 0, while [V ]k ̸= 0 for k ≤ Lstut + r, so ( π if Lstut < k ≤ Lstut + r, θk (U, V ) = 2 0 ifk > Lstut + r.
A WEIGHTED ANGLE DISTANCE ON STRINGS
15
Hence X
dρ (U, V ) ≤
(20)
Lstut +r ck + d k π X ρ ·π √ + ρk . 2 Lstut − k + 1 2 k=L +1 k
1≤k≤Lstut
stut
Let Kstut = ⌊Lstut /2⌋. For k ≤ Kstut we have Lstut − k + 1 ≥ Lstut /2, so ck + d k π π √ ≤√ (ck + dk ). 2Lstut 2 Lstut − k + 1 Moreover, ck ≤ min(k, Mstut ),
dk ≤ r + 2 min(k, Mstut ),
so ck + dk ≤ r + 3 min(k, Mstut )
(21)
(k ≤ Kstut ).
Therefore K stut X
K stut X
ρ + 3AMstut (ρ). 1 − ρ k=1 k=1 1≤k≤Kstut P k Bounding the remaining k > Kstut part of the first sum in (20) by π2 ∞ k=Kstut +1 ρ and evaluating the geometric tails yields (16). □ X
ρk (ck + dk ) ≤ r
ρk + 3
ρk min(k, Mstut ) ≤ r
7.2. Topology. In this subsection, we describe the topology induced on Σ∗ by dρ . We first note that we can recover |S| from dρ . Lemma 7.5. Let ρ > 0. For any S ∈ Σ∗ , we have 2(1−ρ)d (S,ϵ) ρ log 1− πρ log ρ |S| = 2 d (S, ϵ) π ρ
if ρ ̸= 1, if ρ = 1.
Proof. Let S ∈ Σ∗ , and write n = |S|. We have n
πX k ρ , dρ (S, ϵ) = 2 k=1 which sums as a geometric series if ρ ̸= 1. Rearranging, we obtain the desired result.
□
We can also recover the local angular distances from dρ . Proposition 7.6. Let ρ > 0, and let n ≥ 1. For any S, T ∈ Σ∗ , there is an explicit recursive formula expressing θn (S, T ) in terms of the finite set of distances {dρ (S, W ), dρ (T, W ) : W ∈ Σ≤n .} Consequently, the collection of functions (θn )n≥1 is determined by dρ . Proof. Let ρ > 0. We proceed by induction on n. Note that for any S, and for W of length n, we have X X [S]n = c(S, W )[W ]n = ∥[S]n ∥ cos θn (S, W )[W ]n . W ∈Σn
W ∈Σn
∗
Thus for any S, T ∈ Σ we have ! θn (S, T ) = arccos
X W ∈Σn
cos θn (S, W ) cos θn (T, W )
16
GRANT MOLNAR
It therefore suffices to evaluate θn (S, W ) for W of length n. Suppose now that we have performed such an evaluation for all k < n. The evaluation set is empty when n = 1, giving the base case. We may write P P dρ (S, W ) − k<n ρk θk (S, W ) − π2 n<k≤|S| ρk θn (S, W ) = ρn P dρ (S, W ) − k<n ρk θk (S, W ) − max (0, dρ (ϵ, S) − dρ (ϵ, W )) = , ρn and our claim follows. □ Remark 7.7. The proof gives an explicit algorithm: knowing dρ , one first recovers lengths via dρ (ϵ, ·), then computes θ1 , then θ2 , and so on. Example 7.8. For n = 1, S, T ∈ Σ∗ nonempty, and a ∈ Σ, Proposition 7.6 gives us the following decompositions of θ1 (S, a) and θ1 (S, T ): dρ (S, a) − dρ (ϵ, S) − π2 ρ , θ1 (S, a) = ρ ! π X dρ (S, a) − dρ (ϵ, S) − π ρ d (T, a) − d (ϵ, T ) − ρ ρ ρ 2 2 θ1 (S, T ) = arccos . 2 ρ a∈Σ It turns out that dρ induces the discrete topology on Σ∗ . For the following proposition, we relax the condition ρ ∈ (0, 1). Proposition 7.9. Let ρ > 0. For every S ∈ Σ∗ there exists δ(S, ρ) > 0 such that T ̸= S implies dρ (S, T ) ≥ δ(S, ρ). In particular, the metric space (Σ∗ , dρ ) has the discrete topology: for each S the open ball Bδ(S,ρ)/2 (S) equals {S}. Proof. We consider three cases according to the length of T . If |T | < |S|, then [T ]|S| = 0 while [S]|S| has a single nonzero coordinate, so θ|S| (S, T ) = π2 and π dρ (S, T ) ≥ ρ|S| . 2 |S| If |T | = |S| and T ̸= S, then [S]|S| and [T ]|S| are distinct standard basis vectors in RΣ , hence orthogonal. Thus again θ|S| (S, T ) = π2 and π dρ (S, T ) ≥ ρ|S| . 2 If |T | > |S|, then [S]|S|+1 = 0 while [T ]|S|+1 ̸= 0, so θ|S|+1 (S, T ) = π2 and π dρ (S, T ) ≥ ρ|S|+1 . 2 In all cases π dρ (S, T ) ≥ min ρ|S| , ρ|S|+1 =: δ(S, ρ) > 0, 2 and the claim follows. □ Remark 7.10. When ρ ≥ 1, the proof of Proposition 7.9 implies that dρ is uniformly discrete, and in fact that Bπ/2 (S) equals {S} for any S ∈ Σ∗ . Proposition 7.9 is not the full story, however: the topology induced by ρ is only uniformly discrete when ρ ≥ 1. When 0 < ρ < 1, Σ∗ has a nontrivial completion.
A WEIGHTED ANGLE DISTANCE ON STRINGS
17
Definition 7.11. Let Σ be a finite alphabet and let ΣN be the one-sided full shift, equipped with the product topology, and let τ : x1 x2 · · · 7→ x2 x3 . . . be the left shift. (See [8, Chapter 1] for the standard shift-space topology, and [17, §1.1] for the one-sided Kolmogorov/measuretheoretic viewpoint; in particular, cylinder sets generate the Borel σ-algebra.) A shift-invariant Borel probability measure on ΣN is a Borel probability measure µ such that µ ◦ τ −1 = µ. We write Mτ (ΣN ) for the set of such measures. For n ≥ 1 and W ∈ Σn , define the cylinder set Cyl(W ) := {x ∈ ΣN : x1 x2 · · · xn = W }, and the length-n cylinder marginal pµn (W ) := µ(Cyl(W )). Shift-invariant measures are a natural receptacle for limiting n-gram statistics. A finite string can be viewed as a short sample from a symbolic process, while a shift-invariant measure records the translation-stable distribution of all finite blocks. In particular, for µ ∈ Mτ (ΣN ) the marginals satisfy the consistency relations X µ X µ pn+1 (aW ) = pµn (W ), pn+1 (W a) = pµn (W ) and a∈Σ
a∈Σ
where the first identity is just disjoint union of cylinders, F and the second follows from −1 −1 µ(Cyl(W )) = µ(τ Cyl(W )) together with τ Cyl(W ) = a∈Σ Cyl(aW ) (see [17, §1.1]). We now describe a common extension of dρ to both finite strings and shift-invariant measures. Definition 7.12. Fix ρ ∈ (0, 1). For any finite string S of length L and any n ≥ 1, define its empirical length-n block distribution by c(S, W ) , L ≥ n, S pn (W ) := L − n + 1 (W ∈ Σn ), 0, L < n, n
and let un (S) be the L2 -normalization of the vector pSn ∈ RΣ ≥0 when it is nonzero, with the convention un (S) = 0 otherwise. For µ ∈ Mτ (ΣN ), define pµn (W ) := µ(Cyl(W )),
un (µ) :=
pµn . ∥pµn ∥2
(Note that pµn is a probability vector, hence nonzero for every n ≥ 1.) For X, Y ∈ Σ∗ ⊔ Mτ (ΣN ) and n ≥ 1, define arccos(⟨un (X), un (Y )⟩) , un (X), un (Y ) ̸= 0, un (X) = un (Y ) = 0, θn (X, Y ) := 0, π , exactly one of un (X), un (Y ) is 0, 2 and set ∞ X b dρ (X, Y ) := ρn θn (X, Y ). n=1
The next lemma explains why this really extends the finite-string construction.
18
GRANT MOLNAR
Lemma 7.13. For a finite string S of length m ≥ n we have [S]n . m−n+1 In particular, un (S) agrees with the L2 -normalization of [S]n , and for finite strings S, T the angle θn (S, T ) from Definition 7.12 coincides with the n-gram angle used in Definition 2.6. Consequently, for S, T ∈ Σ∗ , dbρ (S, T ) = dρ (S, T ). pSn =
Proof. If m ≥ n, then the number of length-n windows in S is m − n + 1, and each such window contributes one to the appropriate coordinate in [S]n . Thus X X 1 pSn (W ) = c(S, W ) = 1, m − n + 1 n W ∈Σ W so pSn is exactly the normalized count vector. The L2 -normalization is therefore the same in both constructions, and the definitions of θn coincide on finite strings. Summing with weights ρn yields the final claim. □ Lemma 7.14. The function dbρ is a metric on Σ∗ ⊔ Mτ (ΣN ). n
Proof. Fix n. On the set {0} ∪ S(RΣ ) (unit sphere plus an extra point 0), the rule defining θn is a metric: it is the spherical metric on the unit sphere, with the extra point 0 placed at distance π/2 from every unit vector and distance 0 from itself. Therefore θn is a metric on the P disjoint union Σ∗ ⊔ Mτ (ΣN ) when composed with un (·). The weighted sum dbρ = n≥1 ρn θn is therefore a metric provided it separates points. Separation for finite–finite follows from Lemma 7.13 and Proposition 7.1. Separation for measure–measure: if dbρ (µ, ν) = 0, then θn (µ, ν) = 0 for all n, hence un (µ) = un (ν) for all n. Since pµn and pνn are probability vectors, un (µ) = un (ν) implies pµn = pνn for all n (because p = u/∥u∥1 on the nonnegative orthant). Cylinder sets generate the Borel σ-algebra, so µ = ν (see [17, §1.1]). Separation for mixed pairs: if S has length L and µ ∈ Mτ (ΣN ), then un (S) = 0 for all n > L while un (µ) ̸= 0 for all n, so θn (S, µ) = π/2 for every n > L and πX n dbρ (S, µ) ≥ ρ > 0. 2 n>L □ Lemma 7.15. Let (Xj )j≥1 be a dbρ -Cauchy sequence in Σ∗ ⊔ Mτ (ΣN ). Then for each fixed n the sequence (Xj ) is θn -Cauchy, and the vectors un (Xj ) form a Cauchy sequence in {0} ∪ n S(RΣ ). Proof. For any i, j and any n we have ρn θn (Xi , Xj ) ≤ dbρ (Xi , Xj ). Since the right-hand side tends to 0 as i, j → ∞, we have θn (Xi , Xj ) → 0 for each n, i.e. n (un (Xj )) is Cauchy in the metric space {0} ∪ S(RΣ ). □ Lemma 7.16. Let (Xj ) be dbρ -Cauchy. (1) If infinitely many Xj are finite strings and their lengths are bounded, then (Xj ) is eventually constant, and hence converges to a finite string. (2) Otherwise, there exists µ ∈ Mτ (ΣN ) such that dbρ (Xj , µ) → 0.
A WEIGHTED ANGLE DISTANCE ON STRINGS
19
Proof. (1) If |Xj | takes only finitely many values and infinitely many Xj are strings, then there are only finitely many possible strings among those terms. A Cauchy sequence in a finite metric space must be eventually constant. (2) We may therefore assume that either Xj are measures for all large j, or that Xj are finite strings with |Xj | → ∞. n Fix n ≥ 1. By Lemma 7.15 the sequence un (Xj ) converges in {0} ∪ S(RΣ ). In our present case, for each fixed n we eventually have |Xj | ≥ n (if Xj are strings) or Xj ∈ Mτ (if they are measures), hence un (Xj ) ̸= 0 for all large j. Therefore the limit lies in the unit sphere; write it as u∞ n . Define probability vectors on Σn by u∞ n (W ) , ∞ U ∈Σn un (U )
pn (W ) := P
W ∈ Σn .
∞ Since u∞ n ≥ 0 and ∥un ∥2 = 1, the denominator is positive. Moreover, the map u 7→ u/∥u∥1 is continuous on the nonnegative unit sphere, so
pnXj =
un (Xj ) −→ pn ∥un (Xj )∥1
for each fixed n. P We claimP that (pn )n≥1 satisfies the Kolmogorov consistency relations, i.e. a pn+1 (W a) = pn (W ) and a pn+1 (aW ) = pn (W ). For Xj ∈ Mτ these equalities hold exactly (as discussed after Definition 7.11), so they pass to the limit immediately. For Xj a finite string S of length L ≥ n + 1, the corresponding empirical distributions satisfy the approximate identities X X 1 1 pSn+1 (W a) − pSn (W ) ≤ , pSn+1 (aW ) − pSn (W ) ≤ , L − n + 1 L − n + 1 a∈Σ a∈Σ because the (n + 1)-windows whose prefix is W account for all n-windows equal to W except possibly the last one, and similarly for suffixes (a boundary-term estimate). Since |Xj | → ∞ in the string case, the error tends to 0 with j, and passing to the limit gives the exact consistency relations for (pn ). By the Kolmogorov extension theorem (see [17, Theorem 1.1.2]), there is a unique Borel probability measure µ on ΣN such that µ(Cyl(W )) = pn (W ) for all n and all W ∈ Σn . The second consistency relation is exactly the stationarity (shift-invariance) condition for the one-sided Kolmogorov model (see [17, §1.1]), hence µ ∈ Mτ (ΣN ). Finally, by construction un (µ) = u∞ θn (Xj , µ) → 0 for each fixed n. Since n for each P n, so π n 0 ≤ θn ≤ π/2, given ε > 0 choose N with 2 n>N ρ < ε/2, and then choose j large enough P that n≤N ρn θn (Xj , µ) < ε/2. This yields dbρ (Xj , µ) < ε, proving dbρ (Xj , µ) → 0. □ Lemma 7.17. For every µ ∈ Mτ (ΣN ) and every ε > 0, there exists a finite string S ∈ Σ∗ such that dbρ (S, µ) < ε. Proof. Fix µ and ε > 0. Choose N such that πX n ε ρ < . 2 n>N 2 It suffices to construct S so that θn (S, µ) is small for each 1 ≤ n ≤ N . Consider the de Bruijn digraph GN with vertex set ΣN −1 and edge set ΣN , where an edge W = w1 · · · wN goes from the prefix w1 · · · wN −1 to the suffix w2 · · · wN . The vector pµN is a
20
GRANT MOLNAR
nonnegative circulation on GN : for each vertex V ∈ ΣN −1 , shift-invariance implies X µ X µ pN (V a) = pµN −1 (V ) = pN (aV ). a∈Σ
a∈Σ
Decompose this circulation into directed cycles with nonnegative coefficients (a standard flow decomposition: iteratively follow edges of positive weight until a directed cycle appears, subtract the minimum weight on that cycle, and repeat). Approximating the finitely many cycle coefficients by rationals yields a rational circulation qN on ΣN that is arbitrarily close to pµN in ℓ2 , and still satisfies the same balance equations (hence both consistency relations). Choose a common denominator M so that Q(W ) := M qN (W ) ∈ N for all W ∈ ΣN . Build the directed multigraph with Q(W ) parallel edges labeled by W as above. Balance of qN implies that every vertex has indegree equal to outdegree, so the multigraph has an Eulerian cycle. Reading symbols along such a cycle produces a finite string S0 of length M + N − 1 whose length-N empirical block distribution is exactly qN , i.e. pSN0 = qN . Now take S := S0k (concatenate k copies) with k large. For each 1 ≤ n ≤ N , the boundaryterm estimates used in the proof of Lemma 7.16 show that pSn is within O(1/k) (in ℓ1 , hence in ℓ2 ) of the corresponding stationary marginal of qN , and therefore (by choosing qN close enough to pµN and then k large enough) we can ensure that pSn is arbitrarily close to pµn for every 1 ≤ n ≤ N . Since the map p 7→ p/∥p∥2 is continuous on the probability simplex (and ∥p∥2 ≥ |Σ|−n/2 ), closeness of pSn to pµn implies θn (S, µ) is as small as we like for 1 ≤ n ≤ N . Hence P n n≤N ρ θn (S, µ) < ε/2, and the tail n > N contributes at most ε/2 by the choice of N . Therefore dbρ (S, µ) < ε. □ Theorem 7.18 (Completion of Σ∗ ). Let ρ ∈ (0, 1), and let dbρ be as in Definition 7.12. Then: (1) dbρ is a metric on Σ∗ ⊔ Mτ (ΣN ). (2) The restriction of dbρ to Σ∗ equals dρ . (3) The metric space Σ∗ ⊔ Mτ (ΣN ), dbρ is complete, and Σ∗ is dense in it. Consequently, the completion of Σ∗ , dρ is naturally identified with the disjoint union Σ∗ ⊔ Mτ (ΣN ) equipped with dbρ . Proof. (1) is Lemma 7.14. (2) is Lemma 7.13. Completeness and existence of limits follow from Lemmas 7.15 and 7.16, and density is Lemma 7.17; together these give (3). The final identification with the metric completion follows from the universal property of completions. □ Note that the completion of Σ∗ is independent of our choice of ρ. This is not a coincidence. Theorem 7.19. Let 1 > σ > ρ > 0. The identity map is a uniform homeomorphism from (Σ∗ , dσ ) to (Σ∗ , dρ ). Proof. For any S, T ∈ Σ∗ we have X X dσ (S, T ) = σ n θn (S, T ) ≥ ρn θn (S, T ) = dρ (S, T ), n≥1
n≥1
so the identity map from (Σ∗ , dσ ) to (Σ∗ , dρ ) is 1-Lipschitz.
A WEIGHTED ANGLE DISTANCE ON STRINGS
21
For the reverse direction, fix ϵ > 0. For any integer N ≥ 1, X X dσ (S, T ) = σ n θn (S, T ) + σ n θn (S, T ) 1≤n<N
n≥N
X σ π σN , ≤ dρ (S, T ) + · ρn 2 1−σ 1≤n<N n
N
σ since 0 ≤ θn ≤ π/2 on finite strings (all un are nonnegative). Choose N so that π2 1−σ < ϵ/2, and then choose ϵ δ< P . 2 1≤n<N (σ n /ρn ) Then dρ (S, T ) < δ implies dσ (S, T ) < ϵ, proving uniform continuity. The inverse is continuous as well, hence the identity is a uniform homeomorphism. □
Corollary 7.20. Let 1 > σ > ρ > 0. The identity underlying set Σ∗ ⊔ on the common N Mτ (Σ ) is a uniform homeomorphism between · , dbσ and · , dbρ . In particular, the induced identification between the two metric completions agrees with Theorem 7.18. Proof. The same estimates as in Theorem 7.19 apply verbatim because 0 ≤ θn ≤ π/2 on the entire disjoint union by definition. □ 7.3. Isometries. Fix ρ ∈ (0, 1). In this subsection, we characterize the isometries of dρ . Let π : Σ → Σ be a permutation, and extend the action of π to Σ∗ character-wise, so π(s1 . . . sn ) = π(s1 ) . . . π(sn ). The map π : Σ∗ → Σ∗ is visibly an isometry. Let R : Σ∗ → Σ∗ be the reversal map given by R(s1 . . . sn ) = sn . . . s1 . The reversal map is an isometry of Σ∗ that commutes with π. It is the goal of this section to prove that every isometry of Σ∗ is either a permutation or the product of a permutation and a reversal. Along the way, we prove three lemmas. Lemma 7.21. Let ρ ∈ (0, 1). Let ϕ : Σ∗ → Σ∗ be an isometry. Then ϕ(ϵ) = ϵ. Proof. For any X ∈ Σ∗ , consider the set of all distances from X: DX := {dρ (X, T ) : T ∈ Σ∗ }. Since ϕ is an isometry, we have Dϕ(X) = DX . We readily compute ( N ) πX k Dϵ = ρ : N ∈ Z≥0 , 2 k=1 ρ which is a strictly increasing sequence with unique accumulation point π2 · 1−ρ . N Now let S ̸= ϵ. Consider the sequence of strings S for N ≥ 1. Observe that [S N ]1 = N [S]1 , so θ1 (S, S N ) = 0. For every k ≥ 2, we trivially have θk (S, S N ) ≤ π/2. Hence X πX k π ρ2 ρk θk (S, S N ) ≤ ρ = · . dρ (S, S N ) = 2 k≥2 2 1−ρ k≥1 The bounded sequence dρ (S, S N ) N ≥1 therefore has an accumulation point no greater than ρ π · 1−ρ − π2 · ρ. In particular, DS has an accumulation point strictly smaller than the only 2 accumulation point of Dϵ . Thus DS cannot equal Dϵ for any S ̸= ϵ, and we conclude ϕ(ϵ) = ϵ. □
Lemma 7.22. Let ρ ∈ (0, 1). Let ϕ : Σ∗ → Σ∗ be an isometry. Then for any S ∈ Σ∗ , we have |ϕ(S)| = |S|.
22
GRANT MOLNAR
Proof. The claim is immediate from Lemma 7.5 and Lemma 7.21.
□
Lemma 7.23. Let ρ ∈ (0, 1). Let S, T ∈ Σ∗ , let n ∈ N, and let ϕ : Σ∗ → Σ∗ be an isometry. We have θn (S, T ) = θn (ϕ(S), ϕ(T )). Proof. This is immediate from Proposition 7.6, Lemma 7.21, and Lemma 7.22.
□
Theorem 7.24. Let ρ ∈ (0, 1). Every isometry of Σ∗ is either a character-permutation, or the composition of a character-permutation with reversal. Proof. Let ρ ∈ (0, 1). If |Σ| = 1, then the claim is trivial and immediate from Lemma 7.22. So suppose |Σ| ≥ 2. Let ϕ be an isometry of Σ∗ under dρ . By Lemma 7.22, ϕ induces a permutation π on Σ; extending π to Σ∗ character-wise induces another isometry on Σ∗ , and π −1 ϕ is an isometry which fixes Σ. Without loss of generality, we now assume that ϕ fixes Σ. We wish to show that ϕ is either the identity map or the reversal map R. We claim at least that ϕ(ak ) = ak for any character a ∈ Σ and any k ≥ 1. Indeed, by Proposition 7.6, we see θ1 (ϕ(ak ), a) = θ1 (ϕ(ak ), ϕ(a)) = θ1 (ak , a) = 0, but ak is the only length k string with the property θ1 (ak , a) = 0, so Lemma 7.22 implies ϕ(ak ) = ak . Let a, b ∈ Σ be distinct characters. By Lemma 7.23, ϕ preserves θ1 , so θ1 (ϕ(ab), a) = θ1 (ab, a) and θ1 (ϕ(ab), b) = θ1 (ab, b). As |ϕ(ab)| = 2, we conclude that [ϕ(ab)]1 = [ab]1 , so ϕ(ab) ∈ { ab, ba }. For a ̸= b, define ( 1 if ϕ(ab) = ab, χ(a, b) := −1 if ϕ(ab) = ba. Note that by bijectivity, χ(a, b) = χ(b, a). We claim that χ(a, b) is independent of our choice of a ̸= b. If |Σ| = 2, this claim is trivial. Otherwise, let a, b, c ∈ Σ be distinct characters, and consider the string abc, with bigrams ab and bc. We have θ2 (abc, ab), θ2 (abc, bc) < π2 while θ2 (abc, xy) = π2 for all other bigrams xy, so { ϕ(ab), ϕ(bc) } must be the bigrams of ϕ(abc). As a length 3 string has exactly two bigrams, we see { ϕ(ab), ϕ(bc) } must be the bigrams of some three-letter string. But this ( implies χ(a, b) = χ(b, c) as desired, and there must exist a ab if χ = 1, independent of a and b. χ ∈ { ±1 } such that ϕ(ab) = ba if χ = −1 Suppose by induction that we are given N and χ ∈ { ±1 } such that ϕ agrees with R on Σ≤N if χ = −1, and ϕ agrees with id on Σ≤N if χ = 1. Let S = s1 . . . sN +1 be a string of length N + 1 in Σ∗ , and let T1 = s1 . . . sN and T2 = s2 . . . sN +1 be the two N -grams of S. By θN -invariance, we see θN (ϕ(S), ϕ(T1 )), θN (ϕ(S), ϕ(T2 )) < π2 , so ϕ(T1 ) and ϕ(T2 ) are the two N -grams of ϕ(S). Now if χ = −1, then ϕ(T1 ) = R(T1 ) and ϕ(T2 ) = R(T2 ), which uniquely determines ϕ(S) = R(S). Likewise, if χ = 1, then ϕ(T1 ) = T1 and ϕ(T2 ) = T2 , which uniquely determines ϕ(S) = S. The claim follows. □ 8. Appendix: Tables and plots 8.1. Tables and plots. For completeness we include the main numeric summaries and plots generated from results.csv by our analysis script.
A WEIGHTED ANGLE DISTANCE ON STRINGS
Dataset
N
Edit
k-gram angle
JS k-gram
23
Weighted angle
splice 3190 0.0003/0.0009 0.0003/0.0009 0.0003/0.0009 0.0003/0.0009 strseq 1624 0.8825/0.8970 0.3293/0.6725 0.5394/0.7714 0.5060/0.7527 ucsc trf 8905 0.0003/0.0210 0.4390/0.8421 0.4309/0.8378 0.4596/0.8632 Table 1. Best ARI/NMI achieved by each distance family on each dataset (max over the family parameter: ρ for weighted angle, k for k-gram methods).
Dataset
Metric
Best ρ Best value
Std./Range
splice ari 0.6 0.0003 0.0003/0.0008 splice nmi 0.6 0.0009 0.0002/0.0004 splice silhouette 0.1 -1.0000 0.0000/0.0000 strseq ari 0.6 0.5060 0.1348/0.4105 strseq nmi 0.6 0.7527 0.1066/0.3083 strseq silhouette 0.1 0.8387 0.0722/0.2579 ucsc trf ari 0.6 0.4596 0.0817/0.2543 ucsc trf nmi 1.0 0.8643 0.0442/0.1463 ucsc trf silhouette 0.9 0.9527 0.0819/0.2611 Table 2. Sensitivity of the weighted angle distance to ρ: for each dataset and metric we report the best ρ (maximizing the metric) and the variability across the sweep ρ ∈ {0.1, 0.2, . . . , 1.0}.
Dataset
ρs (ARI, NMI) ρs (ARI, sil) ρs (NMI, sil)
splice 0.937 – – strseq 0.998 -0.439 -0.458 ucsc trf 0.974 0.136 0.097 Table 3. Spearman rank correlation ρs between evaluation metrics across the 19 distances tested (per dataset).
References [1] William B. Cavnar and John M. Trenkle, N-gram-based text categorization, Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval (Las Vegas, NV), 1994. [2] Rudi Cilibrasi and Paul M. B. Vitányi, Clustering by compression, IEEE Transactions on Information Theory 51 (2005), no. 4, 1523–1545. [3] Fred J. Damerau, A technique for computer detection and correction of spelling errors, Communications of the ACM 7 (1964), no. 3, 171–176. [4] Richard W. Hamming, Error detecting and error correcting codes, The Bell System Technical Journal 29 (1950), no. 2, 147–160. [5] Christina Leslie, Eleazar Eskin, and William Stafford Noble, The spectrum kernel: A string kernel for SVM protein classification, Pacific Symposium on Biocomputing, vol. 7, 2002, pp. 564–575. [6] Christina Leslie, Eleazar Eskin, Jason Weston, and William Stafford Noble, Mismatch string kernels for discriminative protein classification, Bioinformatics 20 (2004), no. 4, 467–476. [7] Vladimir I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, Doklady Akademii Nauk SSSR 163 (1965), no. 4, 845–848, In Russian. [8] Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, 2 ed., Cambridge University Press, 2021. [9] Huma Lodhi, Craig Saunders, John Shawe-Taylor, Nello Cristianini, and Chris Watkins, Text classification using string kernels, Journal of Machine Learning Research 2 (2002), 419–444.
24
GRANT MOLNAR
Dataset
Family
Median pairwise time
splice splice splice splice
edit kgram angle js kgram weighted angle
2.5s 1.2m 3.2m 19.3m
strseq strseq strseq strseq
edit kgram angle js kgram weighted angle
2.1s 39.0s 1.2m 19.7m
ucsc trf ucsc trf ucsc trf ucsc trf
edit kgram angle js kgram weighted angle
25.9s 9.1m 17.4m 5.26h
Table 4. Median wall-clock time to compute the full pairwise distance matrix for each family on each dataset (pure Python implementation; no caching or parallelism).
Figure 1. Best ARI achieved by each distance family on splice. [10] Christopher D. Manning, Prabhakar Raghavan, and Hinrich Schütze, Introduction to information retrieval, Cambridge University Press, 2008. [11] Grant Molnar, weighted-angle-distance: reference implementation and experimental pipeline, https://github.com/grantmolnar/weighted-angle-distance, 2026, Accessed Apr. 22, 2026.
A WEIGHTED ANGLE DISTANCE ON STRINGS
25
Figure 2. Best NMI achieved by each distance family on splice. [12] Brian D. Ondov, Todd J. Treangen, Páll Melsted, Adam B. Mallonee, Nicholas H. Bergman, Sergey Koren, and Adam M. Phillippy, Mash: Fast genome and metagenome distance estimation using MinHash, Genome Biology 17 (2016), no. 1, 132. [13] Hasan H. Otu and Khalid Sayood, A new sequence distance measure for phylogenetic tree construction, Bioinformatics 19 (2003), no. 16, 2122–2130. [14] Franco Pappalardo, strsimpy: String similarity library (includes cosine on n-gram count vectors), https://pypi.org/project/strsimpy/, 2024, Accessed Nov. 17, 2025. [15] Taylor Petty, Jan Hannig, Tunde I. Huszar, and Hari Iyer, A new string edit distance and applications, Algorithms 15 (2022), no. 7, 242. [16] Gérard Salton, Anita Wong, and Chung-Shu Yang, A vector space model for automatic indexing, Communications of the ACM 18 (1975), no. 11, 613–620. [17] Paul C. Shields, The ergodic theory of discrete sample paths, Graduate Studies in Mathematics, vol. 13, American Mathematical Society, 1996. [18] Sören Sonnenburg, Gabriele Schweikert, Philipp Philips, Johannes Behr, and Gunnar Rätsch, Accurate splice site prediction using support vector machines, BMC Bioinformatics 8 (2007), no. Suppl 10, S7. [19] Esko Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science 92 (1992), no. 1, 191–211. [20] Robert A. Wagner and Michael J. Fischer, The string-to-string correction problem, Journal of the ACM 21 (1974), no. 1, 168–173. [21] Andrzej Zielezinski, Hani Z. Girgis, Guillaume Bernard, Chris-Andre Leimeister, Kujin Tang, Thomas Dencker, Anna Katharina Lau, Sophie Röhling, Jae Jin Choi, Michael S. Waterman, Matteo Comin, Sung-Hou Kim, Susana Vinga, Jonas S. Almeida, Cheong Xin Chan, Benjamin T. James, Fengzhu Sun, Burkhard Morgenstern, and Wojciech M. Karlowski, Benchmarking of alignment-free sequence comparison methods, Genome Biology 20 (2019), no. 1, 144. Email address: [email protected]
26
GRANT MOLNAR
Figure 3. ARI and NMI versus ρ for the weighted angle distance on splice.
Figure 4. Best ARI achieved by each distance family on strseq.
A WEIGHTED ANGLE DISTANCE ON STRINGS
Figure 5. Best NMI achieved by each distance family on strseq.
Figure 6. ARI and NMI versus ρ for the weighted angle distance on strseq.
27
28
GRANT MOLNAR
Figure 7. Best ARI achieved by each distance family on ucsc trf.
Figure 8. Best NMI achieved by each distance family on ucsc trf.
A WEIGHTED ANGLE DISTANCE ON STRINGS
Figure 9. ARI and NMI versus ρ for the weighted angle distance on ucsc trf.
Figure 10. Silhouette versus ARI across all tested distances on strseq.
29
30
GRANT MOLNAR
Figure 11. Silhouette versus ARI across all tested distances on ucsc trf.
Figure 12. ARI versus DBSCAN noise fraction across all tested distances on strseq.
A WEIGHTED ANGLE DISTANCE ON STRINGS
31
Figure 13. ARI versus DBSCAN noise fraction across all tested distances on ucsc trf.