从字符串列表中删除重叠较短的字符串

Question

我有一个字符串列表：mylist = ["Hanks", "Tom Hanks","Tom","Tom Can"]，我需要删除列表中是另一个字符串的子字符串的较短字符串。

例如，在上面的情况下，输出应为：["Tom Hanks","Tom Can"]。

我在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)            

代码运行正常。我该如何使其更高效？

- Jesujoba Oluwadara ALABI

---

一个方法是，一旦在迭代中 noexist 为假，您就可以停止将其与列表的剩余部分进行比较，因此在内部循环中加入 if not noexist: break 将带来一些好处。不确定是否还有更多可以改进。 - Tadhg McDonald-Jensen

输出的顺序是否重要？ - Ehsan

嗨@TadhgMcDonald-Jensen，我也想到了类似的东西。我认为你在你的答案中表达的是一个相近的思路。 - Jesujoba Oluwadara ALABI

@Ehsan，输出顺序无关紧要 - Jesujoba Oluwadara ALABI

@JesujobaALABI，在您发表评论之前，我已经在我的帖子中添加了两个版本：）。请随意使用最适合您应用程序的版本。谢谢。 - Ehsan

@Ehsan，很酷！谢谢。 - Jesujoba Oluwadara ALABI

Answer 1

• If order in output does not matter (replace ',' character with a character that doesn't occur in strings of your list):

  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)
  

  list comprehension alternative (less readable):

  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:])]
  

  output:

  ['Tom Can', 'Tom Hanks']
  

• And if you want to keep the order:

  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]
  

  output:

  ['Tom Hanks', 'Tom Can']
  

- Ehsan

---

如果任何字符串包含“，”，则技术上可能会出现问题。此外，这也假设子字符串出现在字符串的开头，以确保在排序后它肯定存在于后面的字符串中，例如列表["Hanks Tom", "Tom"]无法删除"Tom"。 - Tadhg McDonald-Jensen

@TadhgMcDonald-Jensen 分隔符可以根据应用程序进行调整。您始终可以选择一个您确定不会出现在列表中的字符。至于排序，已包含在帖子中的按字符串长度排序会处理这个问题。 - Ehsan

啊，排序时错过了“key”，是的，这就做到了。绕过分隔符的方法可能是执行if not any(map(x.__contains__, mylist[i+1:])或者更详细的版本。不确定它在性能方面如何比较。你正在制作许多列表切片，这并不理想。 - Tadhg McDonald-Jensen

@TadhgMcDonald-Jensen 你是正确的。我最初也这样想，它速度较慢。这基本上会创建一个双重循环（甚至比使用 map 更慢）。然而，如果你无法确定分隔符，你的建议是正确的。谢谢。 - Ehsan

Answer 2

看这个能否帮到你。根据问题示例列表添加了答案：

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打印语句，以便遍历并检查条件。

- Avinash Dalvi

---

这会在迭代列表时删除其中的元素，如果不跳过由于在迭代时删除它们而删除的一些元素，则会删除所有元素。 - Tadhg McDonald-Jensen

尝试使用任何其他元素顺序，例如 mylist = list(range(10))，你的代码基本上只是删除每个第二个元素。 - Tadhg McDonald-Jensen

或者，为了进一步说明逻辑本身是有缺陷的，请尝试 [a for a in mylist if a not in mylist]。这将每次产生一个空列表，因为逻辑是“对于mylist中的每个元素，检查它是否在mylist中。如果是，则跳过它。” - C.Nivs

添加了不同的方法来找出问题。请检查并给予反馈。@C.Nivs - Avinash Dalvi

添加了不同的方法来找出问题。请检查并给予反馈。@TadhgMcDonald-Jensen - Avinash Dalvi

Answer 3

一种不改变整体算法的小改进是，一旦找到另一个包含当前元素的元素，则可以跳出内部循环，因为此后它将被跳过。

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)

- Tadhg McDonald-Jensen

---

我说这并不是什么很大的改进，因为 OP 要求性能提高到 O(n^2) 复杂度。 - Tadhg McDonald-Jensen

好的。谢谢您点赞并提供帮助。 - Avinash Dalvi

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算法进行改进，其中您将为所有条目构建模式，并将其与所有输入进行匹配，并丢弃任何具有多个匹配项的模式。这在理论上可能是线性时间复杂度。

- Cireo