ugrep indexer下载 - ugrep indexer源代码下载

ugrep indexer

其他源码

v1.0.0

下载

用于加速 grep 的单调索引器

ugrep-indexer实用程序递归地索引文件以加速递归 grep。

当使用命令行选项指定时，还会对存档和压缩文件的内容建立索引。当它们的内容都不与指定模式匹配时，这消除了对它们的搜索。

ugrep 是一个与 grep 兼容的快速文件搜索器，支持基于索引的搜索。基于索引的搜索在慢速文件系统上以及文件系统缓存无效时可以显着加快：如果搜索的驱动器上的文件系统未缓存在 RAM 中，即“冷”，则索引将加快搜索速度。它仅使用文件索引搜索那些可能与指定正则表达式模式匹配的文件。该索引允许快速检查是否存在潜在匹配，因此我们避免搜索所有文件。

使用 ugrep 进行基于索引的搜索是安全的，并且永远不会跳过现在可能匹配的更新文件。如果在索引后添加或更改了任何文件和目录，则搜索将始终通过将文件和目录时间戳与索引时间戳进行比较来搜索对文件系统所做的这些添加和更改。

当在索引后添加或更改许多文件时，我们可能需要重新索引以使索引保持最新。重新索引是增量式的，因此不会像初始索引过程那样花费那么多时间。

基于索引的搜索的典型但小示例，例如位于单独驱动器上的 ugrep v3.12.6 存储库：

 $ cd drive/ugrep
$ ugrep-indexer -I

12247077 bytes scanned and indexed with 19% noise on average
    1317 files indexed in 28 directories
      28 new directories indexed
    1317 new files indexed
       0 modified files indexed
       0 deleted files removed from indexes
     128 binary files ignored with --ignore-binary
       0 symbolic links skipped
       0 devices skipped
 5605227 bytes indexing storage increase at 4256 bytes/file

在没有索引的冷文件系统上正常搜索需要 1.02 秒，卸载drive并再次挂载以清除 FS 缓存以记录索引的效果：

 $ ugrep -I -l 'std::chrono' --stats
src/ugrep.cpp

Searched 1317 files in 28 directories in 1.02 seconds with 8 threads: 1 matching (0.07593%)

对于相同的冷搜索，Ripgrep 13.0.0 需要更长的时间，为 1.18 秒（ripgrep 默认情况下会跳过二进制文件，因此未指定选项-I ）：

 $ time rg -l 'std::chrono'
src/ugrep.cpp
    1.18 real         0.01 user         0.06 sys

相比之下，使用索引，在卸载drive并再次挂载以清除 FS 缓存以记录索引的效果后，使用 ugrep 搜索冷文件系统只需 0.0487 秒，速度提高了 21 倍：

 $ ugrep --index -I -l 'std::chrono' --stats
src/ugrep.cpp

Searched 1317 files in 28 directories in 0.0487 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1316 of 1317 files with non-matching indexes

经过的时间总是存在一些差异，四次搜索运行的最佳时间为 0.0487 秒，产生的搜索时间范围为 0.0487（21 倍加速）到 0.0983 秒（10 倍加速）。

与这个小型演示相比，速度的提升通常会明显更高，具体取决于几个因素：索引文件的大小、文件系统的读取速度以及假设大多数文件是冷的。

我设计的索引算法被证明是单调的：更高的精度通过降低误报率来保证提高搜索性能，但也增加了索引存储开销。同样，较低的精度会降低搜索性能，但也会减少索引存储开销。因此，我将我的索引器命名为单调索引器。

如果文件存储空间非常宝贵，那么我们可以通过指定较低的索引精度来降低索引存储开销。

使用级别 0（选项-0 ）对上面的示例进行索引可将索引存储开销减少 8.6 倍，从每个文件 4256 字节减少到每个文件区区 490 字节：

 12247077 bytes scanned and indexed with 42% noise on average
    1317 files indexed in 28 directories
       0 new directories indexed
    1317 new files indexed
       0 modified files indexed
       0 deleted files removed from indexes
     128 binary files ignored with --ignore-binary
       0 symbolic links skipped
       0 devices skipped
  646123 bytes indexing storage increase at 490 bytes/file

在此示例中，索引搜索仍然比非索引搜索快 12 倍，实际搜索了 16 个文件（15 个误报）：

 Searched 1317 files in 28 directories in 0.0722 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1301 of 1317 files with non-matching indexes

比此示例更复杂的正则表达式模式自然可能具有更高的误报率，即文件被认为可能匹配但实际上不匹配的比率。当误报率大到足以产生影响时，较高的误报率可能会降低搜索速度。

