Need to determine similarity of sentences in some body of text. The sentences are not exactly human language (internal technical terms and abbreviations), so word2vec and similar approach is not useful.

Trying to line up all the sentences in 1-dimensional space and apply clustering. For that purpose I'm thinking of using some string distance measure from empty string to the given string.

Question: is there any string distance measure that satisfies triangle equality (d(a, b) = d(a) + d(b))? Distances like Levenshtein distance satisfy triangle inequality, while it seems to me distance that gives equality would be a much better predictor of "closeness" for strings (considering they are lined up in 1-d space by distance from empty string, that is strings are close if abs(d(a, '') - d(b, '') < ε)

Clarification: From definition of metric distance properties 1, 2, 3, but property 4 should be d(x, z) = d(x, y) + d(y, z)

  • $\begingroup$ You may interest in Levenshtein distance en.wikipedia.org/wiki/Levenshtein_distance. $\endgroup$ – logistic Dec 4 '17 at 7:22
  • $\begingroup$ As far as I understand, Levenshtein distance doesn't produce strong equality for all cases of triangle inequality. $\endgroup$ – ssanin82 Dec 4 '17 at 7:24
  • $\begingroup$ The relation you cite is not the triangle inequality (it isn't even an inequality): it's additivity. Is that what you really meant? $\endgroup$ – whuber Aug 22 '19 at 12:58

Your approach to line up the strings in a 1D-space is not the way to go. Instead use a distance like Levenshtein to build up the distance matrix between all strings and then use a clustering method that can work on metric spaces, e.g. agglomerative hierarchical linkage clustering (e.g. single-linkage).

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.