`
kabike
  • 浏览: 608479 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

BloomFilter和trie

阅读更多
记录下最近刚刚了解到了两种数据结构BloomFilter和trie

trie:
有一天,有个同学问了个问题,假设有个敏感词列表["敏感词1","敏感词2","敏感词3","敏感词4"],
如何快速判断一组字符串的每个字符串是否包含了所有的敏感词.
这要是用双重for循环,contains那套方法,估计都能跑死.所以我当时想到了把敏感词列表预先做成自动机.然后循环一遍
字符串数组.不过怎么构造那个自动机呢,后来那同学提到了trie的概念.trie可以用来实现高速的字符串匹配.这是典型的空间换时间
具体可以看http://en.wikipedia.org/wiki/Trie

BloomFilter:
BloomFilter是做hadoop semijoin时发现的,它的思路是用容错率来换空间.就像一个hashset,只是BloomFilter有一定的不准确性.
具体可以看http://en.wikipedia.org/wiki/Bloom_filter
分享到:
评论

相关推荐

    基于FPGA的3G数据包过滤算法设计及实现.pdf

    与传统的包过滤技术相比,如并行BV、Bloom Filter和Trie CAM(Ternary Content-Addressable Memory),Hash算法具有较高的处理速度和较低的存储需求。尽管Bloom Filter在节省存储空间方面表现出色,但可能会出现误判...

    基于Trie的算法中具有计数BloomFilter的高效IP地址查找

    计数Bloom Filter的引入,替代了原有的单比特位Bloom Filter,它能够通过多比特计数来记录匹配情况,从而支持Trie节点的删除和插入操作。 此外,Bloom Filter的原理是通过哈希函数将元素映射到一个位数组中,如果...

    《编程之法:面试和算法心得1》数据结构

    综合演练部分则涉及海量数据处理,如关联式容器、分而治之策略、simhash算法、外排序、MapReduce、多层划分、Bitmap、Bloom filter和Trie树等,这些都是大数据处理和分布式计算中的核心技术。 此外,书的附录还包含...

    c语言如何对海量数据进行处理

    以上策略的核心在于合理利用内存,通过外部存储扩展处理能力,并结合合适的数据结构和算法,如哈希表、堆、Bloom Filter、Trie树等,有效地处理海量数据。在C语言中实现这些算法时,需要注意内存管理、I/O效率和程序...

    SuRF: Practical Range Query Filtering with Fast Succinct Tries原文

    SuRF旨在解决传统Bloom Filter无法同时高效处理单键查找和范围查询的问题。文章由来自卡内基梅隆大学、慕尼黑工业大学、英特尔实验室和惠普企业实验室的研究人员共同撰写。SuRF基于一个名为Fast Succinct Trie(FST...

    Scalable Name Lookup with Adaptive Prefix Bloom Filter for Named Data Networking

    这篇文章的标题为:“Scalable Name Lookup with Adaptive Prefix Bloom Filter for Named Data Networking”,可以将其翻译为“面向命名数据网络的可扩展名称查找与自适应前缀布隆过滤器”。文章的主体讨论了在命名...

    海量数据处理

    这些方法的核心思想是通过哈希函数、分布式计算、数据结构优化(如Bloom Filter、trie树、hash_map等)以及外部排序(如归并排序)来处理大数据。在实际应用中,还需要考虑磁盘I/O效率、数据冗余、错误率控制等因素...

    java源码:预输入搜索 Cleo.zip

    它采用了一些先进的数据结构和算法,如Trie树(字典树)和Bloom Filter,以实现高效的数据存储和查询。下面我们将逐一解析这些关键组件。 1. **Trie树**:Trie树是一种字符串查找的数据结构,每个节点代表一个前缀...

    常见算法面试题--海量数据专题.doc

    这些题目展示了在处理大规模数据时常见的策略,如分而治之、哈希映射、Bloom Filter、Trie树、分布式计算(如MapReduce)等。这些方法都是为了在有限的内存条件下高效地处理大数据集,降低时间复杂度,以及在必要时...

    Filter Solution v11.0

    1. **数据过滤算法**:Filter Solution可能包含多种先进的过滤算法,如Bloom Filter、Trie树、Bitwise Filter等,用于快速定位和剔除特定数据,同时保持较低的误报率。 2. **高性能处理**:软件可能优化了多线程...

    Towards Practical Use of Bloom Filter based IP Lookup in Operational Network

    特别是,前缀布隆过滤器(Prefix Bloom Filter, PBF)被提出,旨在利用片上布隆过滤器来代表用于查找最长匹配前缀的trie树结构。PBF能够在平均情况下大幅减少对片外内存的访问次数,相比传统的三态内容寻址存储器...

    海量排序总结.txt

    在处理海量数据时,Bloom Filter是一种非常高效的数据结构,主要用于判断一个元素是否在一个集合中,具有空间效率高和查询速度快的特点。它通过将元素映射到一个位数组中来实现这一点。 1. **原理介绍**:Bloom ...

    Java_一个简单的搜索引擎,用于学习基本概念.zip

    总结来说,这个Java实现的简单搜索引擎涵盖了以下知识点:倒排索引、搜索算法(如Trie树和Bloom Filter)、文件I/O、相关性排序(TF-IDF和PageRank)、线程安全与并发控制以及项目结构设计。通过实践这个项目,初学...

    以太坊的数据结构(状态树、交易树、收据树)及代码分析

    文章目录一、状态树1.1 trie1.2 Patricia tree(trie)1.3 Merkle Patricia tree(trie)1.4 Modified Merkle Patricia tree(trie)1.5 账户状态值存储二...Merkle Patricia tree(trie)2.3 布隆过滤器(bloom filter)2.4 总结...

    CPPNotes:【C++ 面试 + C++ 学习指南】 一份涵盖大部分 C++ 程序员所需要掌握的核心知识

    CPPNotes 如下是 C++ 后台研发技术路线以及知识点,...BloomFilter原理 Trie树原理 LSM树原理 linux下操作命令以及工具 工作中常用的linux 命令 编译工具GCC 调试工具GDB 性能优化工具Perf 内存泄露检查工具Valgrind

    《Java面试必知必会》-海量数据类高频问题和参考答案.pdf

    - **处理策略**:分而治之(hash映射)、数据结构优化(如Bloom filter、Bitmap、Trie树、堆、数据库索引等)、分布式处理(Hadoop、MapReduce)。 3. **Bloom Filter** - **应用**:数据判重、集合交集判断。 -...

    海量数据处理方法

    海量数据处理是指基于海量数据上的存储、处理、操作,解决方案包括巧妙的算法搭配适合的数据结构,如 Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie 树,以及大而化小、分而治之的策略。根据数据处理的场景,...

Global site tag (gtag.js) - Google Analytics