下表显示了索引准确性如何影响索引存储以及每个索引文件的平均噪声。最右边的列显示ugrep --index -I -l 'std::chrono'的搜索速度和误报率：

附件	索引存储（KB）	平均噪音	误报	搜索时间（秒）
`-0`	第631章	42%	15	0.0722
`-1`	1276	39%	1	0.0506
`-2`	第1576章	36%	0	0.0487
`-3`	2692	31%	0	乌奇
`-4`	2966	28%	0	乌奇
`-5`	4953	23%	0	乌奇
`-6`	5474	19%	0	乌奇
`-7`	9513	15%	0	乌奇
`-8`	10889	11%	0	乌奇
`-9`	13388	7%	0	乌奇

如果指定的正则表达式匹配更多可能的模式，例如使用搜索ugrep --index -I -l '(todo|TODO)[: ]' ，那么我们可能会在搜索的 1317 个文件中观察到更高的误报率，导致搜索时间稍长：

附件	误报	搜索时间（秒）
`-0`	189	0.292
`-1`	69	0.122
`-2`	43	0.103
`-3`	19	0.101
`-4`	16	0.097
`-5`	2	0.096
`-6`	1	乌奇
`-7`	0	乌奇
`-8`	0	乌奇
`-9`	0	乌奇

精度-4是默认值（之前的旧版本中为-5 ），对于使用适度复杂性的正则表达式模式进行搜索来说，它往往非常有效。

一句警告。检查索引总是会产生一点点开销。这意味着，如果所有文件都已缓存在 RAM 中，因为最近搜索或读取了文件，那么索引显然不一定会加快搜索速度。在这种情况下，非索引搜索可能会更快。此外，基于索引的搜索启动时间较长。当使用必须转换为哈希表的 Unicode 字符类和通配符时，启动时间会增加。

总而言之，当搜索大量冷文件并且正则表达式模式不匹配太多时，基于索引的搜索是最有效的，即我们希望限制无限重复*和+的使用，并限制 Unicode 字符类的使用可能的。这减少了 ugrep 启动时间并限制了误报模式匹配的比率（另请参阅下面的问答）。

快速示例

递归地增量索引所有显示进度的非二进制文件：

 ugrep-indexer -I -v

递归地增量索引所有非二进制文件，包括存储在存档和压缩文件中的非二进制文件，显示进度：

 ugrep-indexer -z -I -v

增量索引所有非二进制文件，包括存档和压缩文件，显示进度，跟踪文件的符号链接（但不跟踪目录），但不索引与 .gitignore 中的 glob 匹配的文件和目录：

 ugrep-indexer -z -I -v -S -X

强制重新索引所有非二进制文件（包括存档和压缩文件），遵循文件的符号链接（但不是目录），但不索引与 .gitignore 中的 glob 匹配的文件和目录：

 ugrep-indexer -f -z -I -v -S -X

相同，但通过将索引精度从 5（默认）降低到 0，将索引文件存储量降至最低：

 ugrep-indexer -f -0 -z -I -v -S -X

通过将索引精度从 5（默认）提高到 7，以更大的索引文件为代价来提高搜索性能：

 ugrep-indexer -f7zIvSX

递归删除所有隐藏的._UG#_Store索引文件，将目录树恢复为非索引状态：

 ugrep-indexer -d

构建步骤

配置并编译：

 ./build.sh

如果需要但不是必需的，请安装：

 sudo make install

未来的增强功能

添加一个选项来创建一个索引文件，例如明确指定为ugrep。如果索引文件位于快速文件系统上，这可以进一步提高索引搜索速度。否则，不要期望有太大的改进，甚至可能会减慢，因为无法同时搜索单个索引文件，并且实际上会跳过目录（也跳过它们的索引），并且会检查更多索引条目。实验会告诉你答案。这种方法的一个重要警告是，使用ugrep --index基于索引的搜索不再安全：尚未建立索引的新文件和修改后的文件将不会被搜索。
每个 N-gram 布隆过滤器在哈希表中都有自己的“位层”，以避免哈希冲突。例如，2-gram 不与 3-gram 共享任何位。这确保了我们永远不会出现任何误报，即错误匹配实际上不属于模式的字符。然而，1-gram（单个字符）位空间很小（最多 256 位）。因此，当哈希表较大时，我们会浪费一些位。减少浪费的一种可能方法是将 1-gram 与 2-gram 组合起来共享相同的位空间。如果我们认为 1-gram 等于 2-gram，且第二个字符设置为 (NUL)，那么这很容易做到。我们可以使用基于不同哈希方法的第二个 2 元哈希来降低误报率。或者我们可以将“位层”从 8 扩展到 9 以存储 9-gram。这将提高较长模式（9 个或更长）的索引准确性，而无需额外成本。另一方面，当错误匹配不属于模式一部分的字符时，这种更改可能会导致更多误报；我们失去了完美的 1 克精度的优势。

