Python pandas 计算子字符串的唯一字符串源的数量

Question

假设我有一个包含 5 个字符串的列表，例如:

AAAAB
BBBBA
BBBBA
ABBBB

我想找到并计算每个可能的 4 个字符的子字符串，并跟踪它们来自的唯一 5 个字符串的数量。这意味着虽然 BBBB 在三个不同的字符串来源中找到，但只有两个独特的来源。
示例输出:

    substring    repeats    unique sources
0     AAAA          1              1
1     AAAB          1              1
2     BBBB          3              2
3     BBBA          2              1
4     ABBB          1              1

我已经设法仅使用 Python、一个更新的字典和两个用于比较现有子字符串和全长字符串的列表来小规模地做到这一点。但是，当将其应用于我的完整数据集(约 160 000 个全长字符串(12 个字符)产生 1.5 亿个子字符串(4 个字符))时，常量字典更新和列表比较过程太慢(我的脚本现在已经运行了一个星期)。
在 Python 和 Pandas 中，计算所有全长字符串中存在的子字符串数量都可以轻松且廉价地完成。
所以我的问题是:如何有效地计算和更新 DataFrame 中子字符串的唯一全长源的计数？

Answer 1

TLDR :对于您描述的数据规模，这是在我的计算机上估计需要大约 2 小时的尝试。

import numpy as np
import pandas as pd

def substring_search(fullstrings, sublen=4):
    '''
    fullstrings: array like of strings
    sublen: length of substring to search
    '''
    # PART 1: FIND SUBSTRINGS

    # length of full strings, assumes all are same
    strsize = len(fullstrings[0])

    # get unique strings, # occurences
    strs, counts = np.unique(fullstrings, return_counts=True)
    fullstrings = pd.DataFrame({'string':strs,
                                'count':counts})
    unique_n = len(fullstrings)

    # create array to hold substrings
    substrings = np.empty(unique_n * (strsize - sublen + 1), dtype=str)
    substrings = pd.Series(substrings)

    # slice to find each substring
    c = 0
    while c + sublen <= strsize:
        sliced = fullstrings['string'].str.slice(c, c+sublen)
        s = c * unique_n
        e = s + unique_n
        substrings[s: e] = sliced
        c += 1

    # take the set of substrings, save in output df
    substrings = np.unique(substrings)
    output = pd.DataFrame({'substrings':substrings,
                           'repeats': 0,
                           'unique_sources': 0})

    # PART 2: CHECKING FULL STRINGS FOR SUBSTRINGS

    for i, s in enumerate(output['substrings']):
        # check which fullstrings contain each substring
        idx = fullstrings['string'].str.contains(s)
        count = fullstrings['count'][idx].sum()
        output.loc[i, 'repeats'] = count
        output.loc[i, 'unique_sources'] = idx.sum()
    print('Finished!')

    return output

应用于您的示例:

>>> example = ['AAAAB', 'BBBBA', 'BBBBA', 'ABBBB']
>>> substring_search(example)

  substrings  repeats  unique_sources
0       AAAA        1               1
1       AAAB        1               1
2       ABBB        1               1
3       BBBA        2               1
4       BBBB        3               2

解释
上面代码的基本思想是遍历所有唯一的子字符串，并且(对于它们中的每一个)使用 pandas 检查完整字符串列表。 str方法。这节省了一个 for 循环(即您不会为每个子字符串遍历每个完整字符串)。另一个想法是只检查唯一的完整字符串(除了唯一的子字符串)；您事先保存每个完整字符串的出现次数并在最后更正计数。
基本结构是:

获取输入中的唯一字符串，并记录每个字符串出现的次数。

查找输入中所有唯一的子字符串(我使用 pandas.Series.str.slice 执行此操作)

循环每个子串，并使用 pandas.Series.str.contains 以(元素方式)检查完整的字符串。由于这些是唯一的并且我们知道每个发生的次数，我们可以同时填写 repeats和 unique_sources .

测试
这是我用来创建更大输入数据的代码:

n = 100
size = 12

letters = list(string.ascii_uppercase[:20])
bigger = [''.join(np.random.choice(letters, size)) for i in range(n)]

所以 bigger是 n size -长度字符串:

['FQHMHSOIEKGO',
 'FLLNCKAHFISM',
 'LDKKRKJROIRL',
 ...
 'KDTTLOKCDMCD',
 'SKLNSAQQBQHJ',
 'TAIAGSIEQSGI']

使用打印进度的修改代码(在下面发布)，我尝试使用 n=150000和 size=12 ，并得到这个初始输出:

Starting main loop...
5%, 344.59 seconds
10.0%, 685.28 seconds

所以 10 * 685 秒/60(秒/分钟)= ~114 分钟 .所以 2 小时并不理想，但实际上比 1 周更有用。我不怀疑有一些更聪明的方法可以做到这一点，但如果没有发布其他内容，这可能会有所帮助。
如果您确实使用了此代码，您可能需要使用一些较小的示例来验证结果是否正确。我不确定的一件事是，您是要计算一个子字符串是否只出现在每个完整字符串中(即 contains )，还是您想要它出现在完整字符串中的次数(即 count )。至少希望这是一个小的改变。
这是在进行搜索时打印进度的附加代码； #PART 2 中只有其他语句:

def substring_search_progress(fullstrings, sublen=4):
    '''
    fullstrings: array like of strings
    sublen: length of substring to search
    '''
    # PART 1: FIND SUBSTRINGS

    # length of full strings, assumes all are same
    strsize = len(fullstrings[0])

    # get unique strings, # occurences
    strs, counts = np.unique(fullstrings, return_counts=True)
    fullstrings = pd.DataFrame({'string':strs,
                                'count':counts})
    unique_n = len(fullstrings)

    # create array to hold substrings
    substrings = np.empty(unique_n * (strsize - sublen + 1), dtype=str)
    substrings = pd.Series(substrings)

    # slice to find each substring
    c = 0
    while c + sublen <= strsize:
        sliced = fullstrings['string'].str.slice(c, c+sublen)
        s = c * unique_n
        e = s + unique_n
        substrings[s: e] = sliced
        c += 1

    # take the set of substrings, save in output df
    substrings = np.unique(substrings)
    output = pd.DataFrame({'substrings':substrings,
                           'repeats': 0,
                           'unique_sources': 0})

    # PART 2: CHECKING FULL STRINGS FOR SUBSTRINGS

    # for marking progress
    total = len(output)
    every = 5
    progress = every

    # main loop
    print('Starting main loop...')
    start = time.time()
    for i, s in enumerate(output['substrings']):

        # progress
        if (i / total * 100) > progress:
            now = round(time.time() - start, 2)
            print(f'{progress}%, {now} seconds')
            progress = (((i / total * 100) // every) + 1) * every

        # check which fullstrings contain each substring
        idx = fullstrings['string'].str.contains(s)
        count = fullstrings['count'][idx].sum()
        output.loc[i, 'repeats'] = count
        output.loc[i, 'unique_sources'] = idx.sum()
    print('Finished!')

    return output