※ 引述《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