FANDOM


Definition Edit

Given an alphabet $ \mathcal{L} $, the Subsequence similarity is a function $ SubsequenceSim: \mathcal{L}^*\times \mathcal{L}^*\longrightarrow [0,1] $ defined as

$ SubsequenceSim(s,t)=\frac{2\max\{|u|:u\sqsubseteq s, u\sqsubseteq t\}}{|s|+|t|} $

where $ \sqsubseteq $ is the subsequence relation.

Examples Edit

  • $ SubsequenceSim(\mbox{'10101101'},\mbox{'001100'}) = \frac{2|\mbox{'0110'}|}{8+6} = 8/14 = 0.57 $
  • $ SubsequenceSim(\mbox{'firstname'},\mbox{'surname'}) = \frac{2|\mbox{'name'}|}{9+7} = 8/16 = 0.5 $

Normalization Edit

It is normalized.

Applications Edit

  • Comparison of codes.
  • Comparison of composed-names (with shared affixed).

References Edit