# Discovering string "motifs" in python

I have millions of strings from different sources that tend to exhibit some common patterns. Is there a way to extract these common motifs?

For example, in a list (of millions) that includes strings

['rs12346','rs1212122',...,'sxs-rs333',...,'kgp222']


..is there a way to extract the following patterns?

• 'rs' plus one or more digits
• 'sxs-rs' plus one or more digits
• 'kgp' plus one or more digits

Some other parameters:

• cleaning up beforehand isn't an option
• some manual tweaking would be possible (e.g. manually changing a pattern because of outside knowledge)
• exceptions (i.e. classifying less than 100% of the strings) can be tolerated
• an ideal solution would be using a built-in python library.

Assuming that letters are indicative of "motifs" and numbers are considered as digits and not exact numbers, this is what I would do:

First - transform numbers into a digit placeholder (#)

import re
s = re.sub("\d",s,"#")


Then I would transform a string into a bag-of-bigrams vector in the char level

from sklearn.feature_extraction.text import CountVectorizer
vecs = CountVectorizer(s, analyzer="char_wb", ngram_range=(1,3))


After these 2 steps, we got a sparse vector from any string:

'ab123' --> {" a":1,"ab":1,"b#","##":2,"# ":1}


Next we want to convert those vectors to a pairwise distance matrix and cluster by that distance.

from sklearn.metrics.pairwise import pairwise_distances
from scipy.cluster import  hierarchy
def link_cluster(X, threshold=0.1, metric="cosine", algo="average"):
X = X.todense()
Z = hierarchy.linkage(X, algo, metric=metric)
C = hierarchy.fcluster(Z,threshold, criterion="distance")
return C


Your end result would be

C = link_cluster(vecs)


I think the answer also depends on your usecase. If you just want to detect these kind of strings I would focus on heuristic rules that suit my needs, rather than creating a system that learns to recognize the patterns of the strings.

However, if your aim is generating similar kind of strings based on the current patterns or finding new strings in a stream of text, you should look for regex generators. There is this list of resources regarding regexes in general and you should focus on the generators for the task at hand.

For a similar task in the past, I had used an online, free tool that will generate a regex (if possible) that satisfies as many of your sample strings as possible. So you could give it a try, as a fast solution.

Either way, I would first do some data exploration(e.g. are numbers and letters also intermixed or do numbers always come up after or letters/symbols etc.), in order to get a better understanding for the problem at hand. Also, this could lead to simple heuristic rules that could suffice as a crude solution or at least a simple baseline system against which I would "pitch" a machine learning model.