文本比对程序设计--按“求同存异”来梳理文本;用“反转的文本”为“状态数组”充值

作者在 2025-03-01 14:07:59 发布以下内容
图1.png (上传于2025-03-01 14:07:59)
图1.png

图2.png (上传于2025-03-01 14:07:59)
图2.png

图3.png (上传于2025-03-01 14:07:59)
图3.png

图4.png (上传于2025-03-01 14:07:59)
图4.png

流程图.png (上传于2025-03-01 14:07:59)
流程图.png

从图1——图3 的程序运行结果的界面中,我们可以看到程序把左右两个文本中的所有的行(文章形式的文本是“字”,下同)都分成了2类:一类行不做任何修饰、文字颜色保持了原来的黑色。为了描述起来简洁一点,我简称是“YES”(相同的行)。
另一类行则是加上了颜色底纹,或文字加上了颜色、下划线,或行首加上了标记“@”等等,我简称是“NO”。
两个文本的“相同行”之间的关系,可以看作是2个文本的“最长公共子序列”(以“行”为单位)。
从程序结果的界面中,我们可以看出,只要我们获取了差异的具体信息,即2边文本的每一次差异的“起始行号”(QS)和连续的差异“行数”(CD),就可以设计出相应的“界面”来。(我在过去的博文中,曾经给出过一些代码,指出可以利用QS()和CD()去给相应的行(“NO”)加上“行首符号”、插入连续的“斜纹行”(“////////////”)、加上“字体颜色”等等)
我的设计思路是:用“求同存异”的方法来梳理文本、获取 QS()和CD()数据的。
   先来说说“求同”:(哪些行是“YES”)
我采用的方法是:对B文本从上到下的每一行,鉴别是否是属于“前一类”的、不加任何修饰的所谓“相同行”(求同)。为了描述起来简洁一点,如果是的话,则该行的“性质”简称是“YES”(相同的行),如果属于“后一类”,就是“NO”。
每次对一行的鉴定的第1步,就是看左边的第 n1 行A(n1),是否等于右边的第 n2 行B(n2)。【 A(n1)=B(n2)  ?  】
★特别指出:n1和n2之前的行的性质都已经有鉴定结果了,是“YES”或“NO”;n1和n2以及之后的行,都还没有鉴定。这样就保证了“一一对应——公共”和“不改变先后顺序——子序列”(我在后面会说到“最长”的问题)
当这2行比较时,会有以下的几种情况:
    如果A(n1)与B(n2)相同,那么,B(n2)的性质是“YES”。我把这样的情况称为①,我在插图中B(n2)的左面用①标出来。下一行的行号是两边都加1(n1+1,n2+1)。
    如果A(n1)与B(n2)不相同,那么,接着用nr=n1、nr逐渐+1,看看是否有:    A(nr)=B(n2)
这过程中,又有2种情况,一种是:直至文本A结束(nr>L1)(L1是A文本最末尾的行号),都没遇到A(nr)=B(n2),这时,B(n2)肯定是“NO”,而A(n1)不能肯定(下一次比对用 n2+1,n1不动)。我用②来表示。这时,必须用变量Tmp来累加 文本B中 连续的鉴定为“NO”的行数(Tmp>0)
★唯一比较复杂的是, 有了A(nr)=B(n2) 。这样的情况我称为“③”。  看图4左边的2个“过”字,注意2条红色的粗竖线。
我用变量 P 来表示“红线划出的2个区域的字符串(确切叫“行串”)”的“最长公共子序列”的长度(行数)。
再看2条蓝色粗竖线:A文本中的起点在“刚”字(n1),正是文本A中★“未鉴定的部分的首行”,右边的起点在“过”字(n2),正是文本B中★“未鉴定的部分的首行”。
我用变量 Q 来表示“蓝线划出的2个区域的字符串(确切叫“行串”)”的“最长公共子序列”的长度。
注意:Q 正是表示了“2个★未鉴定的部分的最长公共子序列”的长度。
很明显,有这样的逻辑推理:
    当发生 Q > P 时,B(n2)鉴定结果必定是“NO”。因为P的值小了。这样的情况我称为“③2”(注意:与②一样,下一次比对用 n2+1,n1不动)
    如果 P=Q,那么B(n2)鉴定结果必定是“YES”。这样的情况我称为“③1”。(注意:这情况下一次比对用 n1=nr+1,n2=n2+1)
那,谁来告诉我,是Q>P ,还是Q=P ?我找到了如下的方法:(看图4的右面)
把文本A(以行为单位)反转,取名为fanA; 把文本B 也(以行为单位)反转,取名为fanB: 
  fanA(1)=A(L1), fanA(2)=A(L1+1-2),…… fanA(L1)=A(1);
  fanB(1)=B(L2), fanB(1)=B(L2+1-2),…… fanB(L2)=B(1)。
(fanA 和 fanB 分别是 A 和 B 的【以“行”为单位的】反转文本,L1 和 L2 分别是文本A 和 文本B 的行数)
(看图4的右面),它正是“动态规划求最长公共子序列中的【状态数组dp】”的示意图。
  dp[i][j]中的“i”就是图中文本“fanA”的行号“anr(红色)和an1(蓝色)”,dp[i][j]中的“j”就是图中文本“fanB”的行号的“an2”。
上面的 P 就写成了: dp(anr,an2)
       Q 就写成了:dp(an1,an2)      
(多说一句:如果 P=Q,那么图4中 A文本的“蓝色竖线”比“红色竖线”多出的那些行,都是“NO”,要在行首打上标记或加颜色底纹了,发现了吗?)     
当预先已经运行过 子过程 LCS_D (见图4)时,状态数组 dp() 中就有了我们需要的数据了。
这样,要鉴别文本B中每一行的性质是不是“YES”(求同),就可以做到了。


    说完了“求同”,再来说“存异”就容易了。[储存QS()和CD()]
1.差异(编辑)起始行(QS):(请看“流程图”)
当A(n1)与B(n2)不相同时,如果有 Tmp=0 ,说明上一行B(n2-1)是“YES”,由‘相同’变成‘不同’,这时就要记下两边的n1和n2:
  mn=mn+1 新增了1个差异点(编辑点) 
  QS(0, mn) = n1 (“0”表示左边的文本)
  QS(1, mn) = n2 (“1”表示右边的文本)
2.连续的差异(编辑)行数:CD(0, mn) 和 CD(1, mn):(请看“流程图”)
    (1) 在遇到情况①时,如果有 Tmp > 0,说明上一行B(n2-1)是“NO”,这时,编辑(差异)结束,就要记下两边的差异(编辑)的“连续的行数”CD():
        CD(0, mn) = 0    和   CD(1, mn) = Tmp (记下后 Tmp归零 Tmp=0)
    (2)在遇到情况③1时,也是编辑(差异)结束,就要记下
        CD(0, mn) = nr - n1 和  CD(1, mn) = Tmp  (记下后 Tmp归零 Tmp=0,nr归零 nr=0)
等到这个过程运行完,“存异”就完成了。(全部存到数组QS() 和 CD() 里面去了)
获得了“差异数据”,就可以根据你的编程语言的特性,去制作“文本对照结果的界面”了。
补充说明:
1.前面提到的“最长公共子序列”中的“最长”问题举例:
    文本A的内容是“英白罗”;文本B的内容是“罗英白”,你不能说有3个字是相同的。但是你可以说“相同的字是‘罗’1个字”,也可以说“相同的字是‘英白’2个字”。这样一来,对照结果不就混乱了吗?总应该约定一个规则吧?这个规则就是“取最多的、一一对应、前后顺序不变的行称为“相同的行”(对于文章形式的文本,把‘行’换成‘字’)”。也就是“最长公共子序列”的意思。
2.我们并没有存下哪些行是"YES",哪些行是"NO",因为我们特别关注的是“上一行的情况”,而这可以通过 Tmp 来观察:如果这时 Tmp>0 则“上一行”肯定是"NO",如果这时 Tmp=0 则"上一行"肯定是"YES"。
本文不引用特定的编程语言代码,是为了能与更多的、熟悉不同编程语言的读者进行交流。
读者如果发现我的文章或插图中有错误或者不妥、我上传的程序有不对的地方,请给我指出。我真诚地感谢。


默认分类 | 阅读 22 次
文章评论,共0条
游客请输入验证码
浏览97797次
文章分类