6
$\begingroup$

I am not sure whether I formulated the question correctly. Basically, what I want to do is:

Let's suppose I have a list of 1000 strings which look like this:

cvzxcvzxstringcvzcxvz

otortorotrstringgrptprt

vmvmvmeopstring2vmrprp

vccermpqpstring2rowerm

proorororstring3potrprt

mprto2435string3famerpaer

etc.

I'd like to extract these reoccuring strings that occur on the list. What solution should I use? Does anyone know about algorithm that could do this?

$\endgroup$
5
  • $\begingroup$ How do you decide that "string", "string2" and "string3" are similar, but "string", "xstring" and "stringg", for example, are not? $\endgroup$
    – ffriend
    Oct 23, 2014 at 19:12
  • $\begingroup$ As I understood it, string, string2 and string3 are placeholders; they are not necessarily similar. $\endgroup$
    – Emre
    Oct 23, 2014 at 20:05
  • $\begingroup$ By string similar I mean they are exactly the same, char by char. Additionally, there might be multiple pairs of exact substrings between the two strings. $\endgroup$ Oct 24, 2014 at 5:58
  • $\begingroup$ No, the question is if there is another string that has "stringg" then if and how is it different from string2 or string3? The question is about defining EXACTLY what you want to do. Like is there a minimum length of strings you're looking to cluster? Is there a maximum length? $\endgroup$
    – LauriK
    Oct 27, 2014 at 15:23
  • $\begingroup$ I've implemented longest common substring algorithm. It solved my problem but it's expensive computationally. $\endgroup$ Oct 28, 2014 at 8:28

1 Answer 1

2
$\begingroup$

Interesting question! I have not encountered it before so here is a solution I just made up, inspired by the approach taken by the word2vec paper:

  1. Define the pair-wise similarity based on the longest common substring (LCS), or the LCS normalized by the products of the string lengths. Cache this in a matrix for any pair of strings considered since it is expensive to calculate. Also consider approximations.

  2. Find a Euclidean (hyperspherical, perhaps?) embedding that minimizes the error (Euclidean distance if using the ball, and the dot product if using the sphere). Assume random initialization, and use a gradient-based optimization method by taking the Jacobian of the error.

  3. Now you have a Hilbert space embedding, so cluster using your algorithm of choice!

Response to deleted comment asking how to cluster multiple substrings: The bulk of the complexity lies in the first stage; the calculation of the LCS, so it depends on efficiently you do that. I've had luck with genetic algorithms. Anyway, what you'd do in this case is define a similarity vector rather than a scalar, whose elements are the k-longest pair-wise LCS; see this discussion for algorithms. Then I would define the error by the sum of the errors corresponding to each substring.

Something I did not address is how to choose the dimensionality of the embedding. The word2vec paper might provide some heuristics; see this discussion. I recall they used pretty big spaces, on the order of a 1000 dimensions, but they were optimizing something more complicated, so I suggest you start at R^2 and work your way up. Of course, you will want to use a higher dimensionality for the multiple LCS case.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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