Фильтровать список строк, игнорируя подстроки других элементов

Ответ 1

Простым квадратичным решением будет следующее:

res = []
n = len(lst)
for i in xrange(n):
    if not any(i != j and lst[i] in lst[j] for j in xrange(n)):
        res.append(lst[i])

Но мы можем сделать гораздо лучше:

Пусть $ - символ, который не отображается ни в одной из ваших строк, и имеет меньшее значение, чем все ваши фактические символы.

Пусть S будет конкатенацией всех ваших строк, с $ между ними. В вашем примере S = a$abc$b$d$xy$xyz.

Вы можете построить массив суффикса массива S в линейном времени. Вы также можете использовать гораздо более простой алгоритм построения O (n log ^ 2 n), который я описал в другом ответе.

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

С запрограммированной информацией LCP это можно сделать и в линейном времени.

Пример O (n log ^ 2 n), адаптированный из моего массива суффиксов:

def findFirst(lo, hi, pred):
  """ Find the first i in range(lo, hi) with pred(i) == True.
  Requires pred to be a monotone. If there is no such i, return hi. """
  while lo < hi:
    mid = (lo + hi) // 2
    if pred(mid): hi = mid;
    else: lo = mid + 1
  return lo

# uses the algorithm described in /questions/293090/rank-the-suffixes-of-a-list/1445922#1445922
class SuffixArray(object):
  def __init__(self, s):
    """ build the suffix array of s in O(n log^2 n) where n = len(s). """
    n = len(s)
    log2 = 0
    while (1<<log2) < n:
      log2 += 1
    rank = [[0]*n for _ in xrange(log2)]
    for i in xrange(n):
      rank[0][i] = s[i]
    L = [0]*n
    for step in xrange(1, log2):
      length = 1 << step
      for i in xrange(n):
        L[i] = (rank[step - 1][i],
                rank[step - 1][i + length // 2] if i + length // 2 < n else -1,
                i)
      L.sort()
      for i in xrange(n):
        rank[step][L[i][2]] = \
          rank[step][L[i - 1][2]] if i > 0 and L[i][:2] == L[i-1][:2] else i
    self.log2 = log2
    self.rank = rank
    self.sa = [l[2] for l in L]
    self.s = s
    self.rev = [0]*n
    for i, j in enumerate(self.sa):
      self.rev[j] = i

  def lcp(self, x, y):
    """ compute the longest common prefix of s[x:] and s[y:] in O(log n). """
    n = len(self.s)
    if x == y:
      return n - x
    ret = 0
    for k in xrange(self.log2 - 1, -1, -1):
      if x >= n or y >= n:
        break
      if self.rank[k][x] == self.rank[k][y]:
        x += 1<<k
        y += 1<<k
        ret += 1<<k
    return ret

  def compareSubstrings(self, x, lx, y, ly):
    """ compare substrings s[x:x+lx] and s[y:y+yl] in O(log n). """
    l = min((self.lcp(x, y), lx, ly))
    if l == lx == ly: return 0
    if l == lx: return -1
    if l == ly: return 1
    return cmp(self.s[x + l], self.s[y + l])

  def count(self, x, l):
    """ count occurences of substring s[x:x+l] in O(log n). """
    n = len(self.s)
    cs = self.compareSubstrings
    lo = findFirst(0, n, lambda i: cs(self.sa[i], min(l, n - self.sa[i]), x, l) >= 0)
    hi = findFirst(0, n, lambda i: cs(self.sa[i], min(l, n - self.sa[i]), x, l) > 0)
    return hi - lo

  def debug(self):
    """ print the suffix array for debugging purposes. """
    for i, j in enumerate(self.sa):
      print str(i).ljust(4), self.s[j:], self.lcp(self.sa[i], self.sa[i-1]) if i >0 else "n/a"

def filterSublist(lst):
  splitter = "\x00"
  s = splitter.join(lst) + splitter
  sa = SuffixArray(s)
  res = []
  offset = 0
  for x in lst:
    if sa.count(offset, len(x)) == 1:
      res.append(x)
    offset += len(x) + 1
  return res

Однако накладные расходы интерпретации, вероятно, заставляют это быть медленнее, чем приближение O (n ^ 2), если S действительно велико (порядка 10 ^ 5 символов или более).

Ответ 2

Вы можете создать свою проблему в виде матрицы:

import numpy as np

lst = np.array(["a", "abc", "b", "d", "xy", "xyz"], object)
out = np.zeros((len(lst), len(lst)), dtype=int)
for i in range(len(lst)):
    for j in range(len(lst)):
        out[i,j] = lst[i] in lst[j]

откуда вы получаете out как:

array([[1, 1, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0],
       [0, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 1, 1],
       [0, 0, 0, 0, 0, 1]])

тогда ответ будет индексом lst, где сумма òut вдоль столбцов 1 (строка только сама по себе):

lst[out.sum(axis=1)==1]
#array(['abc', 'd', 'xyz'], dtype=object)

EDIT: Вы можете сделать это гораздо эффективнее:

from numpy.lib.stride_tricks import as_strided
from string import find

size = len(lst)
a = np.char.array(lst)
a2 = np.char.array(as_strided(a, shape=(size, size),
                                 strides=(a.strides[0], 0)))

out = find(a2, a)
out[out==0] = 1
out[out==-1] = 0
print a[out.sum(axis=0)==1]
# chararray(['abc', 'd', 'xyz'], dtype='|S3')

a[out.sum(axis=0)==1]

Ответ 3

Имеет ли смысл порядок? Если нет,

a = ["a", "abc", "b", "d", "xy", "xyz"]

a.sort(key=len, reverse=True)
n = len(a)

for i in range(n - 1):
    if a[i]:
        for j in range(i + 1, n):
            if a[j] in a[i]:
                a[j] = ''


print filter(len, a)  # ['abc', 'xyz', 'd']

Не очень эффективный, но простой.

Ответ 4

O (n) решение:

import collections
def filterSublist1(words):
    longest = collections.defaultdict(str)
    for word in words:                                 # O(n)
        for i in range(1, len(word)+1):                # O(k)
            for j in range(len(word) - i + 1):         # O(k)
                subword = word[j:j+i]                  # O(1)
                if len(longest[subword]) < len(word):  # O(1)
                    longest[subword] = word            # O(1)

    return list(set(longest.values()))                 # O(n)
                                                       # Total: O(nk²)

Объяснение:

Чтобы понять временную сложность, я дал верхнюю оценку сложности в каждой строке в приведенном выше коде. Узкое место встречается в циклах for, где, поскольку они вложены, общая временная сложность будет O(nk²), где n - количество слов в списке, а k - длина среднее/длинное слово (например, в приведенном выше коде n = 6 и k = 3). Однако, считая, что слова не являются произвольно длинными строками, мы можем привязать k к некоторому небольшому значению - например, k=5, если мы рассмотрим среднюю длину слова в английском словаре. Поэтому, поскольку k ограничено значением, оно не включено в временную сложность, и мы получаем время выполнения O(n). Конечно, размер k добавит к постоянному коэффициенту, особенно если k не меньше n. Для английского словаря это означало бы, что когда n >> k² = 25 вы начнете видеть лучшие результаты, чем с другими алгоритмами (см. График ниже).

Алгоритм работает путем сопоставления каждого уникального подслова с самой длинной строкой, содержащей это подслово. Например, 'xyz' будет искать longest['x'], longest['y'], longest['z'], longest['xy'], longest['yz'] и longest['xyz'] и установить их равными 'xyz'. Когда это делается для каждого слова в списке, longest.keys() будет набором всех уникальных подслов всех слов, а longest.values() будет списком только слов, которые не являются подсловами других слов. Наконец, longest.values() может содержать дубликаты, поэтому они удаляются путем переноса в set.

Визуализация сложности времени

Ниже я протестировал алгоритм выше (вместе с вашим оригинальным алгоритмом), чтобы показать, что это решение действительно O(n) при использовании английских слов. Я тестировал это, используя timeit в список из 69000 английских слов. Я назвал этот алгоритм filterSublist1 и ваш исходный алгоритм filterSublist2.

График показан на оси логарифмического журнала, что означает, что временная сложность алгоритма для этого входного набора задается наклоном линий. Для filterSublist1 наклон равен ~ 1, что означает O(n1), а для filterSublist2 наклон равен ~ 2, что означает O(n2).

ПРИМЕЧАНИЕ. Мне не хватает filterSublist2() времени для 69000 слов, потому что мне не хотелось ждать.