http://www-igm.univ-mlv.fr/~lecroq/string/index.html
這個網站不但列出各種較知名的字串搜尋法，而且還有 C 程式、
論文出處及 Java 版動畫喔，真的滿讚的。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.222.173.26
> -------------------------------------------------------------------------- <
作者: reader (讀者) 看板: CSSE
標題: Re: [資料] Exact String Matching Algorithms
時間: Sun Dec 26 04:35:21 2004
※ 引述《reader (讀者)》之銘言：
: http://www-igm.univ-mlv.fr/~lecroq/string/index.html
: 這個網站不但列出各種較知名的字串搜尋法，而且還有 C 程式、
: 論文出處及 Java 版動畫喔，真的滿讚的。
在傳統的演算法研究中，字串搜尋一直是很重要的一個議題。
不過在實用上，我認為一對一的搜尋研究已經相當成熟了，但
一對多、多對一及多對多的字串搜尋，卻似乎還不夠完善。
當然或許是我了解得不夠深入。
現實上 anti-spam 的機制，由於需要過濾大量關鍵字，就成
滿大的一個效能問題，我曾經差點就到趨勢去工作，那時候，
他們希望我參與的就是提昇 anti-spam 軟體的效能（不過我
對於修改系統而不是製作新系統實在興趣不太大），但可見這
確實還是一個議題。
這是在單一長字串中要搜尋大量小字串的問題。
另外在許多 p2p 系統中，常見而且重要的檔案搜尋伺服器，
則需要面對多對一的字串搜尋問題，如何在數以百萬計的檔案
名稱中，迅速找到使用者所需要的檔案，就是一個很大的效能
問題。
這都很令人傷腦筋呢。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.222.173.26
> -------------------------------------------------------------------------- <
作者: klain (klain) 看板: CSSE
標題: Re: [資料] Exact String Matching Algorithms
時間: Thu Dec 30 02:03:33 2004
: 比較現實來說，有誰使用過非 brute-force 的字串搜尋呢?
: 在什麼樣的場合應用? 為什麼? 以及使用效益如何?
據小弟粗淺所知，
string matching目前在生物資訊方面所用非常多，
無論是exact matching或是找alignment之類的，
而目前因為設計演算法的人都是因應生物學家的要求來設計演算法，
也因為有各式各樣的要求，
所以使用效益上很難一以評估，
不過，目前的exact matching algorithm，倒是可以在O(n)內完成。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.157.147
> -------------------------------------------------------------------------- <
作者: CGary (煙霞) 看板: CSSE
標題: Re: [資料] Exact String Matching Algorithms
時間: Fri Dec 31 11:50:25 2004
※ 引述《reader (讀者)》之銘言：
: 在傳統的演算法研究中，字串搜尋一直是很重要的一個議題。
: 不過在實用上，我認為一對一的搜尋研究已經相當成熟了，但
: 一對多、多對一及多對多的字串搜尋，卻似乎還不夠完善。
: 當然或許是我了解得不夠深入。
其實還是有些空間可以做, 傳統上, 對於字串搜尋的母體空間都不是很大,
exact string matching的問題作到O(n)大概就OK了,但是在Bio-tech上,
O(n)恐怕不是個很OK的時間, 而且Space Capacity也是個問題, 搞Bio-tech
最常遇到的問題, "Variable"有10G over, 光是塞到memory就有問題了
所以現在在搞String Alignment, String Matching在這類問題上都走向
approximate algorithm, 在做 drug discovery-PROTEIN FOLDING 也好,
DNA research 也罷, 其實都在尋找機率比較高的pattern去做而已, 所以
有足夠高的機率打到就夠了, 所以現在這幾年的演算法開始流行approximate
approach.
至於一般應用的字串搜尋, 目前在多對多跟一對多的搜尋, 也已經不玩這種把戲了,
Google興起之後(Brin跟Page的The anatomy of a large-scale hypertextual
Web search engine以及Kleinberg的Authoritative sources in a hyperlinked
environment), 作search的都玩ranking的套, 比搞那種exact matching方法要來得
有效有用多了
: 現實上 anti-spam 的機制，由於需要過濾大量關鍵字，就成
: 滿大的一個效能問題，我曾經差點就到趨勢去工作，那時候，
: 他們希望我參與的就是提昇 anti-spam 軟體的效能（不過我
: 對於修改系統而不是製作新系統實在興趣不太大），但可見這
: 確實還是一個議題。
Anti-spamming的研究,在商用或許還不太成熟,不過在理論界,
大概前兩三年已經被做到翻掉, 目前比較多人用的方法大概都是
Boosting approach(Machine learning上的, 可以看些AI相關的
書), google 之前有探討過這方面的東西, 我記得沒錯gmail也就是
用這方法搞Spam-filter的, 記pattern比記字的index還要來得多..
至於過濾關鍵字的速度, 反正可以平行運算, 其實是沒有那麼迫切,
這是有錢就可以解決的問題:)
: 這是在單一長字串中要搜尋大量小字串的問題。
: 另外在許多 p2p 系統中，常見而且重要的檔案搜尋伺服器，
: 則需要面對多對一的字串搜尋問題，如何在數以百萬計的檔案
: 名稱中，迅速找到使用者所需要的檔案，就是一個很大的效能
: 問題。
基本上, BT, EMule這些系統都不算是理論架構好的系統,
在Chord以後, 很多系統都走向distributed indexing server,
所以這個問題變成了routing problem..:)
: 這都很令人傷腦筋呢。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 202.39.224.31
> -------------------------------------------------------------------------- <
作者: reader (讀者) 看板: CSSE
標題: Re: [資料] Exact String Matching Algorithms
時間: Fri Dec 31 13:08:21 2004
※ 引述《CGary (煙霞)》之銘言：
: 其實還是有些空間可以做, 傳統上, 對於字串搜尋的母體空間都不是很大,
: exact string matching的問題作到O(n)大概就OK了,但是在Bio-tech上,
: O(n)恐怕不是個很OK的時間, 而且Space Capacity也是個問題, 搞Bio-tech
: 最常遇到的問題, "Variable"有10G over, 光是塞到memory就有問題了
: 所以現在在搞String Alignment, String Matching在這類問題上都走向
: approximate algorithm, 在做 drug discovery-PROTEIN FOLDING 也好,
: DNA research 也罷, 其實都在尋找機率比較高的pattern去做而已, 所以
: 有足夠高的機率打到就夠了, 所以現在這幾年的演算法開始流行approximate
: approach.
Bioinformatics 要用的技術實在是非常瘋狂，電腦科學中所有能用的
東西大概都給它用上了。
: 至於一般應用的字串搜尋, 目前在多對多跟一對多的搜尋, 也已經不玩這種把戲了,
: Google興起之後(Brin跟Page的The anatomy of a large-scale hypertextual
: Web search engine以及Kleinberg的Authoritative sources in a hyperlinked
: environment), 作search的都玩ranking的套, 比搞那種exact matching方法要來得
: 有效有用多了
但是精確比對還是有很多應用的。例如源碼分析或解譯、編譯等等編程
相關的東西，或是各類 markup language 應用就還是很需要這類技術，
特別是更高的效能。而且幾乎都是一對多或多對多的搜尋。
對於程式設計者來說，工作中幾乎所有的相關軟體，都跟它有關。即使
相差零點幾秒都是要爭取的。
: Anti-spamming的研究,在商用或許還不太成熟,不過在理論界,
: 大概前兩三年已經被做到翻掉, 目前比較多人用的方法大概都是
: Boosting approach(Machine learning上的, 可以看些AI相關的
: 書), google 之前有探討過這方面的東西, 我記得沒錯gmail也就是
: 用這方法搞Spam-filter的, 記pattern比記字的index還要來得多..
: 至於過濾關鍵字的速度, 反正可以平行運算, 其實是沒有那麼迫切,
: 這是有錢就可以解決的問題:)
我知道前幾年就做到翻掉了，但是多數都是給大機構用的，比較小型、
個人化的實用技術，卻很少看見。何況現在 spammer 也推陳出新，愈來
愈刁鑽，這場戰爭還有得打，並且現在仍是 spammer 佔上風的局面，到
後來連立法手段等外部的非技術干預都搞出來了，可見 anti-spam 這方
敗得有多慘。
我做 anti-spamming 也完全是為了解決個人現實的垃圾信問題，一天有
上千封的垃圾信，真是太糟糕了，而像是 Bill Gates 這類名人，甚至
一天有四百萬封垃圾信，要用一組人來研發技術處理垃圾信... orz
: 基本上, BT, EMule這些系統都不算是理論架構好的系統,
: 在Chord以後, 很多系統都走向distributed indexing server,
: 所以這個問題變成了routing problem..:)
那是因為應用不同，他們可以假設有很大量的機器隨時連線，這樣當然
可以這麼做。但實際上如果沒有強烈的分享熱情（非法利益）或是黏著
機制，大多數的使用者都是想抓檔案時才連線，抓完就下線，既不能讓
他們抓太久，也不能讓他們抓太快，不然系統會很快爛掉。
理論跟現實之間，實在是相差很多。或者說，許多系統對於最糟狀況的
考量，並不是那麼看重。成功的系統自然有它成功的原因。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.222.173.26