以最小编辑距离时间效率创建高nr随机序列

2024-03-29 11:44:21 发布

您现在位置:Python中文网/ 问答频道 /正文

我需要创建一个程序/脚本来创建大量随机序列(基于4个不同字母的20个字母长的序列),所有序列之间的编辑距离最小。”“高”在这里至少是10万个序列,但如果可能的话可以达到100万个。你知道吗

我从一个简单的方法开始,只生成随机的20个字母的序列,对于每个序列,计算序列和所有其他已经创建和存储的序列之间的编辑距离。如果新序列通过了我的阈值,则存储它,否则丢弃它。你知道吗

正如您所了解的,对于更高数量的序列,这种扩展非常糟糕。高达10公里是合理的罚款,但试图得到10万这开始变得麻烦。你知道吗

我真的只需要创建一次序列并存储输出,所以我真的不太在意速度,但以现在的速度赚100万是不可能的。你知道吗

一直在想办法加快这个过程,比如构建序列是“块”的最小ED然后合并,但是还没有想出任何解决方案。你知道吗

想知道,有没有人有什么聪明的想法/方法可以用最少的时间和更高效的时间来创建如此多的序列?你知道吗

干杯, 接线盒


Tags: 方法程序脚本编辑距离数量过程字母
1条回答
网友
1楼 · 发布于 2024-03-29 11:44:21

从维基百科看来,编辑距离是三种操作之一:插入、删除、替换;在起始字符串上执行。为什么不系统地从一个开始的字符串生成最多N个编辑的所有字符串,然后在达到限制时停止?你知道吗

不需要检查实际的编辑距离,因为它们在生成时是正确的。对于随机性,您可以生成一个数字,然后将它们洗牌。你知道吗

相关问题 更多 >