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 個位元組中任何位置具有字元的模式，該字元實際上不會出現在索引檔案中的任何位置，而標準布隆過濾器可能會出現誤報匹配。此外，用於索引雜湊表的位元尋址可以實現高效的表壓縮。

Q：什麼是分度精度？

索引是有損壓縮的一種形式。索引精度越高，ugrep 搜尋效能應該越快，可以跳過更多不匹配的檔案。較高的精度可降低雜訊（損耗較小）。高水準的噪音會導致 ugrep 有時搜尋不匹配的索引檔。我們稱這些為「誤報匹配」。更高的精度需要更大的索引檔。通常我們預期每個檔案平均有 4K 或更少的索引儲存。每個檔案的索引儲存最小值為 128 位元組，不包括檔案名稱和 4 個位元組索引標頭。對於非常大的雜訊文件，每個文件的最大儲存空間為 64K 位元組。

使用ugrep --index --stats搜尋索引檔案時，選項--stats顯示基於索引的搜尋完成後的搜尋統計資料。當許多文件因索引雜訊（即誤報）而未被跳過搜尋時，更高的準確度有助於提高索引的有效性，這可能會加快搜尋速度。

Q：UTF-16 和 UTF-32 檔案怎麼樣？

UTF-16 和 UTF-32 文件也被索引。索引器在內部將它們轉換為 UTF-8 進行索引後，將它們視為 UTF-8。

Q：為什麼要為檔案和壓縮檔案建立索引？

透過歸檔 (zip/tar/pax/cpio) 和壓縮檔案來節省磁碟空間。另一方面，搜尋檔案和壓縮文件比搜尋常規文件慢得多。使用ugrep-indexer -z -I對檔案和壓縮檔案建立索引並使用ugrep -z -I --index PATTERN搜尋它們可加快搜尋速度，即跳過檔案和壓縮檔案時。另一方面，隨著歸檔和壓縮檔案的索引檔案條目的添加，磁碟儲存需求將會增加。請注意，當存檔和壓縮檔案包含二進位檔案時，選項-I會忽略這些二進位檔案。

Q：為什麼使用選項 --index 時 ugrep 的啟動時間較長？

ugrep --index建立索引雜湊表的啟動開銷取決於正規表示式模式。如果正規表示式模式非常“寬鬆”，即匹配許多可能的模式，則ugrep --index計算雜湊表的啟動時間會顯著增加。當使用大型 Unicode 字元類別和通配符時，尤其是使用無限的*和+重複時，可能會發生這種情況。若要了解啟動時間如何增加，請使用選項ugrep --index -r PATTERN /dev/null --stats=vm用您的 PATTERN 搜尋 /dev/null 。