Python pandas 计算子字符串的唯一字符串源的数量
Python pandas counting the number of unique string sources for substrings
假设我有一个包含 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 中子字符串的唯一全长源的计数？
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 (seconds/minute) = ~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
假设我有一个包含 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 中子字符串的唯一全长源的计数？
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 (seconds/minute) = ~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