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