文本比对的一种算法探索、比对算法中的难点及解决方法

作者在 2019-01-11 21:24:54 发布以下内容
    在录入文本里,有2种字符:“有效字符”和“多打字符”。“有效字符”是指它在标准文本里可以找到唯一的“对应字符”。“对应字符”当然与它相同,但是,相同的字符不一定就是“对应字符”。例如:
    标准文本:我们班里的学生大多数是女生。
    录入文本:我们班里喜欢数学的学生大多数是女生。
录入文本的第一个“数”字,在标准文本里是找不到“对应字符”的。
    我的算法思路是这样的:对于录入文本里的每一个字符(包括看不见但是占位置的全、半角空格;包括看不见又不占位但长度又不为零的回车),在标准文本里寻找“对应字符”。(如何确认“对应字符”是个难点,我在后面会提出解决方法,那其实是本文的重点。寻找“对应字符”首先是寻找“相同字符”,只有“相同字符”才有资格做“对应字符”)
    根据寻找的结果(有或没有),自然就解决了“漏”和“多”的问题,既可以得到字符(串)的内容,又可以统计数字。至于“错字”,其实就是“漏”与“多”在对应位置所出现的综合事件,比如把“你说”错打成了“他说”,漏了“你”;多了“他”。在下面的描述中我会细说的。
    下面用文字和图片来描述一次“寻找”的过程。
图1.png (上传于2019-01-11 21:24:54)
图1.png

图1中n1、n2分别是寻找的第一个字符的位置,内容是zn1、zn2 。我称为“起始字符”。如果相同,那比较简单。(不是本文的重点,后面会提出一个小细节)。在图1中两个字不相同。那么把标准文本里的下一个字符与zn2进行比较(标准文本的起始字符仍然记住是zn1)。如果最终找到(z1)。(并确定是“对应字符”,下同)。那么从n1(包括zn1)到z1(不包括z1)的字符(串)就是“漏字符(串)”,标准文本下一轮寻找(比对)从z1之后的那个字符开始;录入文本下一轮寻找从zn2之后的那个字符开始。(即zn2是“有效字符”)。
如果zn2始终没找到“对应字符”(图2)
图2.png (上传于2019-01-11 21:24:54)
图2.png
,那么zn2就是“多”字符,标准文本下一轮寻找仍然从n1开始;录入文本下一轮寻找从zn2之后的那个字符开始。(录入文本始终是一个一个的往后“走”,不管这个字是“有效”还是“多打”)。
    这里说一下“错字”的问题。在每次发生“多”结果时,要有一个变量记录连续“多”的累计字符数(不是最终评分的累计数),一旦发生了“漏”结果,就要马上算出“错”字符内容和个数(当然也可以算出准确字符的内容,调整“漏”和“多”的内容和数量,包括重新涂颜色)然后把“多”的累计字符数清零。这里的细节就不多说了。
下面借助几张截图来说说怎样判断“对应字符”。这是本文的重点。
图34.png (上传于2019-01-11 21:24:54)
图34.png

图3:录入文本里的加红圈的字被误判为“有效字符”;图4里标准文本里的加红圈的字被误判为“对应字符”,造成的后果虽然不影响总分,但是看上去别扭且不大合理,本来连续的漏或错被分成了2段,中间夹了一个对应字符和有效字符。
而图5
图5.png (上传于2019-01-11 21:24:54)
图5.png
更是误判了,录入文本里原本有效的“BCD”成了“多”字符,而标准文本里的“BCD”又成了“漏字符”。真实情况是“多打”了1个“E”。造成这个结果,是因为标准文本里的那个“E”被误判成录入文本第一个“E”字符的“对应字符”了。那是我用“人脑”发现的。怎样让程序来判断呢?
我以本文开头的2行文字为例:图6
图6.png (上传于2019-01-11 21:24:54)
图6.png

先定义2个12个字符的字符串:在标准文本里的  串1=“数是女生。    ”和录入文本的  串2=“数学的学生大多数是女生。”(它们的首字符就是被判断是否“对应字符”的字符“数”)
用一个十多行左右代码的函数判断“有几个不颠倒、可以有间隔的共同字符”。上面的共同字符数是5。
下一步,我先把上述标准文本里的“BCD”+“E”表述成“疑漏字符串”,图6中标准文本里“的学生大多数”。把录入文本在n2后面的区域表述为“未比对区域”。
接着,用For 循环分别把“疑漏字符串”中的每个字符在“未比对区域”寻找相同的字符,若找到,就用该字符为首字符用标准文本和录入文本组成2个也是12个字符的字符串3和字符串4(图6右下方的上下2个)。

然后用同样的函数求出它们的共同字符数。★一旦发生“第2个共同字符数大于第1个共同字符数”(图6这里是10)时,那个疑似“对应字符”(数)即被否定。退出For 循环,确认标准文本上的这个“数”字符不是“对应字符”而继续在标准文本里找,也就是说,这一轮寻找还没有结束。这样就避免了误判。等到这一轮寻找结束,确定是“”还是“”,本轮寻找才算结束,然后更新“起始字符”,进入下一轮寻找“对应字符”.....。

将这样的“寻找”在录入文本里从头到尾走一遍,就完成了“文本比对”。

如果你对上面的描述已经理解的话,你试试在图1中找出2对(4个)字符串,看会不会发生“第2个共同...大于...数”,从而否定“E”(z1)是“对应字符”。

前面图3图4里的问题,也是用“继续找相同字”--“比较2个共同字符数”的方法(不再赘述),不过寻找的区域不同,也不用For 循环,因为只有1个要找的字符。前面为什么要for每个字要找,是因为那个“未比对区域”有可能恰好漏打了某个字,以致找不到。

我以这样的思路,用VB编了这个程序。我用到的命令都是很常用的。也只有1个自定义函数。

以上是自己的见解,欢迎共同探索和指教。


默认分类 | 阅读 5584 次
文章评论,共2条
A洲
2020-09-23 17:00
1
因为你的文章,注册了账号
nhjsjjs(作者)
2020-09-24 20:32
2
以下是引用A洲在2020-09-23 17:00的发言1
因为你的文章,注册了账号
我在2020年8、9月,又把“文本比对”与“最长公共子序列”(LCS)联系起来思考,并有了相应的“流程图”和程序“代码”。看起来是讲LCS,其实“文本比对”的“正确、漏、多”都已经包含着在“流程图”与“代码”里了。我觉得VB的代码理解起来更直观,你有兴趣的话,可以看看那几篇博文,我觉得那里讲的更明白些。
游客请输入验证码
浏览91190次
文章分类