|
|
|
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.中「大自」之後的「然，喜歡大自然...」與上述的「太白然，喜歡」做比較.
> 這樣或許可以解決此類問題.
能否說詳細一些, 後學不是很能弄清您的建議...
另外, 舉個黃金範例, 供大家動腦
１２３４５６ＡＢ３４甲乙ＥＦＧ
甲乙丙丁ＡＢ３４甲乙ＥＦＧ
標準答案：
１２３４５６ＡＢ３４甲乙ＥＦＧ
甲乙丙丁 ＡＢ３４甲乙ＥＦＧ
錯誤１：(第一行找到二個相同的就對到第二行去)
１２ ３４５６ＡＢ３４甲乙ＥＦＧ
甲乙丙丁ＡＢ３４ 甲乙ＥＦＧ
錯誤２：(第二行找到二個相同的就對到第一行去)
１２３４５６ＡＢ３４甲乙 ＥＦＧ
甲乙丙丁ＡＢ３４甲乙ＥＦＧ
您如何要電腦去判斷上面的邏輯呢?
Heaven
Tue May 20 09:30:21 1997
|
|
|
|
|
Re: 演算法 |
#3 |
|
發信站:
國立中山大學網路組 Mailing List
(tpts1.seed.net.tw>, 信區: BudaTech)
|
Heaven wrote:
>
> 另外, 舉個黃金範例, 供大家動腦
>
> １２３４５６ＡＢ３４甲乙ＥＦＧ
> 甲乙丙丁ＡＢ３４甲乙ＥＦＧ
>
> 標準答案：
> １２３４５６ＡＢ３４甲乙ＥＦＧ
> 甲乙丙丁 ＡＢ３４甲乙ＥＦＧ
>
> 錯誤１：(第一行找到二個相同的就對到第二行去)
> １２ ３４５６ＡＢ３４甲乙ＥＦＧ
> 甲乙丙丁ＡＢ３４ 甲乙ＥＦＧ
>
> 錯誤２：(第二行找到二個相同的就對到第一行去)
> １２３４５６ＡＢ３４甲乙 ＥＦＧ
> 甲乙丙丁ＡＢ３４甲乙ＥＦ�>
>
> 您如何要電腦去判斷上面的邏輯呢?
好！讓我這個不懂程式、不懂數學的人再來亂想一通，或
許可以激發大家的靈感。
先把這個黃金範例修改成這樣：
═════════════════════════
字序 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
－－－－－－－－－－－－－－－－－－－－－－－－－
Ａ檔 １ ２ ３ ４ ５ ６ Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
Ｂ檔 甲 乙 丙 丁 Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
═════════════════════════
假設每次從Ａ檔抓一個字來跟Ｂ檔比，且每次都從Ｂ檔的
開頭第一個字比起。
Ａ檔第01個字「１」在Ｂ檔找不到，記錄值∞。
Ａ檔第02個字「２」在Ｂ檔找不到，記錄值∞。
Ａ檔第03個字「３」在Ｂ檔07找到，記錄值 7。
Ａ檔第04個字「４」在Ｂ檔08找到，記錄值 8。
Ａ檔第05個字「５」在Ｂ檔找不到，記錄值∞。
Ａ檔第06個字「６」在Ｂ檔找不到，記錄值∞。
Ａ檔第07個字「Ａ」在Ｂ檔05找到，記錄值 5。
Ａ檔第08個字「Ｂ」在Ｂ檔06找到，記錄值 6。
Ａ檔第09個字「３」在Ｂ檔07找到，記錄值 7。
Ａ檔第10個字「４」在Ｂ檔08找到，記錄值 8。
Ａ檔第11個字「甲」在Ｂ檔01、09找到，記錄值 1、 9。
Ａ檔第12個字「乙」在Ｂ檔02、10找到，記錄值 2、10。
Ａ檔第13個字「Ｅ」在Ｂ檔11找到，記錄值11。
Ａ檔第14個字「Ｆ」在Ｂ檔12找到，記錄值12。
Ａ檔第15個字「Ｇ」在Ｂ檔13找到，記錄值13。
從上面的觀察，當Ａ檔第11、12字各產生兩個記錄值時，依據前
後連續性來考量，應當取記錄值9跟10。
很顯然的，Ａ檔第03、04字有連續記錄值7、8，其記錄值總和為
7+8=15。但Ａ檔從第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:
>
> 另外, 舉個黃金範例, 供大家動腦
>
> １２３４５６ＡＢ３４甲乙ＥＦＧ
> 甲乙丙丁ＡＢ３４甲乙ＥＦＧ
>
> 標準答案：
> １２３４５６ＡＢ３４甲乙ＥＦＧ
> 甲乙丙丁 ＡＢ３４甲乙ＥＦＧ
>
> 錯誤１：(第一行找到二個相同的就對到第二行去)
> １２ ３４５６ＡＢ３４甲乙ＥＦＧ
> 甲乙丙丁ＡＢ３４ 甲乙ＥＦＧ
>
> 錯誤２：(第二行找到二個相同的就對到第一行去)
> １２３４５６ＡＢ３４甲乙 ＥＦＧ
> 甲乙丙丁ＡＢ３４甲乙ＥＦ�>
>
> 您如何要電腦去判斷上面的邏輯呢?
好！讓我這個不懂程式、不懂數學的人再來亂想一通，或
許可以激發大家的靈感。
先把這個黃金範例修改成這樣：
═════════════════════════
字序 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
－－－－－－－－－－－－－－－－－－－－－－－－－
Ａ檔 １ ２ ３ ４ ５ ６ Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
Ｂ檔 甲 乙 丙 丁 Ａ Ｂ ３ ４ 甲 乙 Ｅ Ｆ Ｇ
═════════════════════════
假設每次從Ａ檔抓一個字來跟Ｂ檔比，且每次都從Ｂ檔的
開頭第一個字比起。
Ａ檔第01個字「１」在Ｂ檔找不到，記錄值∞。
Ａ檔第02個字「２」在Ｂ檔找不到，記錄值∞。
Ａ檔第03個字「３」在Ｂ檔07找到，記錄值 7。
Ａ檔第04個字「４」在Ｂ檔08找到，記錄值 8。
Ａ檔第05個字「５」在Ｂ檔找不到，記錄值∞。
Ａ檔第06個字「６」在Ｂ檔找不到，記錄值∞。
Ａ檔第07個字「Ａ」在Ｂ檔05找到，記錄值 5。
Ａ檔第08個字「Ｂ」在Ｂ檔06找到，記錄值 6。
Ａ檔第09個字「３」在Ｂ檔07找到，記錄值 7。
Ａ檔第10個字「４」在Ｂ檔08找到，記錄值 8。
Ａ檔第11個字「甲」在Ｂ檔01、09找到，記錄值 1、 9。
Ａ檔第12個字「乙」在Ｂ檔02、10找到，記錄值 2、10。
Ａ檔第13個字「Ｅ」在Ｂ檔11找到，記錄值11。
Ａ檔第14個字「Ｆ」在Ｂ檔12找到，記錄值12。
Ａ檔第15個字「Ｇ」在Ｂ檔13找到，記錄值13。
從上面的觀察，當Ａ檔第11、12字各產生兩個記錄值時，依據前
後連續性來考量，應當取記錄值9跟10。
很顯然的，Ａ檔第03、04字有連續記錄值7、8，其記錄值總和為
7+8=15。但Ａ檔從第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.中「大自」之後的「然，喜歡大自然...」與上述的「太白然，喜歡」做比較.
> 這樣或許可以解決此類問題.
能否說詳細一些, 後學不是很能弄清您的建議...
另外, 舉個黃金範例, 供大家動腦
１２３４５６ＡＢ３４甲乙ＥＦＧ
甲乙丙丁ＡＢ３４甲乙ＥＦＧ
標準答案：
１２３４５６ＡＢ３４甲乙ＥＦＧ
甲乙丙丁 ＡＢ３４甲乙ＥＦＧ
錯誤１：(第一行找到二個相同的就對到第二行去)
１２ ３４５６ＡＢ３４甲乙ＥＦＧ
甲乙丙丁ＡＢ３４ 甲乙ＥＦＧ
錯誤２：(第二行找到二個相同的就對到第一行去)
１２３４５６ＡＢ３４甲乙 ＥＦＧ
甲乙丙丁ＡＢ３４甲乙ＥＦＧ
您如何要電腦去判斷上面的邏輯呢?
Heaven
Tue May 20 09:30:21 1997
|
|
|
|
|
Re: 演算法 |
#6 |
|
白明弘
發信站:
獅子吼站
(Lion , 信區: BudaTech)
|
==> 於 ("Heaven") 文中述及:
: 能否說詳細一些, 後學不是很能弄清您的建議...
: 另外, 舉個黃金範例, 供大家動腦
: １２３４５６ＡＢ３４甲乙ＥＦＧ
: 甲乙丙丁ＡＢ３４甲乙ＥＦＧ
: 標準答案：
: １２３４５６ＡＢ３４甲乙ＥＦＧ
: 甲乙丙丁 ＡＢ３４甲乙ＥＦＧ
: 錯誤１：(第一行找到二個相同的就對到第二行去)
: １２ ３４５６ＡＢ３４甲乙ＥＦＧ
: 甲乙丙丁ＡＢ３４ 甲乙ＥＦＧ
: 錯誤２：(第二行找到二個相同的就對到第一行去)
: １２３４５６ＡＢ３４甲乙 ＥＦＧ
: 甲乙丙丁ＡＢ３４甲乙ＥＦＧ
: 您如何要電腦去判斷上面的邏輯呢?
小弟有找到兩篇探討這類問題的文章, 供學長參考:
[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
| |