Chinaunix

标题: 什么是位图算法 [打印本页]

作者: hiliunx 时间: 2010-04-30 09:02
标题: 什么是位图算法
我上次在某个论坛上看到说对于查找字符串，可以使用位图算法和散列，

散列我知道一点点，但是位图算法我不知道，不知道位图算法在查找字符串中是如何使用的

到底什么是位图算法，请知道的大侠告诉我一下。谢谢

作者: numdisp 时间: 2010-04-30 22:46
居然没有人回答？

我也不懂，但是简单google了一下，应该是属于一种基于概率，并使用先验信息的搜索算法。
楼主想了解详情的话，建议到学术期刊上去搜一搜。

我搜到一片文章，Bitmap algorithms for counting active flows on high
speed links，看了一下Abstract和Introduction部分，文章本身不怎么样，但是应该可以提供一点线索找到你要的信息，注意它的参考文献部分。

作者: starwing83 时间: 2010-04-30 23:08
- -位图就是hash，只是一种很简单的hash，hash函数是f(x) = x，换句话说一个萝卜一个比特，所以叫“位”图。实际上翻译成比特映射会比较贴切有一点（bitmap == bit map）

作者: A.com 时间: 2010-05-01 12:12
bmp文件就是一种位图，每一位都是对应像素的颜色值。

作者: 没本 时间: 2010-05-01 12:20
字串匹配比较经典的算法有: Knuth-Morris-Pratt算法, Boyer-Moore算法, Karp-Rabin算法。其中Karp-Rabin算法是用散列，那个位图算法真没见过，谁来讲解一下？

作者: prolj 时间: 2010-05-01 13:25
《编程珠玑》第二版，第二章。
这个方案是我给一个朋友提的，hashbitmap，就是结合bitmap和hash，不懂的去看书，看不懂再看。

作者: 没本 时间: 2010-05-01 13:45
没那本书，要是这个算法表现良好，建议楼上将之加到维基百科字符串搜索条目中去http://en.wikipedia.org/wiki/String_searching_algorithm 。

作者: 16887126 时间: 2010-05-01 14:46

《编程珠玑》第二版，第二章。
这个方案是我给一个朋友提的，hashbitmap，就是结合bitmap和hash，不懂的去 ...
prolj 发表于 2010-05-01 13:25

第二版第二章哪有讲位图啊？

作者: dotadang 时间: 2010-05-16 20:40
回复 8# 16887126

有的

作者: notion001 时间: 2010-05-17 23:44
位图算法，还是第一次听到

作者: youngky2008 时间: 2011-09-05 11:04
晚上回去好好研究一下

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)