How to determine the minimum period of a periodic series

user_9145521 0
Viewed 379

I am doing a text mining and trying to clean bullet screen (弹幕) data.(Bullet screen is a kind of comment in video websites) There are repetitions of expressions in my data. ("LOL LOL LOL", "LMAOLMAOLMAOLMAO") And I want to get "LOL", "LMAO".

In most cases, I want to find the minimum period of a sequence.

CORNER CASE: The tail of the input sequence can be seen as a part of the periodic subsequence. 

"eat an apple eat an apple eat an" # input
"eat an apple" # output

There are some other test cases:

cases = [
    "abcd",        #4  abcd
    "ababab",      #2  ab
    "ababcababc",  #5  ababc
    "abcdabcdabc", #4  abcd
]

NOTE: As for the last case "abcdabcdabc", "abcd" is better than "abcdabcdabc" because the last three character "abc" is part of "abcd".

def solve(x):
    n = len(x)
    d = dict()
    T = 0
    k = 0
    while k < n:
        w = x[k]
        if w not in d:
            d[w] = T
            T += 1
        else:
            while k < n and d.get(x[k], None) == k%T:
                k += 1
            if k < n:
                T = k+1
        k += 1
    return T, x[:T]

it can output correct answers for first two cases but fails to handle all of them.

algorithm python string
3 Answers

I'm not fluent in Python, but can easily describe the algorithm you need:

found <- false
length <- inputString.length
size = 1
output <- inputString
while (not found) and (size <= length / 2) do
    if (length % size = 0) then
        chunk <- inputString.substring(0, size)
        found <- true
        for (j <- 1,length/size) do
            if (not inputString.substring(j * size, size).equals(chunk)) then
                found <- false
            if end
        for end
        if found then
            output <- chunk
        if end
    if end
    size <- size + 1
while end

The idea is to increasingly take substrings starting from the start of the string, the starting length of the substrings being 1 and while you do not find a repetitive cycle, you increase the length (until it is evidently no longer feasible, that is, half of the length of the input has been reached). In each iteration you compare the length of the substring with the length of the input string and if the length of the input string is not divisible with the current substring, then the current substring will not be repetitive for the input string (an optimization would be to find out what numbers is your input string's length divisible with and check only for that lengths in your substrings, but I avoided such optimizations for the sake of understandability). If the size of your string is divisible with the current size, then you take the substring from the start of your input string up until the current size and check whether it is repeated. The first time you find such a pattern you can stop with your loop, because you have found the solution. If no such solution is found, then the input string is the smallest repetitive substring and it is repeated 0 times, as it is found in your string only once.

EDIT

If you want to tolerate the last occurrence being only a part of the pattern, limited by the inputString, then the algorithm can be changed like this:

found <- false
length <- inputString.length
size = 1
output <- inputString
while (not found) and (size <= length / 2) do
    chunk <- inputString.substring(0, size)
    found <- true
    for (j <- 1,length/size) do
        if (not inputString.substring(j * size, size).equals(chunk)) then
            found <- (chunk.indexOf(inputString.substring(j).length) = 0)
        if end
    for end
    if found then
        output <- chunk
    if end
    size <- size + 1
while end

In this case, we see the line of

            found <- (chunk.indexOf(inputString.substring(j).length) = 0)

so, in the case of a mismatch, we check whether our chunk starts with the remaining part of the string. If so, then we are at the end of the input string and the pattern is partially matched up until the end of the string, so found will be true. If not, then found will be false.

user_4365600

There is effective Z-algorithm

Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from S[i] which is also a prefix of S, i.e. the maximum k such that S[j] = S[i + j] for all 0 ≤ j < k. Note that Z[i] = 0 means that S[0] ≠ S[i]. For easier terminology, we will refer to substrings which are also a prefix as prefix-substrings.

Calculate Z-array for your string and find such position i with property i + Z[i] == len and len % i == 0 (len is string length). Now i is period length

user_8444160

You could do it this way :

def solve(string):
    foundPeriods = {}

    for x in range(len(string)):
        #Tested substring
        substring = string[0:len(string)-x]
        #Frequency count
        occurence_count = string.count(substring)

        #Make a comparaison to original string
        if substring  * occurence_count in string:
            foundPeriods[occurence_count] = substring 

    return foundPeriods[max(foundPeriods.keys())]


for x in cases:
    print(x ,'===> ' , solve(x), "#" , len(solve(x)))
    print()

Output

abcd ===>  a # 1
ababab ===>  ab # 2
ababcababc ===>  ababc # 5
abcdabcdabc ===>  abcd # 4

EDIT : Answer edited to consider the following in the question

"abcdabcdabc", "abcd" is better than "abcdabcdabc" because it comes more naturally

user_76525440
Related