实现最长公共子序列的并行算法

Question

我正在尝试实现http://www.iaeng.org/publication/WCE2010/WCE2010_pp499-504.pdf中描述的最长公共子序列问题的并行算法

但是我在第4页的公式6中遇到了变量C的问题

该论文在第3页末尾提到了C on

C为Let C [1:l]为有限字母表

我不确定这是什么意思,因为我猜它会用2个字符串ABCDEF而且ABQXYEF是ABCDEFQXY.但是,如果我的2个蜇是一个对象列表(我的匹配测试的例子是obj1.Name = obj2.Name什么),我的C会在这里怎么办？只是2个阵列上的联合？

Answer 1

阅读并研究了论文后,我可以说这C应该是一个包含字符串字母表的数组,其中字母表大小(以及大小C)是l.

然而,根据你的问题的外观,我觉得有必要深入研究这个问题,因为看起来你还没有全面了解.什么是 P[i,j],为什么你需要它？答案是你并不真的需要它,但这是一个优雅的优化.在第3页,在定理1之前的一点点,据说:

[...]此过程结束时,在第k个步骤,或(ⅰ)JK = 0在第k个步骤= B(JK).假设过程在第k步停止,k必须是使(i)= b(jk)或jk = 0的最小数.[...]

(3)中的递归关系等价于(2),但基本区别在于(2)递归扩展,而(3)你从不有递归调用,前提是你知道k.换句话说,(3)不递归扩展的魔力是你以某种方式知道(2)上的递归停止的位置,所以你立即查看那个单元格,而不是递归地接近它.

那好吧,但你如何找到价值k？由于k是(2)到达基本情况的位置,可以看出,k在B你超出限制之前你必须"返回" 的列数(即,第一列填充0的)或者你找到一个字符B和一个字符之间的匹配A(对应于(2)中的基本情况).请记住,您将匹配角色a(i-1),i当前行在哪里.

所以,你真正想要的是找到角色出现B之前的最后位置.如果之前没有出现这样的人物,那么这相当于达到(2)中的情况; 否则,它与(2)中的到达相同.ja(i-1)Bji = 0 or j-1 = 0a(i) = b(j-1)

我们来看一个例子:

考虑该算法正在计算i = 2和j = 3的值(行和列以灰色突出显示).想象一下,该算法正在处理以黑色突出显示的单元格,并应用(2)确定S[2,2](黑色位置左侧的位置)的值.通过应用(2),然后通过查看a(2)和开始b(2).a(2)是C,b(2)是G,没有匹配(这是与原始的,众所周知的算法相同的过程).该算法现在想要找到的值S[2,2],因为它需要计算S[2,3](我们在哪里).S[2,2]目前还不知道,但是论文表明可以在不引用行的情况下确定该值i = 2.在(2)中,选择第3种情况:S[2,2] = max(S[1, 2], S[2, 1]).请注意,如果你愿意,所有的这个公式做的是看该位置将被用于计算S[2,2].所以,重新说一下:我们是计算S[2,3],我们需要S[2,2]它,我们还不知道它,所以我们回到桌面上看看它的价值S[2,2]与我们原来的方式非常相似,非并行算法.

这什么时候停止？在这个例子中,当我们在第二列(当前列上的字母)或当我们到达第0列时找到字母C(这是我们的a(i))时它会停止.因为之前没有,我们到达第0列.另一个例子:TGTTCGACATCT

在此,(2)将与停止j-1= 5,因为这是在最后的位置TGTTCGACA,其中C示出了.因此,递归到达基本情况a(i) = b(j-1)时j-1 = 5.

考虑到这一点,我们可以在这里看到一个快捷方式:如果你能以某种方式知道的量k,使得j-1-k在(2),那么你就不会要经过评分表中查找基本情况基本情况.

这就是背后的整个想法P[i,j].P是一个垂直放置整个字母表的表格(在左侧); 该字符串B再次水平放置在上侧.此表被计算为预处理步骤的一部分,它会告诉你到底你需要提前知道:对于每个位置j中B,它说,每个字符C[i]的C(字母),什么是在最后的位置B之前j在那里C[i]被发现(注意,i用于索引C,字母,而不是字符串A.也许,作者应该用另一个指标变量,以避免混淆).

所以,你可以把条目的语义想象成以下几P[i,j]行:B中我在位置j之前看到C [i]的最后一个位置.例如,如果你字母表sigma = {A, E, I, O, U},而B = "AOOIUEI", thenP`是:

花点时间了解这张表.请注意该行O.请记住:此行列出了每个位置B,其中最后一个已知的"O".只有当j = 3我们有一个不为零的值(它是2)时,因为那是第一个O进入后的位置AOOIUEI.此条目说,在最后的位置B,其中O前被认为是位置2(事实上,B[2]是一个O,后面的一个A).请注意,同一行中,对于j = 4,我们有值3,因为现在的最后一个位置O是correspnds到第二的一个O中B(而且由于没有更多O的存在,该行的其余部分将是3).

回想一下,P如果想要轻松找到值,那么构建是一个必要的预处理步骤,k这使得从等式(2)的递归停止.它应该是有意义的,现在P[i,j]就是k你正在寻找(3).有了P,您可以及时确定该值O(1).

因此,C[i]in(6)是字母表中的字母 - 我们正在考虑的字母.在上面的例子,C = [A,E,I,O,U]以及C[1] = A,C[2] = E等.在equaton(7),c是在位置C,其中a(i)(字符串的当前信A正在考虑)生活.这是有道理的:毕竟,建立评分表位置的时候S[i,j],我们想用P找到的价值k-我们想知道在哪里是我们看到的最后一次a(i)在B之前j.我们通过读书P[index_of(a(i)), j].

好的,既然您已了解其使用情况P,那么让我们看一下您的实施情况.

关于你的具体案例

在本文中,P显示为列出整个字母表的表格.迭代字母表是一个好主意,因为这种算法的典型用途是生物信息学,其中字母表比字符串小得多A,使得字母表中的迭代更便宜.

因为你的字符串是对象的序列,你C将是所有可能的对象,所以你必须建立一个表P与所有可能的对象实例(废话,当然)的.这绝对是一个字母大小与字符串大小相比较大的情况.但是,请注意,您只会P在与以下字母对应的A行中P编制索引:对于C[i]不在的字母中的任何行A都是无用的且永远不会被使用.这使您的生活更轻松,因为这意味着您可以P使用字符串构建A而不是使用每个可能对象的字母表.

同样,一个例子:如果你的字母表AEIOU,A是EEI和B是AOOIUEI,你只会被索引P的行为E及I,所以这就是你需要P:

这是有效的,因为在(7)中,P[c,j]是P字符的入口c,并且c是索引a(i).换句话说:C[c]永远属于A,所以在大小相当于大小的情况下,P为字符构建A而不是使用整个字母表是完全合理A的C.

您现在要做的就是将相同的原则应用于您的对象.

我真的不知道怎么解释它更好.起初这可能有点密集.确保重新阅读它,直到你真正得到它 - 我的意思是每一个细节.在考虑实现它之前,你必须掌握它.

注意:您说您正在寻找可靠和/或官方来源.我只是另一个CS学生,所以我不是官方消息来源,但我认为我可以被认为是"可信的".我以前研究过这个,我知道这个主题.快乐的编码!