发信人: heaven@ccbs.ntu.edu.tw (Post Gateway), 信区: BudaTech
标  题: fgfc 的故事
发信站: 由 狮子吼站 收信 (Sat Feb 27 08:09:34 1999)


前言 :

有网友来问及 fgfc 的原理, 利用这个机会写了篇故事, 让有兴趣的朋友参考!

=============

我来说说 fgfc 的故事.

最先的构想是中研院处传来, 他们在输入资料时是请二家打字行打字, 再用程式来
比对, 这个是很好的构想, 他们也有公开比对程式, 但要求是二份文件格式相同.
才能做有效的处理.

网路上有一群做佛典的义工, 采用这个很好的概念, 但网路上的经典输入者不一,
来源不一, 格式不一, 无法利用中研院的程式, 有些肯下工夫的人, 就将文章的
标点, 空白等去除, 再做成一字一行的档案, 然後使用 dos 的 fc 来处理.

小弟某机缘得知此事, 就尝试利用程式来帮忙做到这点. 程式的构想是 :

原文一 : ---,------,-----aaa----------bbbb--------
原文二 : -----,-----,----ccccc---------dd---------

1.设定 "忽略字" , 逐一读取 "非略忽字" 比对, 直到出现差异为止.

　若忽略字为标点与空白, 则第一个找到的差异处在 aaa--- 与 ccccc- 的第一个字

2.自差异处逐一读取非忽略字, 一一读入 buffer 中, buffer 大小由使用者自订.
  在说明档中, 使用的参数就是 MaxwordNum . 内定值是 100
  (这些数字实际上是以中文字为主)

  本例的 buffer 如下:

  buffer 1 : aaa----------bbbb--------
  buffer 2 : ccccc---------dd---------

3.另一个参数叫 CompareNum , 是我用来判断差异在何处结束用的.
  本来内定为 4 , 意即 : 当有连续 4 个字在二个 buffer 都相同,
  表示差异至此结束.

  程式就是先捉 buffer 1 前四个字 [aaa-] 去 buffer 2 找是否
  有相同的, 若无, 就用下一组四个字 [aa--] 去 buffer 2 找.

  若都找不到, 则程式结束, 表示有连续 100 个字找不到相同的.
  也就表示二篇文章差异性太高, 建议使用者不要玩下去了.

  本例会在 buffer 1 第 4-7 个字找到, 即第一次出现的 [----]

  buffer 1 : aaa    [----]------bbbb--------
  buffer 2 : ccccc  [----]-----dd---------

  於是第一篇的 aaa 与第二篇的 ccccc 相异, 然後从 [----] 再由第一个动作开始.
  直至档案结束或发生太大差异中断.

  **** **** ****

  至此, fgfc 粗稿已经出来了. 参考 readme.txt 的版本讯息,
  大概就是 6/3 '97 第 4 版.

  11/12 '97 改了第五版, 因为上述的方式总是不尽理想, 故这回将 buffer 的
  资料转成一行一字, 丢给 dos 下的 fc 处理, 再读取结果做後续处理.

  **** **** ****

  12/23 '97 想到一个好方法, 於是又放弃了利用 fc.exe , 因为这样实在很慢.

  原来的问题是这样的, 若 buffer 分别如下 :

  buffer 1 : aaa----------bbbb--------
  buffer 2 : ccccc---------aa---------

  则依上述原理, 会在 buffer1 的 2-5 字 [aa--] 在 buffer 2 找到.
  结果就变成

  buffer 1 : a              [aa--]--------bbbb--------
  buffer 2 : ccccc--------- [aa--]-------

  结果就不是我们要的了, 後来的想法是 :

  找到後并不立刻采用, 而去记录在 buffer 1 的第 n 个对应 buffer 2 第 m 个.
  记录 n+m 的最小值, 然後逐一试过, 直到 buffer 1 超过最小的 n+m 个字
  (也就是说再做下去也不可能是最小值), 然後采用最小那一组, 例 :


  buffer 1 : a[aa--]--------bbbb-------- n = 2
  buffer 2 : ccccc---------[aa--]------- m = 15 , n + m = 17

  buffer 1 : aa[a---]-------bbbb-------- n = 3
  buffer 2 : ccccc---------a[a---]------ m = 16 , n + m = 19

  buffer 1 : aaa[----]------bbbb-------- n = 4
  buffer 2 : ccccc[----]-----aa--------- m = 6 , n + m = 10

  ......

  以 n + m = 10 这组最小, 故采用这组.
  这个做法与上一版采用 fc.exe 的方式比较, 效果不差. 且速度快多了.
  本以为这个程式已经很好了. (和 "Microsoft" fc.exe 的效果一样了嘛!)
  您可注意到在这一版的版本说明有一行 :

  2.最大相同字数 default 由 4 个改为 2 个. 其实各有千秋....

  改为 2 是因为用 2 做出来的结果, 和 fc.exe 的结果相同.
  但比 fc.exe 强的是, 我不只可用 2 , 我还有其它选择呢! ^_^

  但想不到这个 "各有千秋" 才是痛心的另一个开始!
  底下是一个实例, 实例中 B: 少了前面的第一句, 而我将标点移去了, 比较好看.

  A: 大般若经第一卷般若经卷一大唐沙门某某序奉天承运...
  B:               般若经卷一大唐少门某人序奉天承运...

  若相同字数设为 2 (差异後面至少要有二个相同的中文字)

  A: [大]般若经 [第一卷般若经] 卷一大唐 [沙] 门某 [某] 序奉天承运...
  B:     般若经                卷一大唐 [少] 门某 [人] 序奉天承运...

  若相同字数设为 4 (差异後面至少要有四个相同的中文字)

  A: [大般若经第一卷] 般若经卷一大唐 [沙门某某] 序奉天承运...
  B:                  般若经卷一大唐 [少门某人] 序奉天承运...

  我们会发现设为 2 时 , 前半段的判断并不好, 分的太细了,
  设为 4 时, 後面 [沙门某某] 我们会希望再分细一点.

  有时我们不想计较太多, 但在实际操作中, 很容易因为不好的判断,
  造成後面的文章无法继续判断下去, 没办法, 只有再想办法了.

  **** **** ****

  8/15 '98 终於又与朋友讨论, 想到一个好的方法, 而拼过 M$ 的 fc.exe 了.

  先找到连续十个相同的地方, 也就是设定相同字数为 10 ,
  再将差异处独立出来, 尝试找 7 个相同的字.
  ......
  直到 1 个相同字.

  再以上例而言, 底下已经是找到七个相同字了,

  A: [大般若经第一卷] 般若经卷一大唐.....
  B:                  般若经卷一大唐.....

  但再分析下去, 都是相同的结果. 至下一组差异时.....
  假设目前这是相同字为 4 的情况

  A: [大般若经第一卷] 般若经卷一大唐 [沙门某某] 序奉天承运...
  B:                  般若经卷一大唐 [少门某人] 序奉天承运...

  若降为 1 时, 发现 [沙门某某] 与 [少门某人] 之中有二个字是相同的 [门某]
  於是又分离出来, 最後结果就是我们要的 :

  A: [大般若经第一卷] 般若经卷一大唐 [沙] 门某 [某] 序奉天承运...
  B:                  般若经卷一大唐 [少] 门某 [人] 序奉天承运...

  程式实际上是由 10 , 7 , 4 , 1 这四种逐一比较,
  (8/15 这版是 11, 8, 5, 2 这四组, 由 10 开始是 10/03 这版改的)

  我本来以为这种做法会变慢, 事实上反而比上一版还快呢!

  **** **** ****

  至止, 就是目前为止的情况了, fgfc 分成二个版本,

  fgfc 比对二档.
  fg3fc 比对三档.

  有一点要提醒, 在读取资料是, 若是非中文的半型字 (英文, 数字, 符号....)
  皆转成二个位元, 程式中就是在前加一个 0x01 , 这样一来,
  所有资料都变成双位元, 不论中文英文, 程式处理起来就单纯多了.

  有朋友试过, 若好好利用, 要做几版比对都可以, 只要将结果与其它版比对即可.

  近来打算要改成 winodws 介面的版本, 并将 fgfc 与 fg3fc 合并.
  其它本来有些细节也想做, 如自订格式输入, 增加忽略□围的弹性,
  例如标记 < > 内全忽略不比对.... 但都因为花的时间大於实际效益, 故都没做.
  毕竟不是商业软体, 堪用即可.

  这大概就是 fgfc 的故事了!


