5 ms·

I'm surprised this page and the page on "string metrics" don't say more about the mathematical implications of defining a distance metric on strings. Something

by blt 7y ago

I'm surprised this page and the page on "string metrics" don't say more about the mathematical implications of defining a distance metric on strings. Something interesting must pop up if you apply theorems about metric spaces from analysis and topology to the set of strings with edit distance.

dls2016 7y ago
This metric induces the discrete topology, which isn't very useful. Regarding its metric structure, you could apply the contraction mapping theorem but I can't think of any interesting contractions off the top of my head. I'm just spit-balling here... but when a natural metric induces the discrete topology then it's probably more useful to look at connectivity graphs induced by the metric. For instance the graph on all strings with two strings connected by an edge if their edit distance equals 1. Restrict to words in a dictionary and you have a basic spelling suggestion algorithm. Edit: the analyst in me really wants a translation-invariant abelian group structure ... then we can do Fourier analysis...
- olooney 7y ago
  > Restrict to words in a dictionary and you have a basic spelling suggestion algorithm. Yep. https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html
- mrkeen 7y ago
  The upside of it being metric is that you can optimise lookups by storing the strings in a BK-tree.
- jointpdf 7y ago
  I’m kind of tacking this on here, but does anyone have a good recommendation for notes or a book on applied topology for someone with a decent but not extensive background in applied math? In particular, my goal is to more deeply understand manifold learning techniques like MDS and UMAP.
lmkg 7y ago
The implications are more practical, rather than theoretical. As others have said, the theoretical implications are mostly for continuous spaces, which strings are not. From the practical side, there are a lot of algorithms designed to work on vectors that can work on sets of strings. It depends on whether the algorithm really needs to use the underlying vector, or whether it just uses distances. For example: Clustering! By using string metrics, you can group sets of strings into clusters using standard algorithms. Some algorithms like K-means won't work (in general, you can't find the string half-way in-between two strings), but some algorithms can apply, especially hierarchical clustering. I think you could apply MDS to sets of strings the same way, but I'm a little less familiar with the guts of that algorithm.
- wrs 7y ago
  Yes. I have used clustering on Levenshtein distance in this way to find misspellings in user-entered data fields, in order to canonicalize the data for more analysis.

by blt 7y ago

dls2016 7y ago

This metric induces the discrete topology, which isn't very useful. Regarding its metric structure, you could apply the contraction mapping theorem but I can't think of any interesting contractions off the top of my head. I'm just spit-balling here... but when a natural metric induces the discrete topology then it's probably more useful to look at connectivity graphs induced by the metric. For instance the graph on all strings with two strings connected by an edge if their edit distance equals 1. Restrict to words in a dictionary and you have a basic spelling suggestion algorithm. Edit: the analyst in me really wants a translation-invariant abelian group structure ... then we can do Fourier analysis...

olooney 7y ago
> Restrict to words in a dictionary and you have a basic spelling suggestion algorithm. Yep. https://norvig.com/spell-correct.html https://norvig.com/spell-correct.html
mrkeen 7y ago
The upside of it being metric is that you can optimise lookups by storing the strings in a BK-tree.
jointpdf 7y ago
I’m kind of tacking this on here, but does anyone have a good recommendation for notes or a book on applied topology for someone with a decent but not extensive background in applied math? In particular, my goal is to more deeply understand manifold learning techniques like MDS and UMAP.

lmkg 7y ago

The implications are more practical, rather than theoretical. As others have said, the theoretical implications are mostly for continuous spaces, which strings are not. From the practical side, there are a lot of algorithms designed to work on vectors that can work on sets of strings. It depends on whether the algorithm really needs to use the underlying vector, or whether it just uses distances. For example: Clustering! By using string metrics, you can group sets of strings into clusters using standard algorithms. Some algorithms like K-means won't work (in general, you can't find the string half-way in-between two strings), but some algorithms can apply, especially hierarchical clustering. I think you could apply MDS to sets of strings the same way, but I'm a little less familiar with the guts of that algorithm.

wrs 7y ago
Yes. I have used clustering on Levenshtein distance in this way to find misspellings in user-entered data fields, in order to canonicalize the data for more analysis.