问答

问：它是如何运作的？

索引将隐藏索引文件._UG#_Store添加到每个索引目录。 ugrep-indexer 扫描索引的文件（从未更改！）以生成索引文件。

索引文件的大小取决于指定的精度， -0最低（小索引文件）， -9最高（大索引文件）。默认精度为-4 。有关准确度对索引大小与搜索速度的影响的详细信息，请参阅下一个问题。

索引永远不会遵循目录的符号链接，因为符号链接的目录可能位于文件系统中的任何位置，或者位于我们不希望添加索引文件的另一个文件系统中。您仍然可以使用 ugrep-indexer 选项-S为文件的符号链接建立索引。

选项-v ( --verbose ) 显示索引进度和每个索引文件的“噪音”。噪声是输入中熵或随机性的度量。较高的噪声水平意味着索引在表示文件内容方面不太准确。例如，具有随机数据的大文件很难准确索引，并且会产生高水平的噪声。

索引的复杂性与要索引的给定文件的大小成线性关系。实际上，这不是一个快速的过程，也没有那么快的搜索，并且可能需要一些时间才能完成对大型目录树的完整索引传递。索引完成后，ugrep-indexer 显示索引结果。还报告了添加的索引的总大小和平均索引噪声。

扫描文件以索引会生成 64KB 索引哈希表。然后，ugrep 索引器使用按位压缩将表减半，只要不超过目标精度。减半之所以成为可能，是因为该表在距模式开头的偏移处对 8 个窗口的哈希值进行编码，对应于每个索引哈希表单元的 8 位。组合表的两半可能会将某些位从 1 翻转到 0，这可能会导致误报匹配。这证明了索引器的单调性。零位哈希值表示可能的匹配。

ugrep-indexer 检测“二进制文件”，可以忽略这些文件，并且不使用 ugrep-indexer 选项-I ( --ignore-binary ) 对其进行索引。当使用 ugrep 选项-I ( --ignore-binary ) 搜索以忽略二进制文件时，这非常有用，这是一种典型的场景。

当使用选项-X ( --ignore-files ) 指定时，ugrep-indexer 遵循 .gitignore 文件排除。被忽略的文件和目录将不会被索引以节省文件系统空间。当使用 ugrep 选项--ignore-files搜索文件时，这非常有效。

可以中止索引，例如使用 CTRL-C，这不会导致 ugrep 的搜索功能丧失，但只会使目录结构仅部分索引。

选项-c检查索引中是否有过时的引用以及未索引的文件和目录。

使用 ugrep-indexer 选项-d删除索引。

通过将ugrep --index搜索结果与具有数千种随机搜索模式的数千个文件上的“慢”非索引ugrep搜索结果进行比较，ugrep-indexer 已经过广泛的测试。

基于索引的搜索适用于除选项-v ( --invert-match )、 --filter 、 -P ( --perl-regexp ) 和-Z ( --fuzzy ) 之外的所有 ugrep 选项。选项-c ( --count ) 和--index自动设置--min-count=1以跳过所有匹配为零的文件。

如果在索引后更新、添加或删除了任何文件或目录，则 ugrep --index将始终搜索这些文件和目录（当它们出现在递归搜索路径上时）。您可以再次运行ugrep-indexer来增量更新所有索引。

正则表达式模式由 ugrep 使用选项--index在内部转换为哈希表的形式，最多包含指定正则表达式模式的前 16 个字节，可能更短，以便在正则表达式模式复杂时减少构建时间。因此，要搜索的正则表达式模式的前 8 到 16 个字符是最关键的，不应匹配太多，以限制可能减慢搜索速度的所谓误报匹配。

在 ugrep 中，正则表达式模式被转换为 DFA。在 DFA 之上构建索引哈希有限自动机 (HFA)，以将哈希表紧凑地表示为带有标记边缘的状态转换。该 HFA 最多由八层组成，每层移位一个字节以表示模式上的下一个 8 字节窗口。每个 HFA 层都对模式的该部分的索引哈希进行编码。选择的索引哈希函数是“加法”，这意味着当与前一个哈希进行哈希处理时，会添加下一个字节。这非常重要，因为它极大地减少了 HFA 建设开销。我们现在可以将标记的 HFA 转换编码为具有 16 位哈希值范围的多个边，而不是一组每个具有单独哈希值的单边。为此，我使用从std::set<T>派生的开放式范围库reflex::ORanges<T> 。

