您有新信

 
Re: 演算法
#1
發信站: National Sun Yet San University (m2.dj.net.tw>, 信區: BudaTech)
Heaven wrote:
> 
> Shann 兄:
> 
> > 這就是所謂 pattern matching 的想法.  我不清楚您的程式依據什麼算法寫的.
> > 請找一本資料結構或演算法則的課本, 找一個稱做 Knuth-Morris-Pratt 的算法.
> 
>   昨天翻了一下家中的書 :) , 果然有看到這個演算法, 但和以前一樣, 還是看不懂
> :<
> 
>   不過, 那個是在一個長字串中找某一段短字串的技巧, 其實這方面我直接用 c 的函
>   數就搞定了.
> 
>   後學的重點在於, 在二個長字串中, 如何判斷那些部份是相同的,
> 那些部份是不同的,
>   我想大家都懂我的意思, 不過還是舉例一下:
> 
>   我愛大自然, 喜歡大自然, 您愛不愛?
>   我愛太白然, 喜歡大自然, 您愛不愛?
> 
>   寫的不好的程式, 有時會看成 (我的程式就會啦!)
> 
>   我愛      大自然....
>   我愛太白然,喜歡大自然....
> 
>   這些判斷如何叫電腦做呢? 有什麼好規則?
> 
>   Heaven
可以考慮用辭庫來作輔助.

-- 
------------------------------------------------------------------------
張文明
日月工作室
voice: 886-2-658-0270 (night)
mailto: dnstudio@m2.dj.net.tw 或 wmc@mozart.seed.net.tw
電子佛教藏經閣: http://w5.dj.net.tw/~DNStudio/canon 或
http://www.tyba.org.tw/canon
Fri May 16 12:50:16 1997
回覆 | 轉寄 | 返回

Re: 演算法
#2
發信站: 國立中山大學網路組 Mailing List (mail.chinatrust.com.tw>, 信區: BudaTech)
> >   我愛大自然, 喜歡大自然, 您愛不愛?
> >   我愛太白然, 喜歡大自然, 您愛不愛?
> >   寫的不好的程式, 有時會看成 (我的程式就會啦!)
> >   A.我愛      大自然....
> >   B.我愛太白然,喜歡大自然....
> >   這些判斷如何叫電腦做呢? 有什麼好規則?

>     再多加個判斷, 將 B.中的「太白然,喜歡」當成另一列待判斷的字串, 而將
>   A.中「大自」之後的「然,喜歡大自然...」與上述的「太白然,喜歡」做比較.
>     這樣或許可以解決此類問題. 

  能否說詳細一些, 後學不是很能弄清您的建議... 

  另外, 舉個黃金範例, 供大家動腦

 123456AB34甲乙EFG
 甲乙丙丁AB34甲乙EFG  

標準答案:
 123456AB34甲乙EFG
 甲乙丙丁  AB34甲乙EFG  

錯誤1:(第一行找到二個相同的就對到第二行去)
 12    3456AB34甲乙EFG
 甲乙丙丁AB34      甲乙EFG  

錯誤2:(第二行找到二個相同的就對到第一行去)
 123456AB34甲乙        EFG
           甲乙丙丁AB34甲乙EFG  

您如何要電腦去判斷上面的邏輯呢?

  Heaven
Tue May 20 09:30:21 1997
回覆 | 轉寄 | 返回

Re: 演算法
#3
發信站: 國立中山大學網路組 Mailing List (tpts1.seed.net.tw>, 信區: BudaTech)
Heaven wrote:
> 
>   另外, 舉個黃金範例, 供大家動腦
> 
>  123456AB34甲乙EFG
>  甲乙丙丁AB34甲乙EFG
> 
> 標準答案:
>  123456AB34甲乙EFG
>  甲乙丙丁  AB34甲乙EFG
> 
> 錯誤1:(第一行找到二個相同的就對到第二行去)
>  12    3456AB34甲乙EFG
>  甲乙丙丁AB34      甲乙EFG
> 
> 錯誤2:(第二行找到二個相同的就對到第一行去)
>  123456AB34甲乙        EFG
>            甲乙丙丁AB34甲乙EF> 
>
> 您如何要電腦去判斷上面的邏輯呢?

好!讓我這個不懂程式、不懂數學的人再來亂想一通,或
許可以激發大家的靈感。

先把這個黃金範例修改成這樣:

