Re: [資料] Exact String Matching Algorithms

看板CSSE (電腦科學及軟體工程)作者reader (讀者)時間20年前 (2004/12/31 12:28)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串6/6 (看更多)

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