Удалите подстроки внутри списка лучше, чем O (n ^ 2) сложности

У меня есть список со многими словами (100. 000+), и я хотел бы удалить все подстроки каждого слова в списке.

Поэтому для простоты предположим, что у меня есть следующий список:

words = ['Hello', 'Hell', 'Apple', 'Banana', 'Ban', 'Peter', 'P', 'e']

Требуется следующий вывод:

['Hello', 'Apple', 'Banana', 'Peter']

'Hell' был удален, потому что это подстрока 'Hello'
'Ban' был удален, потому что это подстрока 'Banana'
'P' был удален, потому что это подстрока 'Peter'
'e' был удален, потому что это подстрока 'Hello', 'Hell', 'Apple' и т.д.

Что я сделал

Это мой код, но мне интересно, есть ли более эффективный способ, чем эти вложенные методы.

to_remove = [x for x in words for y in words if x != y and x in y]
output = [x for x in words if x not in to_remove]

Как я могу улучшить производительность? Должен ли я использовать regex?

Ответ 1

@wim является правильным.

Учитывая алфавит фиксированной длины, следующий алгоритм является линейным по всей длине текста. Если алфавит имеет неограниченный размер, тогда он будет O(n log(n)). В любом случае это лучше, чем O(n^2).

Create an empty suffix tree T.
Create an empty list filtered_words
For word in words:
    if word not in T:
        Build suffix tree S for word (using Ukkonen algorithm)
        Merge S into T
        append word to filtered_words

Ответ 2

Сначала создайте набор всех (уникальных) подстрок, затем отфильтруйте слова с ним:

def substrings(s):
    length = len(s)
    return {s[i:j + 1] for i in range(length) for j in range(i, length)} - {s}


def remove_substrings(words):
    subs = set()
    for word in words:
        subs |= substrings(word)

    return set(w for w in words if w not in subs)

Ответ 3

Вы можете сортировать данные по длине, а затем использовать список:

words = ['Hello', 'Hell', 'Apple', 'Banana', 'Ban', 'Peter', 'P', 'e']
new_words = sorted(words, key=len, reverse=True)
final_results = [a for i, a in enumerate(new_words) if not any(a in c for c in new_words[:i])]

Выход:

['Banana', 'Hello', 'Apple', 'Peter']

Ответ 4

Обратите внимание, что использование for в пионе вообще медленное (вы можете использовать массивы numpy или пакет NLP), кроме этого, как насчет этого:

words = list(set(words))#elimnate dublicates
str_words = str(words)
r=[]
for x in words:
    if str_words.find(x)!=str_words.rfind(x):continue
    else:r.append(x)
print(r)

как я отвечаю здесь, я не вижу причины, почему c++ не был бы вариантом