Encontrar várias substrings em uma string sem iterar várias vezes

Question

Preciso descobrir se os itens de uma lista aparecem em uma string e, em seguida, adicionar os itens a uma lista diferente. Este código funciona:

data =[]
line = 'akhgvfalfhda.dhgfa.lidhfalihflaih**Thing1**aoufgyafkugafkjhafkjhflahfklh**Thing2**dlfkhalfhafli...'
_legal = ['thing1', 'thing2', 'thing3', 'thing4',...] 
for i in _legal:
    if i in line:
        data.append(i)

No entanto, o código itera line(o que pode ser longo) várias vezes - quantas vezes houver item _legal(o que pode ser muito ). Isso é muito lento para mim e estou procurando uma maneira de fazer isso mais rápido. linenão tem nenhum formato específico, então usar .split()não funcionou, pelo que eu sei. Edit: alterado linepara que represente melhor os problemas.

Answer 1

Uma maneira que eu poderia pensar para melhorar é:

• Obtenha todos os comprimentos exclusivos das palavras em _legal
• Construa um dicionário de palavras linedesses comprimentos específicos usando uma técnica de janela deslizante. A complexidade deve ser O( len(line)*num_of_unique_lengths ), isso deve ser melhor do que força bruta.
• Agora procure cada um thingno dicionário em O (1).

Código:

line = 'thing1 thing2 456 xxualt542l lthin. dfjladjfj lauthina '
_legal = ['thing1', 'thing2', 'thing3', 'thing4', 't5', '5', 'fj la']
ul = {len(i) for i in _legal}
s=set()
for l in ul:
    s = s.union({line[i:i+l] for i in range(len(line)-l)})
print(s.intersection(set(_legal)))

Resultado:

{'thing1', 'fj la', 'thing2', 't5', '5'}

Answer 2

Uma abordagem é construir um padrão regex muito simples e usar re.findall()para encontrar / extrair quaisquer palavras correspondentes na string.

import re

line = 'akhgvfalfhda.dhgfa.lidhfalihflaih**Thing1**aoufgyafkugafkjhafkjhflahfklh**Thing2**dlfkhalfhafli...'
_legal = ['thing1', 'thing2', 'thing3', 'thing4']

exp = re.compile(r'|'.join(_legal), re.IGNORECASE)
exp.findall(line)

>>> ['Thing1', 'Thing2']

Answer 3

O seguinte deve funcionar de forma bastante eficiente. Ele implementa a sugestão de @SomeDude dada acima

lens=set([len(i) for i in _legal])
d={}
for k in lens:
    d[k]=[line[i:i+k] for i in range(len(line)-k)]
s=set(sum(d.values(), []))
result=list(s.intersection(set(_legal)))

para os dados a seguir (eu mudei "linha" um pouco, pois ela retornou uma lista vazia devido ao uppecase em Thing1 e Thing2)

line = 'akhgvfalfhda.dhgfa.lidhfalihflaih**thing1**aoufgyafkugafkjhafkjhflahfklh**thing2**dlfkhalfhafli...'
_legal = ['thing1', 'thing2', 'thing3', 'thing4',...]

O resultado é:

print(result)

['thing2', 'thing1']

Explicação: Salvamos todos os comprimentos possíveis das palavras em substrings. Para esses comprimentos, criamos todas as substrings possíveis em texto (conjuntos). Por fim, encontramos itens comuns em se substrings, que é a resposta à pergunta.