1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ – Emre Jan 26 '18 at 3:18
  • $\begingroup$ 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. $\endgroup$ – Boris D. Teoharov Jan 26 '18 at 3:25
1
$\begingroup$

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.

$\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.