字序  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
-------------------------
A檔 1 2 3 4 5 6 A B 3 4 甲 乙 E F G
B檔 甲 乙 丙 丁 A B 3 4 甲 乙 E F G  


假設每次從A檔抓一個字來跟B檔比,且每次都從B檔的
開頭第一個字比起。

A檔第01個字「1」在B檔找不到,記錄值∞。
A檔第02個字「2」在B檔找不到,記錄值∞。
A檔第03個字「3」在B檔07找到,記錄值 7。
A檔第04個字「4」在B檔08找到,記錄值 8。
A檔第05個字「5」在B檔找不到,記錄值∞。
A檔第06個字「6」在B檔找不到,記錄值∞。
A檔第07個字「A」在B檔05找到,記錄值 5。
A檔第08個字「B」在B檔06找到,記錄值 6。
A檔第09個字「3」在B檔07找到,記錄值 7。
A檔第10個字「4」在B檔08找到,記錄值 8。
A檔第11個字「甲」在B檔01、09找到,記錄值 1、 9。
A檔第12個字「乙」在B檔02、10找到,記錄值 2、10。
A檔第13個字「E」在B檔11找到,記錄值11。
A檔第14個字「F」在B檔12找到,記錄值12。
A檔第15個字「G」在B檔13找到,記錄值13。

從上面的觀察,當A檔第11、12字各產生兩個記錄值時,依據前
後連續性來考量,應當取記錄值9跟10。

很顯然的,A檔第03、04字有連續記錄值7、8,其記錄值總和為
7+8=15。但A檔從第07到15字皆有連續記錄值,且當中亦包含記
錄值7、8,而其開始連續的頭兩個(第07、08字)記錄值總和為
5+6=11。

若考慮這兩個發生連續記錄值的區段,第二個區段的範圍不但大
於第一個區段,而且包含第一個區段,所以應當放棄第一個區段。

再從記錄值總和來看,第一個區段的兩個記錄值總和為7+8=15,
第二個區段頭兩個記錄值總和為 5+6=11,因為15>11,所以應該
放棄第一個區段。


 摩訶工作室.吳寶原
 E-mail:maha@tpts1.seed.net.tw
 Tel:(02)6741715/Fax:(02)6741716
Tue May 20 13:50:04 1997
回覆 | 轉寄 | 返回

Re: 演算法
#4
發信站: 國立中山大學網路組 Mailing List (tpts1.seed.net.tw>, 信區: BudaTech)
Heaven wrote:
> 
>   另外, 舉個黃金範例, 供大家動腦
> 
>  123456AB34甲乙EFG
>  甲乙丙丁AB34甲乙EFG
> 
> 標準答案:
>  123456AB34甲乙EFG
>  甲乙丙丁  AB34甲乙EFG
> 
> 錯誤1:(第一行找到二個相同的就對到第二行去)
>  12    3456AB34甲乙EFG
>  甲乙丙丁AB34      甲乙EFG
> 
> 錯誤2:(第二行找到二個相同的就對到第一行去)
>  123456AB34甲乙        EFG
>            甲乙丙丁AB34甲乙EF> 
>
> 您如何要電腦去判斷上面的邏輯呢?

好!讓我這個不懂程式、不懂數學的人再來亂想一通,或
許可以激發大家的靈感。

先把這個黃金範例修改成這樣:

字序  01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
-------------------------
A檔 1 2 3 4 5 6 A B 3 4 甲 乙 E F G
B檔 甲 乙 丙 丁 A B 3 4 甲 乙 E F G  


假設每次從A檔抓一個字來跟B檔比,且每次都從B檔的
開頭第一個字比起。

A檔第01個字「1」在B檔找不到,記錄值∞。
A檔第02個字「2」在B檔找不到,記錄值∞。
A檔第03個字「3」在B檔07找到,記錄值 7。
A檔第04個字「4」在B檔08找到,記錄值 8。
A檔第05個字「5」在B檔找不到,記錄值∞。
A檔第06個字「6」在B檔找不到,記錄值∞。
A檔第07個字「A」在B檔05找到,記錄值 5。
A檔第08個字「B」在B檔06找到,記錄值 6。
A檔第09個字「3」在B檔07找到,記錄值 7。
A檔第10個字「4」在B檔08找到,記錄值 8。
A檔第11個字「甲」在B檔01、09找到,記錄值 1、 9。
A檔第12個字「乙」在B檔02、10找到,記錄值 2、10。
A檔第13個字「E」在B檔11找到,記錄值11。
A檔第14個字「F」在B檔12找到,記錄值12。
A檔第15個字「G」在B檔13找到,記錄值13。

