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