Найти подстроки в наборе строк

У меня есть большой (50k-100k) набор строк mystrings. Некоторые из строк в mystrings могут быть точными подстроками других, и я хотел бы свернуть их (отбросить подстроку и сохранить только самый длинный). Сейчас я использую наивный метод, который имеет сложность 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)

Какие структуры данных или алгоритмы бы сделать эту задачу проще и не требует O(N^2) операций. Библиотеки в порядке, но мне нужно оставаться чистым Python.

источник

2017-01-19 Daniel Standage

Подробнее Pythonic, отбросьте 'keep' boolean и вместо этого используйте' else' предложение в цикле 'for' (не будет изменять временную сложность) http://python-notes.curiousefficiency.org/en/ last/python_concepts/break_else.html –

@Chris_Rands Могли бы вы продемонстрировать? Нет причин продолжать повторение цикла внутреннего цикла после того, как будет найдено совпадение, таким образом, разрыв. Но тогда, как только мы выйдем из внутреннего цикла, мы не знаем, разразились ли мы, потому что совпадение было найдено или если мы только закончили итерацию. Может быть, я что-то упустил, но я думаю, что это самый лаконичный и эффективный способ реализовать этот (по общему признанию наивный) подход. –

Вы сохраняете 'break', просто замените' if keep: 'на' else: '(тот же отступ) и удалите все строки с' keep'. Предложение 'else' выполняется только тогда, когда' break' не происходит. прочитайте статью, связанную выше, если вы не знакомы с конструкцией for-else –

Наивный подход:

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

Это, вероятно, далека от оптимальной, но должно быть значительно лучше, чем O(N^2) для больших N (количество строк) и небольшой L (средней длины строки).

Вы также можете перебирать строки по убыванию по длине и добавлять все подстроки каждой строки в набор и сохранять только те строки, которые не входят в набор. Алгоритмический большой 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])

источник

2017-01-19 08:11:30 schwobaseggl

В то же время я пришел с этим подходом.

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 как зависимость, которая не является ни легким, ни чистым python (как я изначально спросил).

источник

2017-01-19 20:12:43

ответ

Смежные вопросы