Существует ли встроенная функция или модуль, который выбирает несколько фраз из списка, который содержит перекрывающееся слово, а затем сохраняет только самую длинную фразу?

Question

Я уже посмотрел некоторые форумы здесь, но ничего, что конкретно относится к моей проблеме. У меня есть список:

listofwords = ['rick','rick sanchez','morty','morty smith sanchez','morty smith']

, и моя цель состоит в том, чтобы создать новый список с удаленными более короткими перекрывающимися словами, например:

newlist = ['rick sanchez', 'morty smith sanchez']

Я написал следующее:

def count_substring(string, sub_string):
    count = 0
    for pos in range(len(string)):
        if string[pos:].startswith(sub_string):
            count += 1
    return count

listofwords = ['rick','rick sanchez','morty','morty smith sanchez','morty smith']
keeper = []
for i in listofwords:
    storage = ''
    for j in listofwords[1:]:
        if count_substring(j,i) == 1:
            if len(j) > len(i):
                storage = j
            elif len(i) > len(j):
                storage = i
            else:
                pass
    keeper.append(storage)

print keeper

и результат был:

['rick sanchez', '', 'morty smith', '', 'morty smith sanchez']

, который был довольно близок к тому, к чему я стремился, за исключением того факта, что мне нужно сделать процесс для другого раунда и чистого вверх по списку.

Пожалуйста, помогите мне, есть ли встроенный модуль, предназначенный для такого рода организации списка?

Answer 1

Вот функция с некоторыми basi c короткозамкнутыми логами c, чтобы сделать все это дело более производительным:

def remove_substrings(words):
    output_words = []
    for ind, word in enumerate(words):
        if not any(word in output_word for output_word in output_words):
            if not any(word in words[i] for i in range(ind + 1, len(words))):
                output_words.append(word)
    return output_words

words = ['rick','rick sanchez','morty','morty smith sanchez','morty smith']

print(remove_substrings(words))
print(remove_substrings(["rick"] * 2))
print(remove_substrings(["rick"] * 20000))
print(remove_substrings([*["rick"] * 10000, *["morty"] * 10000]))
print(remove_substrings([w for _ in range(10000) for w in ["rick", "morty"]]))
print(list(map(len, remove_substrings(["a" * i for i in range(10000)]))))
print(list(map(len, remove_substrings(["rick" * i for i in range(10000)]))))
print(list(map(len, remove_substrings(["a" * (10000 - i) for i in range(10000)]))))
print(list(map(len, remove_substrings(["rick" * (10000 - i) for i in range(10000)]))))

Это имеет ожидаемый результат,

['rick sanchez', 'morty smith sanchez']
['rick']
['rick']
['rick', 'morty']
['rick', 'morty']
[9999]
[39996]
[10000]
[40000]

в вполне разумное время.

Его поведение в крайнем случае, когда у вас есть повторяющийся элемент, состоит в том, чтобы сохранить один из этого элемента, который, я думаю, является последовательным способом поведения. Вы можете изменить это, чтобы вести себя по-другому, если хотите.

Идея в том, что если мы ранее отклонили слово, нам не нужно будет снова его рассматривать, так как оно было отклонено на основании либо слово, которое мы уже пометили как правильное, или слово после него, оба из которых имеют это слово в качестве подстроки, поэтому они оба будут работать над отклонением других невозможных кандидатов.

Важно, что использование Функция any с выражениями-генераторами также означает, что как только она находит слово, под которым находится текущее слово, она прекращает поиск таких слов. Такое короткое замыкание делает его еще быстрее.

Я не сомневаюсь, что можно сделать гораздо больше оптимизаций. Почти наверняка есть какая-то древовидная структура, которая в некоторой степени уменьшает временную сложность, но я думаю, что это неплохое начало.

Answer 2

Как говорится в комментариях, это довольно специфично c, возможно, оно не встроено, но вот один вкладыш, который вычисляет то, что вы хотите.

[word for word in listofwords if sum([word in a for a in listofwords]) <= 1]

Возвращает

['rick sanchez', 'morty smith sanchez']

Вот краткое описание. Внешний l oop проходит через каждое слово и выбирает его только на основе условия. Условие здесь состоит в том, что слово не является частью какого-либо другого слова в списке. Если слово является частью другого слова, то сумма будет больше 1. Таким образом, мы не выбираем его.

Надеюсь, это поможет! Позвольте мне знать, если у вас есть какие-либо вопросы.