string match в Python

Question

У меня есть строки 300K, хранящиеся в списке, а длина каждой строки составляет от 10 до 400. Я хочу удалить те, которые являются подстрокой других строк (строки с более короткой длиной имеют более высокую вероятность быть подстрокой других).

В настоящее время я сначала сортирую эти строки 300K по длине, а затем использую метод ниже.

sorted_string = sorted(string_list, key=length, reverse=True) 
for item in sorted_string 
    for next_item in sorted_string[sorted_string.index(item)+1:] 
     if next_item in item: 
      del sorted_string[sorted_string.index(next_item)] 

Время работы этого метода: O (n^2). Поскольку у меня есть 300K строк, я не удовлетворен этим методом.

Я попытался разделить эти отсортированные строки на разные куски и использовать многопроцессорную обработку для вычисления каждого фрагмента. Моя первая мысль заключалась в том, чтобы поставить первые 10K на первый кусок, а следующий 10K на второй кусок и т. Д. Но в этом случае строки в каждом куске имеют одинаковую длину, и они могут не подстроить других в одном куске. Так что это не хорошая стратегия разделения.

Любые хорошие идеи?

Edit: эти строки представляют собой последовательности ДНК, и содержат только 'г', 'C', 'T' и 'а'

Update:

Я попытался построить суффикс дерева, используя код от https://github.com/kvh/Python-Suffix-Tree. Эта программа создает дерево суффиксов на основе Ukkonen's algorithm.

Общая длина конкатенированной строки составляет около 90 000 000. Это большое количество. Программа работает полчаса и обрабатывается всего ~ 3 000 000 (1/30) символов. Я не удовлетворен этой программой.

Есть ли другой алгоритм построения дерева суффикса, который может обрабатывать эту большую строку?

Answer 1

Вы можете использовать suffix tree. Это приведет вас к O (mn), где m - длина строк. Он по-прежнему квадратичен, но поскольку в вашем случае m < < n, это обеспечило бы заметное улучшение.

These lecture notes обеспечивает довольно хорошее визуальное объяснение того, как вы можете использовать дерево суффикса, чтобы найти подстроки.

Answer 2

Это очень крутая и очень интересная проблема. Я изучил алгоритмы семантического набора, и их уже много.

Вы слышали о алгоритме BLAST? http://blastalgorithm.com/ A GUI: http://blast.ncbi.nlm.nih.gov/