I'm struggling with the concepts of writing a formula that will help me tease out certain characteristics of strings I'm comparing. I know this is mathexchange, but bear with me.

Essentially, I have loads of information about two strings I'm comparing. Among those data, I have: Where they're located in a larger context, where they're located in relation to one another, how long they are, how similar they are, etc.

I want to write a formula/algorithm that will help me score these strings for, essentially, grouping. I think I'm on the right track with the data I'm capturing, but I am struggling to piece it into a robust formula with which to get a useful score.

Ms : The similarity of the strings; Based on Levenshtein distance, so it scales linearly with differences. Can be 0 -> Infinity. 0 is an exact match

L1 : The length of string1

L2 : The length of string2

Ld : The difference in those lengths

P : The proximity of one string to another. Based on the closest point of the strings (one's beginning to another's end or vice versa) in an index.

I know that I want Ms to only "matter" if L1, L2 are high and Ld is low. And I only want P to "matter" if Ms is sufficiently bolstered by L1, L2 and Ld.

Is there anywhere I can look to gain insight on this? It can't be a new problem, but if it is, I'm more than happy to learn how to solve it on my own.

Thanks all.


1 Answer 1


For a start, you could try:

$$S(M_s, L_1, L_2, L_d, P) = \frac{L_1L_2}{L_d}\left(\frac{100}{M_s+1} + \frac{100}{P}\right).$$

You only get a decent score if $L_1, L_2$ are high and $L_d$ is low. After that, it depends on $M_s, p$.

This wouldn't be a horrible start to your development. You'll almost certainly want to refine this, and this depends on your goals for mining the text you have. So you can see what this gives you, and if it's not what you expect, then see why this measure gave you what it gave you, and try again.

  • $\begingroup$ Thanks for the kicking off point, John. I'm curious what resources would have aided me toward finding my way toward what you presented. $\endgroup$
    – dclowd9901
    Feb 4, 2014 at 21:14
  • $\begingroup$ No problem. I didn't refer to anything. I just looked at the relationships you needed and applied the simplest functions I could to exhibit what you needed. The $M_s + 1$ came about because you said $0$ was a valid value and I didn't want that term to be undefined. $\endgroup$
    – John
    Feb 4, 2014 at 22:14
  • $\begingroup$ Awesome, thanks! $\endgroup$
    – dclowd9901
    Feb 4, 2014 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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