Optimal matching

Algorithm

Let ${\displaystyle S=(s_1,s_2,s_3,\dots s_T)}$ be a sequence of states ${\displaystyle s_i}$ belonging to a finite set of possible states. Let us denote ${\displaystyle \mathbf{S}}$ the sequence space, i.e. the set of all possible sequences of states.

Optimal matching algorithms work by defining simple operator algebras that manipulate sequences, i.e. a set of operators ${\displaystyle a_i:\mathbf{S}\to \mathbf{S}}$. In the most simple approach, a set composed of only three basic operations to transform sequences is used:

• one state ${\displaystyle s}$ is inserted in the sequence ${\displaystyle a_{s^{\prime }}^{\mathrm{I}\mathrm{n}\mathrm{s}}(s_1,s_2,s_3,\dots s_T)=(s_1,s_2,s_3,\dots ,s^{\prime },\dots s_T)}$
• one state is deleted from the sequence ${\displaystyle a_{s_2}^{\mathrm{D}\mathrm{e}\mathrm{l}}(s_1,s_2,s_3,\dots s_T)=(s_1,s_3,\dots s_T)}$ and
• a state ${\displaystyle s_1}$ is replaced (substituted) by state ${\displaystyle s_1^{\prime }}$, ${\displaystyle a_{s_1,s_1^{\prime }}^{\mathrm{S}\mathrm{u}\mathrm{b}}(s_1,s_2,s_3,\dots s_T)=(s_1^{\prime },s_2,s_3,\dots s_T)}$.

Imagine now that a cost ${\displaystyle c(a_i)\in {\mathbf{R}}_0^{+}}$ is associated to each operator. Given two sequences ${\displaystyle S_1}$ and ${\displaystyle S_2}$, the idea is to measure the cost of obtaining ${\displaystyle S_2}$ from ${\displaystyle S_1}$ using operators from the algebra. Let ${\displaystyle A=a_1,a_2,\dots a_n}$ be a sequence of operators such that the application of all the operators of this sequence ${\displaystyle A}$ to the first sequence ${\displaystyle S_1}$ gives the second sequence ${\displaystyle S_2}$: ${\displaystyle S_2=a_1\circ a_2\circ \dots \circ a_n(S_1)}$ where ${\displaystyle a_1\circ a_2}$ denotes the compound operator. To this set we associate the cost ${\displaystyle c(A)=\sum _{i=1}^{n}c(a_i)}$, that represents the total cost of the transformation. One should consider at this point that there might exist different such sequences ${\displaystyle A}$ that transform ${\displaystyle S_1}$ into ${\displaystyle S_2}$; a reasonable choice is to select the cheapest of such sequences. We thus call distance
${\displaystyle d(S_1,S_2)=\underset{A}{min}\left\{c(A)\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{h}\mathrm{t}\mathrm{h}\mathrm{a}\mathrm{t}{S}_2=A(S_1)\right\}}$
that is, the cost of the least expensive set of transformations that turn ${\displaystyle S_1}$ into ${\displaystyle S_2}$. Notice that ${\displaystyle d(S_1,S_2)}$ is by definition nonnegative since it is the sum of positive costs, and trivially ${\displaystyle d(S_1,S_2)=0}$ if and only if ${\displaystyle S_1=S_2}$, that is there is no cost. The distance function is symmetric if insertion and deletion costs are equal ${\displaystyle c(a^{\mathrm{I}\mathrm{n}\mathrm{s}})=c(a^{\mathrm{D}\mathrm{e}\mathrm{l}})}$; the term indel cost usually refers to the common cost of insertion and deletion.

Considering a set composed of only the three basic operations described above, this proximity measure satisfies the triangular inequality. Transitivity however, depends on the definition of the set of elementary operations.