下面给出了一个非常简单的单字符串maybe_match()函数和素数 61 索引哈希函数，以演示基于索引的单个字符串搜索：

 // prime 61 hashing
uint16_t indexhash(uint16_t h, uint8_t b, size_t size)
{
  return ((h << 6) - h - h - h + b) & (size - 1);
}

// return possible match of string given array of hashes of size <= 64K (power of two)
bool maybe_match(const char *string, uint8_t *hashes, size_t size)
{
  size_t len = strlen(string); // practically we can and should limit len to e.g. 15 or 16
  for (const char *window = string; len > 0; ++window, --len)
  {
    uint16_t h = window[0] & (size - 1);
    if (hashes[h] & 0x01)
      return false
    size_t k, n = len < 8 ? len : 8;
    for (k = 1; k < n; ++k)
    {
      h = indexhash(h, window[k], size);
      if (hashes[h] & (1 << k))
        return false;
    }
  }
  return true;
}

使用真实的实验设置从许多其他可能的散列函数中选择了素数 61 散列。通过从 100MB 维基百科文件中反复搜索随机抽取的单词来测试候选哈希函数。这个词被一个、两个或三个随机字母变异。检查此突变以确保它与维基百科文件中的实际有效单词不对应。然后，每当突变单词与文件匹配时，就会记录误报率。总体而言，具有最小误报率的哈希函数应该是一个很好的候选函数。

通过使用 8 的窗口（或更短，取决于模式长度），与标准布隆过滤器相比，误报率更低。更具体地说，在布隆过滤器中使用N²哈希函数代替N。对于较短的模式， N通常太小而无法限制误报。因此， N²更有效。它还会拒绝匹配中任何在该模式的前 8 个字节中任何位置具有字符的模式，该字符实际上不会出现在索引文件中的任何位置，而标准布隆过滤器可能会出现误报匹配。此外，用于索引哈希表的位寻址可以实现高效的表压缩。

问：什么是分度精度？

索引是有损压缩的一种形式。索引精度越高，ugrep 搜索性能应该越快，可以跳过更多不匹配的文件。较高的精度可降低噪声（损耗较小）。高水平的噪音会导致 ugrep 有时搜索不匹配的索引文件。我们称这些为“误报匹配”。更高的精度需要更大的索引文件。通常我们预计每个文件平均有 4K 或更少的索引存储。每个文件的索引存储最小值为 128 字节，不包括文件名和 4 字节索引标头。对于非常大的噪声文件，每个文件的最大存储空间为 64K 字节。

使用ugrep --index --stats搜索索引文件时，选项--stats显示基于索引的搜索完成后的搜索统计信息。当许多文件由于索引噪声（即误报）而未被跳过搜索时，更高的准确度有助于提高索引的有效性，这可能会加快搜索速度。

问：UTF-16 和 UTF-32 文件怎么样？

UTF-16 和 UTF-32 文件也被索引。索引器在内部将它们转换为 UTF-8 进行索引后，将它们视为 UTF-8。

问：为什么要为档案和压缩文件建立索引？

通过归档 (zip/tar/pax/cpio) 和压缩文件来节省磁盘空间。另一方面，搜索档案和压缩文件比搜索常规文件慢得多。使用ugrep-indexer -z -I对档案和压缩文件建立索引并使用ugrep -z -I --index PATTERN搜索它们可加快搜索速度，即跳过档案和压缩文件时。另一方面，随着归档和压缩文件的索引文件条目的添加，磁盘存储需求将会增加。请注意，当存档和压缩文件包含二进制文件时，选项-I会忽略这些二进制文件。

问：为什么使用选项 --index 时 ugrep 的启动时间更长？

ugrep --index构建索引哈希表的启动开销取决于正则表达式模式。如果正则表达式模式非常“宽松”，即匹配许多可能的模式，则ugrep --index计算哈希表的启动时间会显着增加。当使用大型 Unicode 字符类和通配符时，尤其是使用无限的*和+重复时，可能会发生这种情况。要了解启动时间如何增加，请使用选项ugrep --index -r PATTERN /dev/null --stats=vm用您的 PATTERN 搜索 /dev/null 。