Re: [資料] Exact String Matching Algorithms
※ 引述《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
討論串 (同標題文章)
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
-1
12
