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

Question

我正在进行文本挖掘，试图清理弹幕数据。（弹幕是视频网站上的一种评论）我的数据中有表达式的重复。（"LOL LOL LOL"，"LMAOLMAOLMAOLMAO"）我想得到"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]

这段代码可以正确输出前两种情况的答案，但无法处理所有情况。

- Mcree

---

“it comes more naturally” 是什么意思？如何量化？ - khelwood

相关，但不适用于您的最后一个示例：在字符串中删除重复字符模式的正则表达式。 - Georgy

例如，对于“吃一个苹果吃一个苹果吃一个苹果吃一个”的情况，“吃一个苹果”是更好的结果。我还没有想出一个好的解释，忽略这个条件的解决方案也是可以的。 - Mcree

Answer 1

我不太精通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次，因为它只在你的字符串中出现了一次。

编辑

如果你想容忍最后一次出现只是由输入字符串限制的模式的一部分，那么算法可以改变如下:

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。如果不是，则found将为false。

- Lajos Arpad

Answer 2

这里有一个有效的Z算法

给定长度为n的字符串S，Z算法生成一个数组Z，其中Z[i]是从S[i]开始的最长子串的长度，该子串也是S的前缀，即满足S[j] = S[i + j]（0 ≤ j < k）的最大k。注意，如果S[0] ≠ S[i]，则Z[i] = 0。为了更方便地使用术语，我们将同时是前缀的子串称为前缀子串。

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

- MBo

Answer 3

你可以这样做：

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"比"abcdabcdabc"更好，因为它更自然。

- Sebastien D