Skip to content
Fuzzy text search

Harmonic edit distance

disharmonic(x,y)=2H∣x∣+∣y∣−∣lcs(x,y)∣−H∣x∣−H∣y∣dis_{harmonic}(x,y) = 2H_{|x| + |y| - |lcs(x, y)|} - H_{|x|} - H_{|y|}

where:

  • ∣x∣|x| denotes string length
  • Hn=∑i=1n1iH_n = \sum^{n}_{i=1}\frac{1}{i} is the harmonic series
  • lcs(x,y)lcs(x,y) denotes the longest common subsequence of xx and yy

Type of Edit distance, which takes into account only insert and delete operations. Related to LCS distance. It is metric, but not normalised.

Note: it is not normalized e.g. value can be bigger 1.

disnorm(abcd,a)=2H∣abcd∣+∣a∣−∣lcs(abcd,a)∣−H∣abcd∣−H∣a∣=2H4+1−1−H4−H1=256−2512−1=1312>1dis_{norm}(abcd, a) = 2H_{|abcd| + |a| - |lcs(abcd, a)|} - H_{|abcd|} - H_{|a|} \\ = 2H_{4 + 1 - 1} - H_{4} - H_{1} = \frac{25}{6} - \frac{25}{12} - 1 = \frac{13}{12} > 1

Reading