如何确定周期序列的最小周期

Question

我正在做一个文本挖掘，并试图清理子弹屏幕（弹幕）数据。（子弹屏幕是视频网站中的一种评论）我的数据中有重复的表达式。（“LOL LOL LOL”，“lmaolmaolmao”）我想得到“LOL”，“LMAO”。你知道吗

在大多数情况下，我想找出序列的最小周期。你知道吗

转角情况：输入序列的尾部可以看作周期子序列的一部分。你知道吗

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

还有其他一些测试用例：

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

注意：对于最后一种情况“abcdabcdabc”，“abcd”比“abcdabcdabc”好，因为最后三个字符“abc”是“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]

它可以输出前两种情况的正确答案，但无法处理所有情况。你知道吗

Answer 1

存在有效的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.

为您的字符串计算Z数组，并找到具有属性i + Z[i] == len和len % i == 0（len是字符串长度）的位置i。现在i是周期长度

Answer 2

你可以这样做：

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()

输出

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

编辑： 编辑答案以考虑问题中的以下内容

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

Answer 3

我对Python并不精通，但可以很容易地描述您需要的算法：

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

这个想法是越来越多地从字符串的开头开始取子字符串，子字符串的起始长度是1，当你没有找到一个重复的循环时，你增加长度（直到它显然不再可行，也就是说，已经达到输入长度的一半）。在每次迭代中，比较子字符串的长度和输入字符串的长度，如果输入字符串的长度不能与当前子字符串整除，那么当前的子字符串对于输入字符串将不会重复（一种优化方法是找出输入字符串的长度可整除的数字，并只检查子字符串中的长度，但是为了便于理解，我避免了这种优化）。如果字符串的大小可以被当前大小整除，那么可以从输入字符串的开头一直取子字符串直到当前大小，并检查是否重复。第一次找到这样的模式时，可以停止循环，因为您已经找到了解决方案。如果找不到这样的解决方案，则输入字符串是最小的重复子字符串，并且重复0次，因为它只在字符串中找到一次。你知道吗

编辑

如果希望允许最后一次出现仅是模式的一部分，并受inputString的限制，则可以如下更改算法：

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

在这种情况下，我们看到

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

因此，在不匹配的情况下，我们检查块是否以字符串的剩余部分开始。如果是这样，那么我们就在输入字符串的末尾，并且模式部分匹配到字符串的末尾，所以found将为true。如果没有，那么发现将是假的。你知道吗