快速分块库。
fastchunking的Python项目详细描述
它是什么
快速分块是一个包含高效且易于使用的python库 字符串分块算法的实现。
它是作为萨尔大学CISPA工作的一部分开发的。
安装
$ pip install fastchunking
注意
由于性能原因，该库的部分是用C++实现的。 因此，从源发行版安装需要 正确配置C++编译器。
用法和概述
快速分块为不同的字符串分块提供了有效的实现 算法，例如静态分块（SC）和内容定义分块（CDC）。
静态分块（SC）
静态分块将消息拆分为固定大小的分块。
- 让我们考虑一个应分块的随机示例消息：
>>> import os >>> message = os.urandom(1024*1024)
- 在对单个消息进行分块时，静态分块非常简单：
>>> import fastchunking >>> sc = fastchunking.SC() >>> chunker = sc.create_chunker(chunk_size=4096) >>> chunker.next_chunk_boundaries(message) [4096, 8192, 12288, ...]
- 大消息也可以分块，但是：
>>> chunker = sc.create_chunker(chunk_size=4096) >>> chunker.next_chunk_boundaries(message[:10240]) [4096, 8192] >>> chunker.next_chunk_boundaries(message[10240:]) [2048, 6144, 10240, ...]
内容定义分块（cdc）
快速分块支持内容定义的分块，即消息的分块 变长的碎片。
目前，支持基于rabin-karp滚动哈希的分块策略。
由于在普通python字符串上滚动哈希计算速度非常慢， 任何解释器，大多数计算都是由C++扩展来执行的。 基于daniel lemire的ngramhashing库，请参见： https://github.com/lemire/rollinghashcpp
- 让我们考虑一个应该分块的随机消息：
>>> import os >>> message = os.urandom(1024*1024)
使用静态分块时，必须指定滚动哈希窗口大小（此处： 48字节）和影响伪随机分布的可选种子值 生成的块边界的。
- 尽管如此，用法与静态分块类似：
>>> import fastchunking >>> cdc = fastchunking.RabinKarpCDC(window_size=48, seed=0) >>> chunker = cdc.create_chunker(chunk_size=4096) >>> chunker.next_chunk_boundaries(message) [7475, 10451, 12253, 13880, 15329, 19808, ...]
- 分块很简单：
>>> chunker = cdc.create_chunker(chunk_size=4096) >>> chunker.next_chunk_boundaries(message[:10240]) [7475] >>> chunker.next_chunk_boundaries(message[10240:]) [211, 2013, 3640, 5089, 9568, ...]
多级分块（ml-*）
同一类型的多个块（但块大小不同）可以是 有效地并行使用，例如，执行多级分块[LS16]。
-
再次，让我们考虑一个应该分块的随机消息：
>>> import os >>> message = os.urandom(1024*1024)
- 使用多级分块（例如ML-CDC）很容易：
>>> import fastchunking >>> cdc = fastchunking.RabinKarpCDC(window_size=48, seed=0) >>> chunk_sizes = [1024, 2048, 4096] >>> chunker = cdc.create_multilevel_chunker(chunk_sizes) >>> chunker.next_chunk_boundaries_with_levels(message) [(1049, 2), (1511, 1), (1893, 2), (2880, 1), (2886, 0), (3701, 0), (4617, 0), (5809, 2), (5843, 0), ...]
每个元组中的第二个值指示导致 边界。这里，第一个边界是chunker创建的边界 索引2，即目标块大小为4096字节的分块器。
注意
如果多个块产生相同的结果，则只输出最高的索引 边界。
警告
块大小必须按正确的顺序传递，即从最低到最高 价值。
性能
静态分块的计算成本几乎无法测量：正如分块一样
不取决于实际的消息，而只取决于它的长度，计算成本是
本质上仅限于一个xrange调用。
然而，内容定义的分块是昂贵的：算法必须计算 在的每个字节位置滚动哈希窗口内容的哈希值 要分块的消息。为了最小化成本，快速分块的工作方式如下：
- The message (fragment) is passed in its entirety to the C++ extension.
- Chunking is performed within the C++ extension.
- The resulting list of chunk boundaries is communicated back to Python and converted into a Python list.
基于100 mib的随机内容，作者测量了以下吞吐量 在英特尔酷睿i7-4770k上使用 Python 3.5（Windows x86-64）：
chunk size throughput 64 bytes 118 MiB/s 128 bytes 153 MiB/s 256 bytes 187 MiB/s 512 bytes 206 MiB/s 1024 bytes 221 MiB/s 2048 bytes 226 MiB/s 4096 bytes 231 MiB/s 8192 bytes 234 MiB/s 16384 bytes 233 MiB/s 32768 bytes 234 MiB/s
测试
快速分块使用tox进行测试，因此只需运行：
$ tox
- 参考文献：
[LS16] (1, 2) Dominik Leibenger and Christoph Sorge (2016). sec-cs: Getting the Most out of Untrusted Cloud Storage. arXiv:1606.03368
欢迎加入QQ群-->： 979659372