================
※  版本历史  ※
================

10/08   V0.8.2e
        1. 修正错误, 前一版有时会造成比不完, 或造成程式不正常中断.

10/03   V0.8.1e
        1. 小小修正比较结果, 让 {{abc||xbz}} 变成 {{a||x}}b{{c||z}}
           也就是最小相同的字变成一个.

8/15    V0.8e
        (本版没有正式的差异档了, 也就是只有 Easy 版)
        1. 终於取消 CompareNum 这个参数, 而由程式来进行最佳化处理.
           但保留此参数, 只是无作用, 这是为了要与 wfgfc 程式相容配合之故.
        2. 输出之档案由 "增加" (append) 模式改成 "覆写" 模式,  若有同名之
           档案, 会被覆盖过去, 请小心使用.
        3. 修正差异档结果档格式 (Easy 版) 的问题
        4. 解决若原始文件有乱码所造成的问题.

4/3
        (Easy 版)
        1. 差异档变成一个差异一行而已, 以利统计, 而且以前的格式并不很适用.

4/3
'98     1. 完全同 12/23 版, 只是使用 bcb 编辑成 32 位元版而已.

================

12/23
'97     1.修正比较方式, 与 fc 比较起来, 感觉不输喔, 而比外挂 fc 速度快多了,
          故这回放弃使用 fc 做核心了.
        2.最大相同字数 default 由 4 个改为 2 个. 其实各有千秋....
11/12
        纪念版!
        放弃自己写主要比较的程式, 而改由呼叫 win95 的 fc.exe 来处理.
6/03
        可外挂忽略档
5/14
        改成可加亦可由参数输入, 以利批次处理
4/30
        改正前版之标准输出, 并且各版都有不同的输出结果.
        执行时程式会依序询问各输出档名及 "最大容许差异的中文字数"
        及 "最小相同中文字数"
4/13
'97     文件比较器 -- 专为格式相异之中文文件比较用    by Heaven 04/13 '97
        用法 : FGFC file1 file2");
        □例 : FGFC FG0262.07 FG0262G.07\n");
        说明 :
        本程式专为格式相异之中文文件所设计, 两档案比较时, 忽略一切
        英文字, 数字, 符号等 ASCII 码小於 127 的字元. 中文字 (以第
        一个 BYTE ASCII 码大於 128 为判断标准)  则忽略一些符号, 目
        前忽略的符号为内码 A140 ~ A159 及 A263 ~ A2A7 两段. 日後或
        许考虑外挂想要忽略的符号.


  heaven  2/27 '99