# Finding repeating string patterns in thousands of files

I have files like the following: https://pastebin.com/5mkXY1aU

These are created by filling predefined forms so there are thousands of them that would match a pattern.

I will try to give more generic example for the sake of simplicity.

Let's say I have thousands of documents created using different patterns like 

- "sjkghkjfs <data> skjfs <data> kjskdfjsfkjs <data> sahkj";
- "tretyer erytewr fskjdf <data> trjk";
- "sdhfjsdhj <data> <data> <data> dsjadh";
- "<data> djfhsdk"; and so on.


<data> could be just any string.

I don't know what these patterns are beforehand. I want to find them out.

I can easily come up with some bruteforce solution but it would obviously not work on such amount of data.

It sounds to me like a problem that might have already been solved.

I wondered if there is some readily available software tool I could utilize directly to solve this or a library atleast ?

In case there isn't one how should I proceed to solve it in the most painless way ?

It is a one time task to find these patterns out, so I am not into the idea of spending days on implementing a solution from the scratch.

• This is more of an information retrieval problem than a machine learning one. I suppose you want to define a minimum string length (otherwise each character could be a string), and look for matches in any position? – Emre Jan 26 '18 at 3:18
• Any character could be a string. There are no limitations. Basically there could be thousand words in the begginning of each document before the meaningful data comes. These thousand words at the beginning define a pattern found in thousands of documents. Another pattern could contain the payload at the beginning .... in the middle ... at any position, really. Spaces are considered a delimiter. Even though a trivial solution will produce very big number of combinations. – Boris D. Teoharov Jan 26 '18 at 3:25

## 1 Answer

It looks like you want new word discover ?

## Because thousand is not a big deal

Just build ngrams of filenames , count them would be fine .

You can use Trie to store string counts, reduce memory cost , I can provide a dict way(in python):

from collections import defaultdict, Counter

# for memory effcient, you would need trie here
# t = Trie()
t = defaultdict(int)

filenames = ["sjkghkjfs <data> skjfs <data> kjskdfjsfkjs <data> sahkj",
"tretyer erytewr fskjdf <data> trjk",
"...."]

# some preprocess, tokenize to  sentence , to  words , filter useless one

def ngrams(s, start, end):
for i in range(start, end+1):
if len(s) > i:
for j in range(i, len(s)):
yield s[j:j+i]

# Suppose you need same string with length 4 ~ 6
for s in filenames:
for word in ngrams(s, 4, 7):
t[word]+=1

# Suppose you need most_common 5
print(Counter(t).most_common(5))


## Further more

you can

1. tokenize the filenames at first.
2. Calculate tf-idf or word entropy to remove the useless words
3. then do something like above .

## And

If you have a group of traget strings , word2vec may be a good tool, you can use it to search the strings in similar domain.