Как объединить строки с перекрывающимися символами в Python? - PullRequest
Новая
       29

Как объединить строки с перекрывающимися символами в Python?

0 голосов
/ 27 сентября 2018

Я работаю над проектом Python, который читает закодированный в виде URL список строк.Каждая строка имеет длину 15 символов и пересекается со своей последовательной строкой не менее чем на 3 символа и не более чем на 15 символов (идентично).

Цель программы - перейти из списка перекрывающихся строк - либо упорядоченных, либонеупорядоченный - в сжатую строку в кодировке URL.

Мой текущий метод не работает на дублирующих сегментах в перекрывающихся строках.Например, моя программа неправильно комбинирует: 

StrList1 = [ 'd+%7B%0A++++public+', 'public+static+v','program%0Apublic+', 'ublic+class+Hel', 'lass+HelloWorld', 'elloWorld+%7B%0A+++', '%2F%2F+Sample+progr', 'program%0Apublic+']

для вывода: 

output = ['ublic+class+HelloWorld+%7B%0A++++public+', '%2F%2F+Sample+program%0Apublic+static+v`]

, когда правильный вывод: 

output = ['%2F%2F+Sample+program%0Apublic+class+HelloWorld+%7B%0A++++public+static+v']

Я использую простой Python,не биопионы или выравниватели последовательностей, хотя, может быть, мне следует?

Буду очень признателен за любые советы или предложения о том, как сделать это в python!

Спасибо!

Ответы [ 2 ]

0 голосов
/ 08 октября 2018

Зависает, если ни одна из строчек не превышает 20. Как это можно оптимизировать?

0 голосов
/ 27 сентября 2018

Вы можете начать с одной из строк в списке (сохраненных как string) и для каждой из оставшихся строк в списке (сохраненных как candidate), где:

  • candidate является частью string,
  • candidate, содержит string,
  • candidate, соответствует хвосту string,
  • или, candidate голова совпадает с хвостом string,

собрать две строки в соответствии с их перекрытием, а затем рекурсивно повторить процедуру с удалением перекрывающей строки из оставшихся строки собранная строка добавляется до тех пор, пока в списке не останется только одна строка, и в этот момент она является действительной полностью собранной строкой, которую можно добавить к окончательному выводу.

Поскольку потенциально может быть несколько способов несколькостроки могут накладываться друг на друга, некоторые из которых могут привести к одинаковым собранным строкам, вместо этого вы должны сделать вывод набора строк: 

def assemble(str_list, min=3, max=15):
    if len(str_list) < 2:
        return set(str_list)
    output = set()
    string = str_list.pop()
    for i, candidate in enumerate(str_list):
        matches = set()
        if candidate in string:
            matches.add(string)
        elif string in candidate:
            matches.add(candidate)
        for n in range(min, max + 1):
            if candidate[:n] == string[-n:]:
                matches.add(string + candidate[n:])
            if candidate[-n:] == string[:n]:
                matches.add(candidate[:-n] + string)
        for match in matches:
            output.update(assemble(str_list[:i] + str_list[i + 1:] + [match]))
    return output

, чтобы при вводе образца:

StrList1 = ['d+%7B%0A++++public+', 'public+static+v','program%0Apublic+', 'ublic+class+Hel', 'lass+HelloWorld', 'elloWorld+%7B%0A+++', '%2F%2F+Sample+progr', 'program%0Apublic+']

assemble(StrList1) would return: 

{'%2F%2F+Sample+program%0Apublic+class+HelloWorld+%7B%0A++++public+static+v'}

или как пример ввода с различными перекрывающимися возможностями (что вторая строка может соответствовать первой, находясь внутри, имея хвост, совпадающий с головой, и имея голову, совпадающую с хвостом):

assemble(['abcggggabcgggg', 'ggggabc'])

вернется: 

{'abcggggabcgggg', 'abcggggabcggggabc', 'abcggggabcgggggabc', 'ggggabcggggabcgggg'}
...