什么是位图算法

hiliunx

我上次在某个论坛上看到说  对于查找字符串，可以使用 位图算法和散列，

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

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

numdisp

居然没有人回答？

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

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

starwing83

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

A.com

bmp文件就是一种位图，每一位都是对应像素的颜色值。

没本

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

prolj

《编程珠玑》第二版，第二章。
这个方案是我给一个朋友提的，hashbitmap，就是结合bitmap和hash，不懂的去看书，看不懂再看。

没本

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

16887126

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

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

dotadang

回复 8# 16887126


有的

notion001

位图算法，还是第一次听到