5
$\begingroup$

I am trying to detect patterns in huge code bases. I managed to filter the entire codebase into a tagged string, as in: ABACBABAABBCBABA

The result should be: ABA *3 CBA *2

I'm trying to build / use an algorithm which will find ANY unknown repeating pattern inside the string. The length of the pattern, it's composition, and the number of repeats is unknow.

To be a pattern it must occur atleast twice. And have atleast 2 items. Once I detect the patterns I can represent them back in their original context

I have tried iterating over each tag. For each tag find the following tag in the string. continue until adding a tag matches only one repeat - hence no more pattern.

I get lost in implemetation (in JS or Python) and I'm hoping there is a better way. Thanks.

$\endgroup$
3
  • 1
    $\begingroup$ Welcome to CS.SE! Can you specify more precisely what kinds of patterns you want to look for? An example isn't a substitute for a specification of the problem. Are you simply looking for repeated substrings that occur at least twice? There are standard algorithms for finding the longest repeated substring; have you tried looking at them to see if they will meet your needs? There are probably many algorithms; are you looking for the fastest, or the easiest to implement? Do you have specific running time requirements? $\endgroup$
    – D.W. ♦
    Jul 22, 2017 at 1:37
  • $\begingroup$ Maybe you can look up the lempel ziv algorithm $\endgroup$
    – Elle Najt
    Jul 22, 2017 at 4:24
  • $\begingroup$ "The result should be:" -- why? Which definition/metric of "good" did you use here? Why do you expect it to be applicable to more than this small example? $\endgroup$
    – Raphael ♦
    Jul 22, 2017 at 9:55

5 Answers 5

Reset to default
3
$\begingroup$

Here is a simple search in Python:

s = "ABACBABAABBCBABA"
d={}
for sublen in range(MINLEN,int(len(s)/MINCNT)):
    for i in range(0,len(s)-sublen):
        sub = s[i:i+sublen]
        cnt = s.count(sub)
        if cnt >= MINCNT and sub not in d:
             d[sub] = cnt

Where MINLEN is the minimum length of pattern you want to find and MINCNT is the minimum number of occurrences of that pattern. This runs in O(n^3) (nested for loop + .count()).

If you set MINCNT=2 and MINLEN=2 the result of running this is d = {'CB': 2, 'BABA': 2, 'AB': 4, 'CBAB': 2, 'CBABA': 2, 'BAB': 2, 'BA': 5, 'ABA': 3, 'CBA': 2}

These are all of the patterns that match your string given your description. Your question is a bit unclear in the example, if this is not what you are looking for let me know.

$\endgroup$
1
  • $\begingroup$ Thanks! Worked perfectly. I now need to tune it to give the longest pattern without internal repeats, for instance for ABCDABCDABCDABCD I need the result to be: ABCD and not ABCDABCD or AB, BC, CD, DA But the definition for this is not yet clear in my head so I can't expect to write the algorithm just yet. You put me on a good start. Merci $\endgroup$
    – agora
    Jul 25, 2017 at 8:50
5
$\begingroup$

Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves encode the positions.

$\endgroup$
1
$\begingroup$

What you need looks exactly like an LZ77 algorithm. It has many possible implementations. In particular, you can perform suffix sort on input data (current algorithms are so efficient that they can sort 10 megabytes in less than a second), and get index into your text, sorted on full string being pointed. One particular fast implementation is https://github.com/y-256/libdivsufsort - I think it should be more efficient and easier to use than the suffix tree.

$\endgroup$
0
$\begingroup$

I am put this just in case if someone else is interested with this topic. I find the following work easy to understand and implement for pattern discovery in string.

E. Keogh, J. Lin and A. Fu (2005). HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence. In Proc. of the 5th IEEE International Conference on Data Mining (ICDM 2005), pp. 226 - 233., Houston, Texas, Nov 27-30, 2005.

The paper is available here. https://www.cs.ucr.edu/~eamonn/HOT%20SAX%20%20long-ver.pdf

$\endgroup$
-1
$\begingroup$

If I understand correctly, what you're asking is pretty much the opposite of the question "How truly random a string is?".
There's a huge literature on this in Cryptography and specifically random and pseudorandom generators, you can use statistical tests and tools to recognize recurring patterns.
But first you must have a clear vision on how to sort the significance of these patterns, I recommend defining a utility function u(n, r) in which n is the length of the pattern and r is it's repetition.

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