序列文件中最频繁子串的前列

Question

我有一个文件，里面有很多序列（每个序列的长度都不一样），像这样：

5-2-6
5-6-6-6-1-8
4
1-7-6-6-2-6-6-1
18-24-2-6-6-1-8

我需要计算所有序列中出现频率最高的子串，并得到像这样的结果：

6-6       5 times
2-6       3 times
6-6-1     3 times
6-1       3 times
6-1-8     2 times
1-8       2 times
2-6-6-1   2 times
2-6-6     2 times

子串的长度可以是任意的，但至少要有两个字符。我还需要在代码中提供一个选项，可以改变子串的长度，比如说找出长度超过三个字符的子串。

我知道我应该使用后缀树，但我找不到适合我这个情况的有效例子((

使用的语言是R或Python。

Answer 1

R语言并不是处理这个问题的最佳选择，因为我知道的情况是，它对树的支持并不好。如果你只是想要一个简单粗暴的解决办法，这个方法可以用，但效率并不高：

# Create some data
set.seed(1)
data<-replicate(1000,sample(1:10,round(runif(1,1,8)),replace=TRUE))
# A function for all substrings
all.substrings<-function(s) unlist(sapply(1:length(s), function(y) sapply(y:length(s), function(x) s[y:x])),recursive=FALSE)
# Grab all strings
substrings<-unlist(sapply(data,all.substrings),recursive=FALSE)
# Strip one length substrings
substrings<-substrings[lapply(substrings,length)>1]
# Paste them together so you can easily aggregate
substrings.pasted<-sapply(substrings,paste,collapse=' ')
# Aggregate and sort.
sorted.results<-sort(table(substrings.pasted),decreasing=TRUE)
# Display
head(sorted.results)
# 10 3 4 10  8 1  9 4  9 2 8 10 
#   52   50   48   48   47   45 

所以序列 10 3 出现了 52 次，这是最多的。

Answer 2

你不需要使用后缀树；只需要把序列分开，然后用一个滑动窗口迭代器来生成子字符串。可以从最小的大小开始循环，直到行上的数字总数，这样就能生成不同大小的子字符串。

一个collections.Counter()对象可以用来记录出现次数：

from collections import Counter
from itertools import islice

def window(seq, n=2):
    "Returns a sliding window (of width n) over data from the iterable"
    "   s -> (s0,s1,...s[n-1]), (s1,s2,...,sn), ...                   "
    it = iter(seq)
    result = tuple(islice(it, n))
    if len(result) == n:
        yield result    
    for elem in it:
        result = result[1:] + (elem,)
        yield result

minimum_size = 2
counts = Counter()

with open(filename) as infh:
    for line in infh:
        parts = line.strip().split('-')
        # count substrings of various sizes
        counts.update('-'.join(sp) 
                      for size in range(minimum_size, len(parts) + 1)
                      for sp in window(parts, size))

然后，使用Counter.most_common()方法可以得到一个按频率排序的子字符串列表：

for substring, count in counts.most_common():
    print '{:<20} {:>3d} times'.format(substring, count)

对于你的示例数据，前10个条目是：

6-6                    5 times
6-6-1                  3 times
2-6                    3 times
6-1                    3 times
2-6-6                  2 times
1-8                    2 times
6-1-8                  2 times
6-6-1-8                2 times
2-6-6-1                2 times
18-24-2-6-6            1 times

如果你想关注不同的最小子字符串长度，就不需要重新计算整个文件。你可以直接过滤这个Counter对象；计算键中-字符的数量：

for substr, freq in counts.most_common():
    if substr.count('-') < 2:
        # skip substrings shorter than 3 elements
        continue