문자열 집합에서 부분 문자열 찾기

Question

큰 (50k-100k) 문자열 세트 mystrings이 있습니다. mystrings에있는 문자열 중 일부는 다른 문자열의 정확한 하위 문자열 일 수 있습니다. 이러한 문자열을 삭제 (가장 긴 문자열 만 삭제)하고 싶습니다. 지금은 O(N^2) 복잡도가있는 순진한 방법을 사용하고 있습니다. 데이터 구조 나 알고리즘이 작업을 더 쉽게 할 수 있도록하고 O(N^2) 작업을 필요로하지 않을

unique_strings = set() 
for s in sorted(mystrings, key=len, reverse=True): 
    keep = True 
    for us in unique_strings: 
     if s in us: 
      keep = False 
      break 
    if keep: 
     unique_strings.add(s) 

. 라이브러리는 괜찮지 만 순수 Python을 유지해야합니다.

Answer 1

본래의 접근 방식은 :

1. sort strings by length, longest first # `O(N*log_N)` 
2. foreach string: # O(N) 
    3. insert each suffix into tree structure: first letter -> root, and so on. 
     # O(L) or O(L^2) depending on string slice implementation, L: string length 
    4. if inserting the entire string (the longest suffix) creates a new 
     leaf node, keep it! 

O[N*(log_N + L)] or O[N*(log_N + L^2)] 

이것은 아마도 지금까지 최적의에서, 그러나 큰 N (문자열의 수) 작은 L (평균 문자열 길이)에 대한 O(N^2)보다 훨씬 더 나은해야한다.

길이에 따라 내림차순으로 문자열을 반복하고 각 문자열의 모든 하위 문자열을 집합에 추가하고 집합에없는 문자열 만 유지할 수도 있습니다. 알고리즘의 큰 O는 (O[N*(log_N + L^2)]) 위의 최악의 경우와 동일해야하지만 구현은 매우 간단하다 :이 방법 해낸 그 동안

seen_strings, keep_strings = set(), set() 
for s in sorted(mystrings, key=len, reverse=True): 
    if s not in seen_strings: 
     keep_strings.add(s) 
     l = len(s) 
     for start in range(0, l-1): 
      for end in range(start+1, l): 
       seen_strings.add(s[start:end]) 

Answer 2

.

from Bio.trie import trie 
unique_strings = set() 
suffix_tree = trie() 
for s in sorted(mystrings, key=len, reverse=True): 
    if suffix_tree.with_prefix(contig) == []: 
     unique_strings.add(s) 
     for i in range(len(s)): 
      suffix_tree[s[i:]] = 1 

좋은 : ≈15 분 - 내가 작업 한 데이터 세트> ≈20 초. 불량 : biopython을 종속성으로 소개합니다. 원래는 경량 적이거나 순수한 파이썬이 아니 었습니다.