haskell - 使用冲突实现一个简单的布隆过滤器
问题描述
我在布隆过滤器中实现了一个简单的哈希过程。如何使用冲突实现相同的过程?
这是我已经实现的Haskell代码:</p>
module testbloom where
data HashTable = HashTable { location :: Int, value :: [Int] }
data HashFunction = HashFunction { hashfunction :: HashTable -> Int -> Int }
data BloomFilter = BloomFilter { hashF :: [HashFunction], table :: HashTable }
hashtable :: Int -> HashTable
hashtable loc = HashTable { location = loc, value = replicate loc 0 }
setbloom :: BloomFilter
setbloom = BloomFilter { hashF = [defaultfunction], table = hashtable 32 }
defaultfunction :: HashFunction
defaultfunction = HashFunction { hashfunction = function }
function :: HashTable -> Int -> Int
function va t = t `mod` ( location va )
hash :: HashFunction -> HashTable -> Int -> Int
hash func hash t = ( hashfunction func ) hash t
replacebit :: [Int] -> Int -> Int -> [Int]
replacebit hashtable posit v = a ++ (v:tail ax)
where (a,ax) = splitAt posit hashtable
setToOne :: Int -> HashTable -> HashTable
setToOne t hashtable = hashtable { value = values }
where values = replacebit (value hashtable) t 1
fill :: BloomFilter -> [Int] -> BloomFilter
fill bf t = bf {table = tables}
where tables = foldr setToOne initialbloom $ concat [ [ hash f initialbloom v | v <- t] | f <- fns ]
initialbloom = table setbloom
fns = hashF setbloom
judge:: BloomFilter -> Int -> Bool
judge setbloom v
| vs == [1] = True
| otherwise = False
where vs = [(value bs) !! pos | pos <- positions]
positions = [ hash hf bs v | hf <- hashF setbloom]
bs = table setbloom
bloom :: [Int] -> Int -> Bool
bloom vs v = judge (fill setbloom vs) v
test :: [Int] -> [Int]
test vs = value $ table $ fill setbloom vs
如何将其转换为冲突语言,感谢您的帮助。
解决方案
推荐阅读
- r - rpart.plot 错误:box.palette 既不是颜色也不是调色板
- css - 如何使页脚不延伸到整个窗口大小
- python - 根据列名转换熊猫中的数据框
- flask - 我可以从使用 URLLIB 或 REQUETS 在本地运行的 Flask-api 获取 JSON 响应吗?
- python - Python NLTK 使用自定义语法解析递归错误
- javascript - 使用 jQuery 在点击时隐藏行
- google-data-studio - 为什么将数据源添加到 Google Data Studio 时会添加到 Google Drive?
- javascript - jquery datepicker在引导模式中具有动态文本框
- azure-logic-apps - 如何删除逻辑应用的集成帐户
- node.js - 无法连接到 mongodb 容器