Python:识别和删除列表中的重复序列

Question

我正在寻找在列表中查找重复序列的最佳方法.序列被定义为至少两个相邻值.

示例:在以下列表中,应标识并删除重复序列.

a = [45874,
    35195, # <-
    28965,
    05867,
    25847, # <-
    94937,
    64894,
    55535,
    62899,
    00391,
    35195, # Duplicate Sequence Start
    28965,
    05867,
    25847, # Duplicate Sequence End
    08483,
    55801,
    33129,
    42616]

我无法解决任何问题,所以任何帮助都非常感谢!

Answer 1

使用Boyer-Moore算法可以在不小于O(nm)的情况下在长度为n的串中找到长度为m的单个子序列.找到所有重复的子序列很可能不止于此.虽然,如果你想要的只是删除子序列而不是找到它们,那就有一个技巧.

删除O(n)中的重复子序列

我们只需关注长度为2的子序列,因为任何序列都可以表示为长度为2的重叠子序列.这种观察允许我们保持这些对的计数,然后从右到左移除它们.

特别是,这需要遍历列表仅固定的次数,因此是O(n).

from collections import Counter

def remove_duplicates(lst):
    dropped_indices = set()
    counter = Counter(tuple(lst[i:i+2]) for i in range(len(lst) - 1))

    for i in range(len(lst) - 2, -1, -1):
        sub = tuple(lst[i:i+2])
        if counter[sub] > 1:
            dropped_indices |= {i, i + 1}
            counter[sub] -= 1

    return [x for i, x in enumerate(lst) if i not in dropped_indices]

以下是基于提供的输入的示例.

a = [45874,
     35195, # This
     28965, # Is
     5867,  # A
     25847, # Subsequence
     94937,
     64894,
     55535,
     62899,
     391,
     35195, # Those
     28965, # Should
     5867,  # Be
     25847, # Removed
     8483]

b = remove_duplicates(a)
# Output:
#   [45874,
#    35195,
#    28965,
#    5867,
#    25847,
#    94937,
#    64894,
#    55535,
#    62899,
#    391,
#            <- Here the duplicate was removed
#    8483]