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

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

 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 https://stackoverflow.com/a/21342145/916657 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 символов или более).

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

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

тогда ответ будет òut 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] 

Означает ли порядок? Если не,

 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'] 

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

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(n 1 ) а для filterSublist2 наклон равен ~ 2, что означает O(n 2 ) .

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