Check if string in strings

Question

I have a huge list containing many strings like:

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

Now I am looking for an efficient way that removes all strings that are present within another string. For example 'xx' 'x' fit in 'xxxx'.

As the dataset is huge, I was wondering if there is an efficient method for this beside

if a in b:

The complete code: With maybe some optimization parts:

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)

An updated version of the code:

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)

Now implemented with the enumerate, only now I am wondering if this is more efficient and howto implement the delete step so I have less to search in as well.

Just a short thought...

Basically what I would like to see...

if element does not match any other elements in list write this one to a file. Thus if 'xxxxx' not in 'xx','xy','wfirfj',etc... print/save

A new simple version as I dont think I can optimize it much further anyway...

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> is fast, but checking each string against all other strings in the list will take O(n^2) time. Instead of shaving a few cycles by optimizing the comparison, you can achieve huge savings by using a different data structure so that you can check each string in just one lookup: For two thousand strings, that's two thousand checks instead of four million.

There's a data structure called a "prefix tree" (or trie) that allows you to very quickly check whether a string is a prefix of some string you've seen before. Google it. Since you're also interested in strings that occur in the middle of another string x, index all substrings of the form x, x[1:], x[2:], x[3:], etc. (So: only n substrings for a string of length n). That is, you index substrings that start in position 0, 1, 2, etc. and continue to the end of the string. That way you can just check if a new string is an initial part of something in your index.

You can then solve your problem in O(n) time like this:

1. Order your strings in order of decreasing length. This ensures that no string could be a substring of something you haven't seen yet. Since you only care about length, you can do a bucket sort in O(n) time.

2. Start with an empty prefix tree and loop over your ordered list of strings. For each string x, use your prefix tree to check whether it is a substring of a string you've seen before. If not, add its substrings x, x[1:], x[2:] etc. to the prefix tree.

Deleting in the middle of a long list is very expensive, so you'll get a further speedup if you collect the strings you want to keep into a new list (the actual string is not copied, just the reference). When you're done, delete the original list and the prefix tree.

If that's too complicated for you, at least don't compare everything with everything. Sort your strings by size (in decreasing order), and only check each string against the ones that have come before it. This will give you a 50% speedup with very little effort. And do make a new list (or write to a file immediately) instead of deleting in place.

Answer 2

Here is a simple approach, assuming you can identify a character (I will use '$' in my example) that is guaranteed not to be in any of the original strings:

result = ''
for substring in taxlistcomplete:
    if substring not in result: result += '$' + substring
taxlistcomplete = result.split('$')

This leverages Python's internal optimizations for substring searching by just making one big string to substring-search :)