I'm developing a statistical function for name matching. A core component of the function is an algorithm that determines which individual names from a full name correspond to eachother. For the explanation of my function, i'd like to capture this algorithm in a mathematical equation.
Take for example the input string "JN SMITH T" and the reference string "JOHN ALEXANDER SMITH TAYLOR".
I want to determine how alike the input is to the reference, but i want to account for the possibility of missing names. So i generate a comparison matrix like so:
Each combination of names (like "JN" and "JOHN") gets a comparison score from some other function. Now i want to obtain the best possible total score, where each name can only match one other name, and ordering must be preserved.
In my current algorithm, i generate a list of permutations that can be added together, of which the maximum scoring one is then selected. The best mathematical description i can come up with is this:
Let the comparison matrix be $X$. Each name comparison gets a score at position $X_{ij}$. The input string has 3 names in it (which i'll describe as $n=3$), so we get at most 3 comparisons. That means (i think) that we're looking for the maximum of $\sum_{k=1}^{k=3} X_{i_{k}j_{k}}$, where $i_k < i_{k+1}$ and $j_k < j_{k+1}$ because order is preserved. If i assign the maximum score to the symbol $\Theta$, i'd finally get:
$$\Theta = max\left(\sum_{k=1}^{k=n} X_{i_{k}j_{k}}|i_k < i_{k+1}, j_k < j_{k+1}\right)$$
However, this equation looks like you'll always match all the input names. If my reference name is just "JOHN TAYLOR", you could only match two of the input names, not all three. The max sum would become $X_{11} + X_{23}$. Is it possible to reflect that into the equation for $\Theta$?
I think i've found the answer:
instead of defining $n$ to be the number of names in the input string, i'll define $q$ to be the number of names in the input string.
Then i'll define $n=(m,m+1,...,q)$ and $m = (1,2,...,q)$
and the total equation becomes
$$\Theta = max\left(\sum_{k=m}^{k=n} X_{i_{k}j_{k}}|i_k < i_{k+1}, j_k < j_{k+1},m=(1,2,...,q),n=(m,m+1,...,q)\right)$$