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

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]

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

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次，因为它只在字符串中出现一次。

编辑

如果您希望容忍最后一次出现只是模式的一部分，受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。如果不是，那么found将为false。

Answer 2

有有效的Z-algorithm

给定一个长度为n的字符串S，Z算法产生一个数组Z，其中Zi是从Si开始的最长的子串的长度，也是S的前缀，即最大k使得所有0 ≤ j < k的Sj = Si + j。请注意，Zi = 0意味着S ≠ Si。为了使术语更简单，我们将同时作为前缀的子字符串称为前缀子字符串。

计算字符串的Z数组，并使用属性i + Z[i] == len和len % i == 0找到这样的位置i (len是字符串长度)。现在i是周期长度

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”更好，因为它来自更自然的