發信人: 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