10
$\begingroup$

I have thousands of lists of strings, and each list has about 10 strings. Most strings in a given list are very similar, though some strings are (rarely) completely unrelated to the others and some strings contain irrelevant words. They can be considered to be noisy variations of a canonical string. I am looking for an algorithm or a library that will convert each list into this canonical string.

Here is one such list.

  • Star Wars: Episode IV A New Hope | StarWars.com
  • Star Wars Episode IV - A New Hope (1977)
  • Star Wars: Episode IV - A New Hope - Rotten Tomatoes
  • Watch Star Wars: Episode IV - A New Hope Online Free
  • Star Wars (1977) - Greatest Films
  • [REC] 4 poster promises death by outboard motor - SciFiNow

For this list, any string matching the regular expression ^Star Wars:? Episode IV (- )?A New Hope$ would be acceptable.

I have looked at Andrew Ng's course on Machine Learning on Coursera, but I was not able to find a similar problem.

$\endgroup$
  • 2
    $\begingroup$ PS I think the term you're looking for is "canonical" $\endgroup$ – Sean Owen Aug 23 '14 at 9:23
  • $\begingroup$ Is the "most probable"/"most consensual" string you are looking to idendify a regular expression? Or one of the strings on the list? $\endgroup$ – MrMeritology Aug 24 '14 at 21:47
  • $\begingroup$ @MrMeritology I am not looking for a regular expression. I have shown a regular expression in my question just to illustrate how flexible I am in the kind of strings I would consider to be correct. $\endgroup$ – lacton Aug 25 '14 at 8:07
  • $\begingroup$ OK. Then the answer I gave below should work for you. $\endgroup$ – MrMeritology Aug 25 '14 at 18:53
  • $\begingroup$ Would this come under NER (named entity recognition)? $\endgroup$ – hippietrail Sep 26 '14 at 3:30
4
$\begingroup$

As a naive solution I would suggest to first select the strings which contain the most frequent tokens inside the list. In this way you can get rid of irrelevant string.

In the second phrase I would do a majority voting. Assuming the 3 sentences:

  • Star Wars: Episode IV A New Hope | StarWars.com
  • Star Wars Episode IV - A New Hope (1977)
  • Star Wars: Episode IV - A New Hope - Rotten Tomatoes

I would go through the tokens one by one. We start by "Star". It wins as all the string start with it. "Wars" will also win. The next one is ":". It will also win.

All the tokens will ein in majority voting till "Hope". The next token after "Hope" will be either "|", or "(" or "-". None of the will win in majority voting so I will stop here!

Another solution would be probably to use Longest common subsequence.

As I said I have not though about it much. So there might be much more better solutions to your problem :-)

| improve this answer | |
$\endgroup$
3
$\begingroup$

First compute the edit distance between all pairs of strings. See http://en.wikipedia.org/wiki/Edit_distance and http://web.stanford.edu/class/cs124/lec/med.pdf. Then exclude any outliers strings based on some distance threshold.

With remaining strings, you can use the distance matrix to identify the most central string. Depending on the method you use, you might get ambiguous results for some data. No method is perfect for all possibilities. For your purposes, all you need is some heuristic rules to resolve ambiguities -- i.e. pick two or more candidates.

Maybe you don't want to pick "most central" from your list of strings, but instead want to generate a regular expression that captures the pattern common to all the non-outlier strings. One way to do this is to synthesize a string that is equidistant from all the non-outlier strings. You can work out the required edit distance from the matrix, and then you'd randomly generate regular using those distances as constraints. Then you'd test candidate regular expressions and accept the first one that fits the constraints and also accepts all the strings in your non-outlier list. (Start building regular expressions from longest common substring lists, because those are non-wildcard characters.)

| improve this answer | |
$\endgroup$

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.