Найти наиболее похожие подпоследовательности в другой последовательности

Question

Мне нужно написать алгоритм, который найдет наиболее подобную подстроку в S1 для другой строки S2 (подстрока в S1, которая имеет минимальное расстояние Хэмминга с S2, другими словами) в N log (N), где N = len (S1) + len (S2), len (S2) < = len (S1).

Например:
S1 = AGTCAGTC
S2 = GTC
Ответ: GTC (расстояние 0)

S1 = AAGGTTCC
S2 = TCAA
Ответ: ТТКС (расстояние 3)

Сложность времени может не превышать O (N Log (N)). Космическая сложность не имеет значения.

LCS (самый длинный общий след) не работает в моем случае. Например:

 

    S1 = GAATCCAGTCTGTCT 
    S2 = AATATATAT 

    LCS answer: AATCCAGTC 
    GAATCCAGTCTGTCT 
    ||| 
    AATATATAT 

    right answer: AGTCTGTCT 
    GAATCCAGTCTGTCT 
      | | | | | 
      AATATATAT 

Answer 1

Я думаю, вы пытаетесь решить longest common subsequence problem. Эта проблема связана с попыткой найти наименьшее количество модификаций, необходимых для преобразования одной строки в другую.

Вы сказали, что пытаетесь написать алгоритм для этого. Взгляните на проблему LCS и попробуйте выполнить поиск в Интернете, если вы хотите использовать собственный алгоритм, или вы можете воспользоваться утилитой командной строки diff.

Как и в случае с самой длинной общей проблемой подпоследовательности, diff принимает два файла и находит последовательность дополнений и удалений, что приводит к наименьшим изменениям для преобразования file1 в файл2.Diff очень эффективен, и я думаю, что он будет достаточно быстрым для вашего цели. Я уверен, что большинство различий имеют пространственную и временную сложность O (Nlog (N)) или меньше, но вы можете проверить это самостоятельно. Подробнее о diff здесь http://en.wikipedia.org/wiki/Diff_utility

Я написал небольшую программу python, которая использует diff, чтобы найти самую длинную смежную общую подпоследовательность. Это работает на unix, но я уверен, что любая платформа, которую вы используете, есть утилита diff.

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

import sys 
import subprocess 
import os 
import re 

def getLinesFromShellCommand(command): 
     p = subprocess.Popen(command, shell=True, stdout=subprocess.PIPE, stderr=subprocess.STDOUT, cwd=os.getcwd()) 
     lines = [] 
     for curLine in p.stdout.readlines(): 
       lines.append(curLine) 
     retVal = p.wait() 
     return (retVal, lines) 

#We need to find the longest sequence of lines that start with a space(a space meant the line was in common). 
#We could use some kind of while loop to detect the start and end of a group of lines that start with spaces. 
#However there is a much simpler method. Create a string by concatenating the first char from each line and use regex 
#to find all the subsequences that start with spaces. After that just take the longest subsequence. 
def findLongestCommonSubsequence(diffOutput): 
    outputFirstCharStr = reduce(lambda x, y: x+y[:1], diffOutput, "") 
    commonSubsequences = [(m.start(0), m.end(0)) for m in re.finditer(" +", outputFirstCharStr)] 
    longestCommonSubsequence = max(commonSubsequences, key=lambda (start,end) : end - start) 
    return longestCommonSubsequence 

def main(): 
    if len(sys.argv) != 3: 
     sys.stderr.write("usage: python LongestCommonSubsequence.py <file1> <file2>\n") 
     sys.exit(1) 
    commandOutput = getLinesFromShellCommand("diff -u {0} {1}".format(sys.argv[1], sys.argv[2])) 
    if commandOutput[0] != 1: # apparently diff returns 1 if its successful 
     sys.stderr.write("diff failed with input files.\n") 
     sys.exit(1) 
    diffOutput = commandOutput[1] 
    diffOutput = diffOutput[3:] # the first three lines are not needed 
    longestCommonSubsequence = findLongestCommonSubsequence(diffOutput) 
    print "Indices:",longestCommonSubsequence 
    for i in range(longestCommonSubsequence[0], longestCommonSubsequence[1]): 
     print diffOutput[i], 

if __name__ == "__main__": 
    main() 

использование

python LongestCommonSubsequence.py f1.txt f2.txt 

выход, если f1.txt и f2.txt были второй пример вы дали:

Indices: (5, 7) 
T 
C 

Edit: Я видел ваши комментарии о том, почему выше не будет работать. Возможно, вас заинтересовала эта статья: https://cs.stackexchange.com/questions/2519/efficiently-calculating-minimum-edit-distance-of-a-smaller-string-at-each-positi