algorithm - 路径集合中最常见的子路径

Question

网上有很多关于最长公共(public)子序列问题的文献，但我有一个稍微不同的问题，想知道是否有人知道快速算法。

比如说，你有一组路径:

[1,2,3,4,5,6,7], [2,3,4,9,10], [3,4,6,7], ...

我们看到子路径 [3,4] 是最常见的。

知道找到这个的简洁算法吗？就我而言，有数万条路径!

Answer 1

假设一条“路径”必须包含至少两个元素，那么最常见的路径显然会有两个元素(尽管也可能有一个包含两个以上元素的路径同样常见——稍后会详细介绍) .所以你可以迭代所有列表并计算每对连续数字在不同列表中出现的频率并记住最常出现的那些对。这需要对每个列表进行一次迭代，这是您在任何情况下都必须执行的最少操作。

如果您对最长最常见的路径感兴趣，那么您可以以相同的方式开始，找到最常见的 2 段路径，但除了计数之外，还记录位置这些段中的每一个(例如 {(3,4): [2, 1, 0], ...} 在您的示例中，列表中的数字表示段在不同的位置路径)。现在，您可以采用所有最常见的长度为 2 的路径，看看对于其中任何一个，下一个元素对于所有该路径的出现是否也是相同的。在这种情况下，您有一个最常见的长度为 3 的路径，它与之前的长度为 2 的路径同样常见(很明显，它不能更常见)。您可以对长度为 4、长度为 5 等重复此操作，直到它在不使路径“不太常见”的情况下无法再扩展。这部分需要对每次扩展进行 n*k 的额外工作，其中 n 是剩余候选的数量，k 它们出现的频率。

(这假设频率节拍长度，即如果有一条长度为 2 的路径出现了三次，你更喜欢这个长度为 3 的路径出现两次。同样的方法也可以用于不同的起始长度，例如在不改 rebase 本算法或复杂度的情况下，至少需要长度为 3 的路径。)

---

这里有一个用 Python 编写的简单示例实现来演示该算法。这最多只能达到长度 3，但可以很容易地通过循环扩展到长度 4 甚至更长。此外，它不检查任何边缘情况(数组越界等)

# example data
data = [[1,2,  4,5,6,7,  9],
        [1,2,3,4,5,6,  8,9],
        [1,2,  4,5,6,7,8  ]]

# step one: count how often and where each pair appears
from collections import defaultdict
pairs = defaultdict(list)
for i, lst in enumerate(data):
    for k, pair in enumerate(zip(lst, lst[1:])):
        pairs[pair].append((i,k))

# step two: find most common pair and filter
most = max([len(lst) for lst in pairs.values()])
pairs = {k: v for k, v in pairs.items() if len(v) == most}
print(pairs)
# {(1, 2): [(0, 0), (1, 0), (2, 0)], (4, 5): [(0, 2), (1, 3), (2, 2)], (5, 6): [(0, 3), (1, 4), (2, 3)]}

# step three: expand pairs to triplets, triplets to quadruples, etc.
triples = [k + (data[v[0][0]][v[0][1]+2],) 
           for k, v in pairs.items() 
           if len(set(data[i][k+2] for (i,k) in v)) == 1]
print(triples)
# [(4, 5, 6)]