從上面的觀察,當A檔第11、12字各產生兩個記錄值時,依據前
後連續性來考量,應當取記錄值9跟10。

很顯然的,A檔第03、04字有連續記錄值7、8,其記錄值總和為
7+8=15。但A檔從第07到15字皆有連續記錄值,且當中亦包含記
錄值7、8,而其開始連續的頭兩個(第07、08字)記錄值總和為
5+6=11。

若考慮這兩個發生連續記錄值的區段,第二個區段的範圍不但大
於第一個區段,而且包含第一個區段,所以應當放棄第一個區段。

再從記錄值總和來看,第一個區段的兩個記錄值總和為7+8=15,
第二個區段頭兩個記錄值總和為 5+6=11,因為15>11,所以應該
放棄第一個區段。


 摩訶工作室.吳寶原
 E-mail:maha@tpts1.seed.net.tw
 Tel:(02)6741715/Fax:(02)6741716
Tue May 20 13:50:04 1997
回覆 | 轉寄 | 返回

Re: 演算法
#5
發信站: 國立中山大學網路組 Mailing List (mail.chinatrust.com.tw>, 信區: BudaTech)
> >   我愛大自然, 喜歡大自然, 您愛不愛?
> >   我愛太白然, 喜歡大自然, 您愛不愛?
> >   寫的不好的程式, 有時會看成 (我的程式就會啦!)
> >   A.我愛      大自然....
> >   B.我愛太白然,喜歡大自然....
> >   這些判斷如何叫電腦做呢? 有什麼好規則?

>     再多加個判斷, 將 B.中的「太白然,喜歡」當成另一列待判斷的字串, 而將
>   A.中「大自」之後的「然,喜歡大自然...」與上述的「太白然,喜歡」做比較.
>     這樣或許可以解決此類問題. 

  能否說詳細一些, 後學不是很能弄清您的建議... 

  另外, 舉個黃金範例, 供大家動腦

 123456AB34甲乙EFG
 甲乙丙丁AB34甲乙EFG  

標準答案:
 123456AB34甲乙EFG
 甲乙丙丁  AB34甲乙EFG  

錯誤1:(第一行找到二個相同的就對到第二行去)
 12    3456AB34甲乙EFG
 甲乙丙丁AB34      甲乙EFG  

錯誤2:(第二行找到二個相同的就對到第一行去)
 123456AB34甲乙        EFG
           甲乙丙丁AB34甲乙EFG  

您如何要電腦去判斷上面的邏輯呢?

  Heaven
Tue May 20 09:30:21 1997
回覆 | 轉寄 | 返回

Re: 演算法
#6
白明弘
發信站: 獅子吼站 (Lion , 信區: BudaTech)
==> 於  ("Heaven") 文中述及:
:   能否說詳細一些, 後學不是很能弄清您的建議... 
:   另外, 舉個黃金範例, 供大家動腦
:  123456AB34甲乙EFG
:  甲乙丙丁AB34甲乙EFG  
: 標準答案:
:  123456AB34甲乙EFG
:  甲乙丙丁  AB34甲乙EFG  
: 錯誤1:(第一行找到二個相同的就對到第二行去)
:  12    3456AB34甲乙EFG
:  甲乙丙丁AB34      甲乙EFG  
: 錯誤2:(第二行找到二個相同的就對到第一行去)
:  123456AB34甲乙        EFG
:            甲乙丙丁AB34甲乙EFG  
: 您如何要電腦去判斷上面的邏輯呢?

小弟有找到兩篇探討這類問題的文章, 供學長參考:
[1] "A File Comparison Program", by Webb Miller & Eugene W. Myers, from
    SOFTWARE-PRACTICE AND EXPERIENCE, VOL. 15(11), 1025-1040(NOVEMBER 1985)

[2] "An O(ND) Difference Algorithm and Its Variations" by Eugene W. Myers, 
    from ALGORITHMICA (1986) VOL.1 pp.251-266

如果你在圖書館找不到的話, 小弟可以寄一分給你,
或是等小弟期末考完, k 他一 k, 再POST上來 ^_^
Wed Jun 18 15:05:38 1997
回覆 | 轉寄 | 返回

卍 台大獅子吼佛學專站  http://buddhaspace.org