Удалить короткую перекрывающуюся строку из списка строк

Question

У меня есть список строк: mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"], мне нужно удалить более короткие строки, которые являются подстрокой другой строки в списке.

Например, в приведенном выше случае вывод должен быть: ["Tom Хэнкс »,« Том Кан »].

То, что я сделал в python:

mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
newlst = []
for x in mylist:
    noexist = True
    for j in mylist:
        if x==j:continue
        noexist = noexist and not(x in j)         
    if (noexist==True):
        newlst.append(x)
print(newlst)            

Код работает нормально. Как сделать его эффективным?

Answer 1

• Если порядок вывода не имеет значения (замените символ ',' символом, который не встречается в строках вашего списка):

  mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
  mylist.sort(key = len)
  newlst = []
  for i,x in enumerate(mylist):
      if x not in ','.join(mylist[i+1:]):
          newlst.append(x)
  

  альтернатива понимания списка ( менее читабельно):

  mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
  mylist.sort(key = len)
  newlst = [x for i,x in enumerate(mylist) if x not in ','.join(mylist[i+1:])]
  

  вывод:

  ['Tom Can', 'Tom Hanks']
  

• И если хотите сохранить порядок:

  mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
  mylist_sorted = mylist.copy()
  mylist_sorted.sort(key = len)
  newlst = [x for i,x in enumerate(mylist_sorted) if x not in ','.join(mylist_sorted[i+1:])]
  newlst = [x for x in mylist if x in newlst]
  

  вывод:

  ['Tom Hanks', 'Tom Can']
  

Answer 2

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

mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
newlist = []
for elem in mylist:
    for candidate in mylist:
        if elem == candidate:
            continue
        elif elem in candidate:
            break
    else:
        newlist.append(elem)

print(newlist)

Answer 3

Смотрите, это может вам помочь. Добавлен ответ на основе списка примеров вопросов:

mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]
newlist = []
newstring = "|".join(mylist)
for a in mylist:
    if newstring.count(a) == 1:
        print("Big string: ",a)
        newlist.append(a)
    else:
        print("Small String: ",a) 

print(newlist)

Добавлен оператор if else для печати, как его пересечение и условие проверки.

Answer 4

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

from collections import Counter

items = ["Hanks", "Tom Hanks","Tom","Tom Can"]
items = set(items)  # Don't want to think about uniqueness
item_words = {}  # {item: all_words}
word_counts = Counter()  # {word: item_counts}
word_lookups = {}  # {word: {all_words: {item, ...}, ...}, ...}
for item in items:
    words = frozenset(item.split())
    item_words[item] = words
    for word in words:
        word_lookups.setdefault(word, {}).setdefault(words, set()).add(item)
        word_counts[word] += 1

def is_ok(item):
    words = item_words[item]
    min_word = min(words, key=word_counts.__getitem__)
    if word_counts[min_word] == 1:
        return True  # This item has a unique word
    for all_words, others in word_lookups[min_word].items():
        if not words.issubset(all_words):
            continue  # Not all words present
        for other in others:
            if item == other:
                continue  # Don't remove yourself
            if item in other:
                return False
    return True  # No matches

final = [item for item in items if is_ok(item)]

Если вы хотите быть очень быстрым, рассмотрите вариант алгоритма Aho – Corasick , в котором вы должны построить шаблоны для всех ваших записей и сопоставить их со всеми вашими входными данными и отбросить любые шаблоны, которые имеют более одного совпадения. Это потенциально может быть линейным во времени.