Longest Common Subsequence (LCS)問題は次のとおりです: 2 つのシーケンスAとが与えられた場合、とBの両方で見つかった最長のサブシーケンスを見つけます。たとえば、 と が与えられた場合、最長の共通部分列はです。ABA = "peterparker"B = "spiderman""pera"
誰かがこのLongest Common Subsequenceアルゴリズムを説明できますか?
def longestCommonSubsequence(A: List, B: List) -> int:
# n = len(A)
# m = len(B)
indeces_A = collections.defaultdict(list)
# O(n)
for i, a in enumerate(A):
indeces_A[a].append(i)
# O(n)
for indeces_a in indeces_A.values():
indeces_a.reverse()
# O(m)
indeces_A_filtered = []
for b in B:
indeces_A_filtered.extend(indeces_A[b])
# The length of indeces_A_filtered is at most n*m, but in practice it's more like O(m) or O(n) as far as I can tell.
iAs = []
# O(m log m) in practice as far as I can tell.
for iA in indeces_A_filtered:
j = bisect.bisect_left(iAs, iA)
if j == len(iAs):
iAs.append(iA)
else:
iAs[j] = iA
return len(iAs)
書かれているアルゴリズムは の長さを見つけますが、変更して完全なlongest common subsequenceものを見つけることができます。longest common subsequence
leetcode linkで同等の問題に対する最速のpythonソリューションを調べていたときに、このアルゴリズムを見つけました。このアルゴリズムは、問題に対する最速の Python ソリューション (40 ミリ秒) であり、時間の複雑さもあるようです。これは、他のほとんどのソリューションO(m log m)の時間の複雑さよりもはるかに優れています。O(m*n)
なぜそれが機能するのか完全には理解できず、Longest Common Subsequence問題に対する既知のアルゴリズムを探して他の言及を見つけようとしましたが、そのようなものは見つかりませんでした。私が見つけた最も近いものは、実際にもあると言われているHunt–Szymanski algorithm リンクO(m log m)でしたが、同じアルゴリズムではないようです。
私が理解していること：
indeces_afor ループで小さい方のインデックスが保持されるように逆にiAsなります (これは、以下のウォークスルーを実行するとより明確になります)。- 私が知る限り、
iAsfor ループはlongest increasing subsequenceof を見つけindeces_A_filteredます。
ありがとう！
たとえば、アルゴリズムのウォークスルーを次に示しますA = "peterparker"。B = "spiderman"
01234567890
A = "peterparker"
B = "spiderman"
indeces_A = {'p':[0,5], 'e':[1,3,9], 't':[2], 'r':[4,7,10], 'a':[6], 'k':[8]}
# after reverse
indeces_A = {'p':[5,0], 'e':[9,3,1], 't':[2], 'r':[10,7,4], 'a':[6], 'k':[8]}
# -p- --e-- ---r-- a
indeces_A_filtered = [5,0, 9,3,1, 10,7,4, 6]
# the `iAs` loop
iA = 5
j = 0
iAs = [5]
iA = 0
j = 0
iAs = [0]
iA = 9
j = 1
iAs = [0,9]
iA = 3
j = 1
iAs = [0,3]
iA = 1
j = 1
iAs = [0,1]
iA = 10
j = 2
iAs = [0,1,10]
iA = 7
j = 2
iAs = [0,1,7]
iA = 4
j = 2
iAs = [0,1,4]
iA = 6
j = 3
iAs = [0,1,4,6] # corresponds to indices of A that spell out "pera", the LCS
return len(iAs) # 4, the length of the LCS