python - Python pandas 计算子字符串的唯一字符串源的数量
问题描述
假设我有一个包含 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)]
-length 字符串bigger
也是如此:n
size
['FQHMHSOIEKGO',
'FLLNCKAHFISM',
'LDKKRKJROIRL',
...
'KDTTLOKCDMCD',
'SKLNSAQQBQHJ',
'TAIAGSIEQSGI']
使用打印进度的修改代码(发布在下面),我尝试了n=150000
and 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
推荐阅读
- jquery - jquery库之间的兼容性问题
- python - 如何在 django-cms 中添加背景图片?
- python - 如何在循环中随机编辑 pcap 文件中的一个字节并且仍然有效?
- c# - 如何使 SQLiteConnection 对象可用于另一种方法?
- css - 将 Bootstrap 4 添加到项目导致以 em 测量的尺寸折叠
- node.js - 错误:连接 ECONNREFUSED 127.0.0.1:3003 Docker 容器
- java - Java Blowfish CBC 解密 javax.crypto.BadPaddingException:垫块损坏
- karate - 如果响应本身有,如何在空手道框架中提取 xml 响应
标记在里面 - java - 调整 JFrame 大小后更新 JFreeChart/JPanel
- sql-server - 如何在 SQL Server、WPF、C# 中的每个数据条目上检查重复项并删除它们?