检查字符串中的字符串

Question

我有一个包含许多字符串的巨大列表:

['xxxx','xx','xy','yy','x',......]

现在我正在寻找一种有效的方法来删除另一个字符串中存在的所有字符串.例如'xx''x'适合'xxxx'.

由于数据集很大,我想知道旁边是否有一种有效的方法

if a in b:

完整的代码:可能有一些优化部分:

for x in range(len(taxlistcomplete)):
if delete == True:
    x = x - 1
    delete = False
for y in range(len(taxlistcomplete)):
    if taxlistcomplete[x] in taxlistcomplete[y]:
        if x != y:
            print x,y
            print taxlistcomplete[x]
            del taxlistcomplete[x]
            delete = True
            break
    print x, len(taxlistcomplete)

代码的更新版本:

for x in enumerate(taxlistcomplete):
if delete == True:
    #If element is removed, I need to step 1 back and continue looping.....
    delete = False
for y in enumerate(taxlistcomplete):
    if x[1] in y[1]:
        if x[1] != y[1]:
            print x[1],y[1]
            print taxlistcomplete[x]

            del taxlistcomplete[x[0]]
            delete = True
            break
print x, len(taxlistcomplete)

现在使用枚举实现,只是现在我想知道这是否更有效以及如何实现删除步骤,所以我也少搜索.

只是一个短暂的想法......

基本上我想看到的......

如果element与list中的任何其他元素都不匹配,请将此文件写入文件.因此,如果'xxxxx'不在'xx','xy','wfirfj'等...打印/保存

一个新的简单版本,因为我不认为我可以进一步优化它...

print 'comparison'

file = open('output.txt','a')

for x in enumerate(taxlistcomplete):
    delete = False
    for y in enumerate(taxlistcomplete):
        if x[1] in y[1]:
            if x[1] != y[1]:
                taxlistcomplete[x[0]] = ''
                delete = True
                break
    if delete == False:
        file.write(str(x))

Answer 1

x in <string>很快,但是检查列表中所有其他字符串的每个字符串将花费O(n ^ 2)时间.通过优化比较而不是削减几个周期,您可以通过使用不同的数据结构实现巨大的节省,这样您就可以在一次查找中检查每个字符串:对于两千个字符串,这是两千个检查而不是四百万个.

有一个称为"前缀树"(或trie)的数据结构,它允许您非常快速地检查字符串是否是您之前看到的某个字符串的前缀.谷歌一下.因为你也对在另一个字符串中间出现的字符串感兴趣x,所以索引表单的所有子字符串x, x[1:], x[2:], x[3:],等(所以:只有n字符串表示长度的字符串n).也就是说,您索引从位置0,1,2等开始的子串,并继续到字符串的结尾.这样您就可以检查新字符串是否是索引中某些内容的初始部分.

然后,您可以在O(n)时间内解决您的问题,如下所示:

1. 按照长度递减的顺序排序字符串.这可以确保没有字符串可以是您尚未看到的东西的子字符串.由于您只关心长度,因此可以在O(n)时间内进行铲斗排序.

2. 从空的前缀树开始,循环遍历有序的字符串列表.对于每个字符串x,使用前缀树来检查它是否是您之前看到的字符串的子字符串.如果没有,请将其子字符串x, x[1:], x[2:]等添加到前缀树中.

在长列表中间删除非常昂贵,因此如果您将要保留的字符串收集到新列表中,您将获得进一步的加速(实际字符串不会被复制,只是参考).完成后,删除原始列表和前缀树.

如果这对你来说太复杂了,至少不要把所有东西都比作一切.按大小对字符串进行排序(按递减顺序排序),并仅检查每个字符串与之前的字符串.这将为您提供50%的加速,而且只需很少的努力.并创建一个新列表(或立即写入文件)而不是删除到位.