I have some sequence of words as input (e.g. a sentence or part of a sentence). I'm looking for a way to find the position and contents of the most similar substring within a larger text, as well as some sort of similarity score.
The matching substring can contain typos, similarly sounding words, or fewer/extra words, compared to the input string.
Is there an established way to do this? I could only find answers for how to directly compare two strings for similarity, but nothing about finding the position and similarity score of the closest match within a text.
I'm more interested in matches in terms of characters and/or how stuff sounds, rather than meaning.
Ideally looking for a way to achieve this in JavaScript, but language-agnostic suggestions are also welcome.
What you want to use is dynamic time warping.
It's an algorithm for calculating a similarity score between two sequences, but it can also be used to find the places where the similarities are. Consider the pseudocode in the linked article (May 3rd 2022, if it has changed in the meantime). You probably want to use the second version which includes the locality constraint.
Extend the algorithm as follows: after calculating the DTW array, you can iterate your way backwards from DTW[n,m] towards DTW[0,0] by always going towards the previous minimum value. I. e. if your current position is [i,j] then your next position is [k,l] for which DTW[k,l] is minimal out of the three possible positions
k=i-1, l=jk=i-1, l=i-1k=i, l=j-1Assuming your text is in the first dimension and your "substring" on the second one, you have the following correspondences:
i that doesn't appear in the best matching.i that appears at position j in the best matching.j in the best matching string.The greatest k for which [k,0] appears in the backwards iteration and the smallest l for which [l,m] appears will be the beginning and end of the best matching sequence in your text.