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