How to find common patterns in thousands of strings?

user_3736538 0
Viewed 74

I don't want to find "abc" in strings ["kkkabczzz", "shdirabckai"]

Not like that.

But bigger patterns like this:

If I have to __, then I will ___.

["If I have to do it, then I will do it right.", "Even if I have to make it, I will not make it without Jack.", "....If I have to do, I will not...."]

I want to discover patterns in a large array or database of strings. Say going over the contents of an entire book.

Is there a way to find patterns like this?

I can work with JavaScript, Python, PHP.

data-analysis substring
1 Answers

The following could be a starting point:

The RegExp rx=/(\b\w+(\s+\w+\b)+)(?=.+\1)+/g looks for small (multiple word) patterns that occur at least twice in the text.

By playing around with the repeat quantifier + after (\s+\w+\b) (i.e. changing it to something like {2}) you can restrict your word patterns to any number of words (in the above case to 3: original + 2 repetitions) and you will get different results.

(?=.+\1)+ is a look ahead pattern that will not consume any of the matched parts of the string, so there is "more string" left for the remaining match attempts in the while loop.

const str="If I have to do it, then I will do it right. Even if I have to make it, I will not make it without Jack. If I have to do, I will not."

const rx=/(\b\w+(\s+\w+\b)+)(?=.+\1)+/g, r={};

let t;
while (t=rx.exec(str)) r[t[1]]=(rx.lastIndex+=1-t[1].length);

const res=Object.keys(r).map(p=>
  [p,[...str.matchAll(p)].length]).sort((a,b)=>b[1]-a[1]||b[0].localeCompare(a[0]));
// list all repeated patterns and their occurrence counts, 
// ordered by occurrence count and alphabet: 
console.log(res);

I extended my snippet a little bit by collecting all the matches as keys in an object (r). At the end I list all the keys of this object alphabetically with Object.keys(r).sort().

In the while loop I also reset the rx.lastIndex property to start the search for that next pattern immediately after the start of the last one found: rx.lastIndex+=1-t[1].length.

user_26100610
Related