ugrep indexer

ตัวสร้างดัชนีแบบโมโนโทนิกเพื่อเร่งการ grepping

ยูทิลิตี ugrep-indexer จัดทำดัชนีไฟล์แบบเรียกซ้ำเพื่อเพิ่มความเร็วในการ grepping แบบเรียกซ้ำ

นอกจากนี้เนื้อหาของไฟล์เก็บถาวรและไฟล์บีบอัดจะถูกจัดทำดัชนีเมื่อระบุด้วยตัวเลือกบรรทัดคำสั่ง วิธีนี้จะกำจัดการค้นหาเมื่อไม่มีเนื้อหาใดที่ตรงกับรูปแบบที่ระบุ

ugrep เป็นตัวค้นหาไฟล์ที่รวดเร็วซึ่งเข้ากันได้กับ grep ซึ่งรองรับการค้นหาตามดัชนี การค้นหาตามดัชนีสามารถทำได้เร็วขึ้นอย่างมากในระบบไฟล์ที่ช้า และเมื่อการแคชระบบไฟล์ไม่ได้ผล: หากระบบไฟล์บนไดรฟ์ที่ค้นหาไม่ได้ถูกแคชไว้ใน RAM กล่าวคือ เป็น "เย็น" การทำดัชนีจะทำให้การค้นหาเร็วขึ้น ค้นหาเฉพาะไฟล์ที่อาจตรงกับรูปแบบ regex ที่ระบุโดยใช้ดัชนีของไฟล์ ดัชนีนี้ช่วยให้ตรวจสอบได้อย่างรวดเร็วว่ามีรายการที่ตรงกันหรือไม่ ดังนั้นเราจึงหลีกเลี่ยงการค้นหาไฟล์ทั้งหมด

การค้นหาตามดัชนีด้วย 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

การค้นหาปกติบนระบบไฟล์แบบ Cold ที่ไม่มีการจัดทำดัชนีจะใช้เวลา 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

ในทางตรงกันข้าม เมื่อใช้การทำดัชนี การค้นหาระบบไฟล์แบบ cold จะใช้เวลาเพียง 0.0487 วินาทีด้วย ugrep ซึ่งเร็วกว่า 21 เท่า หลังจากยกเลิกการต่อเชื่อม drive และติดตั้งอีกครั้งเพื่อล้างแคช FS เพื่อบันทึกผลของการทำดัชนี:

 $ 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 เท่า)

ความเร็วที่เพิ่มขึ้นอาจสูงขึ้นอย่างมากโดยทั่วไปเมื่อเทียบกับการสาธิตขนาดเล็กนี้ ขึ้นอยู่กับปัจจัยหลายประการ ขนาดของไฟล์ที่จัดทำดัชนี ความเร็วในการอ่านของระบบไฟล์ และสมมติว่าไฟล์ส่วนใหญ่เป็นไฟล์เย็น

อัลกอริธึมการจัดทำดัชนีที่ฉันออกแบบนั้นมี ความซ้ำซากจำเจที่พิสูจน์ได้ : ความแม่นยำที่สูงขึ้นรับประกันประสิทธิภาพการค้นหาที่เพิ่มขึ้นโดยการลดอัตราผลบวกลวง แต่ยังเพิ่มค่าใช้จ่ายในการจัดเก็บดัชนีด้วย ในทำนองเดียวกัน ความแม่นยำที่ต่ำกว่าจะลดประสิทธิภาพการค้นหา แต่ยังลดค่าใช้จ่ายในการจัดเก็บดัชนีด้วย ดังนั้นฉันจึงตั้งชื่อตัวสร้างดัชนีของฉันว่า ตัวสร้างดัชนีแบบ monotonic

หากพื้นที่จัดเก็บไฟล์อยู่ในระดับพรีเมี่ยม เราสามารถลดค่าใช้จ่ายการจัดเก็บดัชนีลงได้โดยการระบุความแม่นยำในการจัดทำดัชนีที่ต่ำกว่า

การทำดัชนีตัวอย่างจากด้านบนด้วยระดับ 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

รูปแบบ Regex ที่ซับซ้อนกว่าตัวอย่างนี้อาจมีอัตราผลบวกลวงที่สูงกว่าตามธรรมชาติ ซึ่งเป็นอัตราของไฟล์ที่ถือว่าอาจเข้าคู่กันเมื่อไม่เป็นเช่นนั้น อัตราผลบวกลวงที่สูงกว่าอาจลดความเร็วในการค้นหาเมื่อมีอัตราสูงพอที่จะส่งผลกระทบ

ตารางต่อไปนี้แสดงให้เห็นว่าความแม่นยำในการจัดทำดัชนีส่งผลต่อพื้นที่จัดเก็บการทำดัชนีและเสียงรบกวนโดยเฉลี่ยต่อไฟล์ที่ทำดัชนีอย่างไร คอลัมน์ขวาสุดแสดงความเร็วในการค้นหาและอัตราผลบวกลวงสำหรับ 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	ไม่เลย

หาก regex ที่ระบุตรงกับรูปแบบที่เป็นไปได้อื่นๆ อีกมากมาย เช่น กับการค้นหา 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 ก่อนหน้านี้ในรุ่นเก่า) ซึ่งมีแนวโน้มที่จะทำงานได้ดีมากในการค้นหาด้วยรูปแบบ regex ที่มีความซับซ้อนเล็กน้อย

คำเตือนหนึ่งคำ มีค่าใช้จ่ายเล็กน้อยในการตรวจสอบดัชนีเสมอ ซึ่งหมายความว่าหากไฟล์ทั้งหมดถูกแคชไว้ใน RAM แล้ว เนื่องจากไฟล์ถูกค้นหาหรืออ่านเมื่อเร็วๆ นี้ การจัดทำดัชนีจะไม่ทำให้การค้นหาเร็วขึ้นโดยไม่จำเป็น ในกรณีนั้น การค้นหาที่ไม่จัดทำดัชนีอาจเร็วกว่า นอกจากนี้ การค้นหาตามดัชนียังมีเวลาเริ่มต้นที่นานขึ้น เวลาเริ่มต้นนี้จะเพิ่มขึ้นเมื่อมีการใช้คลาสอักขระ Unicode และไวด์การ์ดที่ต้องแปลงเป็นตารางแฮช

โดยสรุป การค้นหาตามดัชนีจะมีประสิทธิภาพสูงสุดเมื่อค้นหาไฟล์ Cold จำนวนมาก และเมื่อรูปแบบ regex ไม่ตรงกันมากเกินไป เช่น เราต้องการจำกัดการใช้การทำซ้ำไม่จำกัด * และ + และจำกัดการใช้คลาสอักขระ Unicode เมื่อ เป็นไปได้. ซึ่งจะช่วยลดเวลาเริ่มต้น ugrep และจำกัดอัตราของการจับคู่รูปแบบผลบวกลวง (ดูคำถาม & คำตอบด้านล่าง)

ตัวอย่างด่วน

จัดทำดัชนีไฟล์ที่ไม่ใช่ไบนารีซ้ำ ๆ และเพิ่มขึ้นทั้งหมดที่แสดงความคืบหน้า:

 ugrep-indexer -I -v

จัดทำดัชนีไฟล์ที่ไม่ใช่ไบนารี่ซ้ำและแบบเพิ่มทีละไฟล์ รวมถึงไฟล์ที่ไม่ใช่ไบนารี่ที่จัดเก็บไว้ในไฟล์เก็บถาวรและในไฟล์บีบอัด แสดงความคืบหน้า:

 ugrep-indexer -z -I -v

สร้างดัชนีไฟล์ที่ไม่ใช่ไบนารี่ทั้งหมดเพิ่มขึ้น รวมถึงไฟล์เก็บถาวรและไฟล์บีบอัด แสดงความคืบหน้า ติดตามลิงก์สัญลักษณ์ไปยังไฟล์ (แต่ไม่ใช่ไดเร็กทอรี) แต่อย่าสร้างดัชนีไฟล์และไดเร็กทอรีที่ตรงกับ globs ใน .gitignore:

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

บังคับให้สร้างดัชนีใหม่ของไฟล์ที่ไม่ใช่ไบนารี่ทั้งหมด รวมถึงไฟล์เก็บถาวรและไฟล์บีบอัด ตามลิงก์สัญลักษณ์ไปยังไฟล์ (แต่ไม่ใช่ไปยังไดเร็กทอรี) แต่อย่าสร้างดัชนีไฟล์และไดเร็กทอรีที่ตรงกับ globs ใน .gitignore:

 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 Bloom แต่ละตัวมี "ระดับบิต" ของตัวเองในตารางแฮชเพื่อหลีกเลี่ยงความขัดแย้งของแฮช ตัวอย่างเช่น 2 กรัมไม่แชร์บิตใดๆ กับ 3 กรัม เพื่อให้แน่ใจว่าเราจะไม่มีผลบวกลวงใดๆ กับอักขระที่จับคู่อย่างไม่ถูกต้องซึ่งจริงๆ แล้วไม่ได้เป็นส่วนหนึ่งของรูปแบบ อย่างไรก็ตาม พื้นที่บิต 1 กรัม (อักขระเดี่ยว) มีขนาดเล็ก (สูงสุด 256 บิต) ดังนั้นเราจึงเสียบิตไปเมื่อตารางแฮชมีขนาดใหญ่ขึ้น วิธีที่เป็นไปได้ในการลดของเสียคือการรวม 1 กรัมกับ 2 กรัมเพื่อใช้พื้นที่บิตเดียวกัน วิธีนี้ทำได้ง่ายหากเราพิจารณาว่า 1 กรัมเท่ากับ 2 กรัมโดยตั้งค่าอักขระตัวที่สองเป็น (NUL) เราสามารถลดอัตราผลบวกลวงได้ด้วยแฮช 2 กรัมอันที่สอง โดยอิงตามวิธีแฮชอื่น หรือเราสามารถขยาย "ระดับบิต" จาก 8 เป็น 9 เพื่อจัดเก็บ 9 กรัมได้ ซึ่งจะเพิ่มความแม่นยำในการจัดทำดัชนีสำหรับรูปแบบที่ยาวขึ้น (9 หรือนานกว่านั้น) โดยไม่มีค่าใช้จ่ายเพิ่มเติม ในทางกลับกัน การเปลี่ยนแปลงนั้นอาจทำให้เกิดผลบวกลวงมากขึ้นเมื่อมีการจับคู่อักขระที่ไม่ได้เป็นส่วนหนึ่งของรูปแบบไม่ถูกต้อง เราสูญเสียข้อได้เปรียบของความแม่นยำ 1 กรัมที่สมบูรณ์แบบ

ถามตอบ

ถาม: มันทำงานอย่างไร?

การทำดัชนีจะเพิ่มไฟล์ดัชนีที่ซ่อนอยู่ ._UG#_Store ลงในแต่ละไดเร็กทอรีที่ทำดัชนี ไฟล์ที่จัดทำดัชนีจะถูกสแกน (ไม่เคยเปลี่ยนแปลง!) โดย ugrep-indexer เพื่อสร้างไฟล์ดัชนี

ขนาดของไฟล์ดัชนีขึ้นอยู่กับความแม่นยำที่ระบุ โดย -0 เป็นค่าต่ำสุด (ไฟล์ดัชนีขนาดเล็ก) และ -9 เป็นค่าสูงสุด (ไฟล์ดัชนีขนาดใหญ่) ความแม่นยำเริ่มต้นคือ -4 ดูคำถามถัดไปสำหรับรายละเอียดเกี่ยวกับผลกระทบของความแม่นยำต่อขนาดการจัดทำดัชนีเทียบกับความเร็วในการค้นหา

การทำดัชนี จะไม่ติดตามลิงก์สัญลักษณ์ไปยังไดเร็กทอรี เนื่องจากไดเร็กทอรีที่ลิงก์เชิงสัญลักษณ์อาจอยู่ที่ใดก็ได้ในระบบไฟล์ หรือในระบบไฟล์อื่น ซึ่งเราไม่ต้องการเพิ่มไฟล์ดัชนี คุณยังคงสามารถสร้างดัชนีลิงก์สัญลักษณ์ไปยังไฟล์ด้วยตัวเลือก ugrep-indexer -S

ตัวเลือก -v ( --verbose ) แสดงความคืบหน้าในการจัดทำดัชนีและ "สัญญาณรบกวน" ของแต่ละไฟล์ที่จัดทำดัชนี สัญญาณรบกวนเป็นการวัด เอนโทรปี หรือ การสุ่ม ในอินพุต ระดับสัญญาณรบกวนที่สูงขึ้นหมายความว่าการจัดทำดัชนีมีความแม่นยำน้อยลงในการนำเสนอเนื้อหาของไฟล์ ตัวอย่างเช่น ไฟล์ขนาดใหญ่ที่มีข้อมูลแบบสุ่มนั้นยากต่อการจัดทำดัชนีอย่างแม่นยำและจะมีสัญญาณรบกวนในระดับสูง

ความซับซ้อนของการจัดทำดัชนีจะเป็นเส้นตรงในขนาดของไฟล์ที่กำหนดเพื่อจัดทำดัชนี ในทางปฏิบัติ มันไม่ใช่กระบวนการที่รวดเร็ว ไม่รวดเร็วในการค้นหา และอาจต้องใช้เวลาระยะหนึ่งในการจัดทำดัชนีแบบเต็มผ่านแผนผังไดเร็กทอรีขนาดใหญ่ เมื่อการจัดทำดัชนีเสร็จสิ้น ugrep-indexer จะแสดงผลลัพธ์ของการจัดทำดัชนี ขนาดรวมของดัชนีที่เพิ่มและสัญญาณรบกวนการจัดทำดัชนีเฉลี่ยก็ถูกรายงานด้วย

การสแกนไฟล์เพื่อจัดทำดัชนีจะทำให้ได้ตารางแฮชการจัดทำดัชนีขนาด 64KB จากนั้น ugrep-indexer จะแบ่งตารางลงครึ่งหนึ่งด้วยการบีบอัดบิตโดยใช้ระดับบิต และตราบใดที่ไม่เกินความแม่นยำของเป้าหมาย การลดจำนวนลงครึ่งหนึ่งเกิดขึ้นได้จากข้อเท็จจริงที่ว่าตารางเข้ารหัสแฮชสำหรับ 8 หน้าต่างที่ออฟเซ็ตจากจุดเริ่มต้นของรูปแบบ ซึ่งสอดคล้องกับ 8 บิตต่อเซลล์ตารางแฮชดัชนี การรวมสองส่วนของตารางเข้าด้วยกันอาจทำให้บิตบางส่วนจากหนึ่งส่วนกลายเป็นศูนย์ ซึ่งอาจทำให้เกิดการจับคู่ที่ผิดพลาดได้ นี่เป็นการพิสูจน์ความซ้ำซากจำเจของตัวทำดัชนี ค่าแฮชเป็นศูนย์บิตบ่งชี้ถึงการจับคู่ที่เป็นไปได้

ugrep-indexer ตรวจพบ "ไฟล์ไบนารี" ซึ่งสามารถละเว้นและไม่ได้จัดทำดัชนีด้วยตัวเลือก ugrep-indexer -I ( --ignore-binary ) สิ่งนี้มีประโยชน์เมื่อค้นหาด้วยตัวเลือก ugrep -I ( --ignore-binary ) เพื่อละเว้นไฟล์ไบนารีซึ่งเป็นสถานการณ์ทั่วไป

ตัวสร้างดัชนี ugrep ปฏิบัติตามการยกเว้นไฟล์ .gitignore เมื่อระบุด้วยตัวเลือก -X ( --ignore-files ) ไฟล์และไดเร็กทอรีที่ถูกละเว้นจะไม่ถูกสร้างดัชนีเพื่อประหยัดพื้นที่ระบบไฟล์ วิธีนี้ใช้ได้ดีเมื่อค้นหาไฟล์ด้วยตัวเลือก ugrep --ignore-files

การทำดัชนีสามารถถูกยกเลิกได้ เช่น ด้วย CTRL-C ซึ่งจะไม่ส่งผลให้สูญเสียความสามารถในการค้นหาด้วย ugrep แต่จะปล่อยให้โครงสร้างไดเร็กทอรีถูกสร้างดัชนีเพียงบางส่วนเท่านั้น

ตัวเลือก -c ตรวจสอบดัชนีสำหรับการอ้างอิงเก่าและไฟล์และไดเรกทอรีที่ไม่ได้จัดทำดัชนี

ดัชนีจะถูกลบด้วยตัวเลือก ugrep-indexer -d

ugrep-indexer ได้รับการทดสอบอย่างกว้างขวางโดยการเปรียบเทียบ ugrep --index ผลการค้นหากับผลการค้นหา ugrep ที่ไม่ได้จัดทำดัชนี "ช้า" ในไฟล์หลายพันไฟล์ที่มีรูปแบบการค้นหาแบบสุ่มนับพัน

การค้นหาตามดัชนีใช้งานได้กับตัวเลือก ugrep ทั้งหมดยกเว้นตัวเลือก -v ( --invert-match ), --filter , -P ( --perl-regexp ) และ -Z ( --fuzzy ) ตัวเลือก -c ( --count ) ด้วย --index จะตั้งค่า --min-count=1 โดยอัตโนมัติเพื่อข้ามไฟล์ทั้งหมดที่มีค่าตรงกันเป็นศูนย์

หากมีการอัปเดต เพิ่ม หรือลบไฟล์หรือไดเร็กทอรีใด ๆ หลังจากการจัดทำดัชนี ugrep --index จะค้นหาไฟล์และไดเร็กทอรีเหล่านี้เสมอเมื่อปรากฏบนพาธการค้นหาแบบเรียกซ้ำ คุณสามารถเรียกใช้ ugrep-indexer อีกครั้งเพื่ออัปเดตดัชนีทั้งหมดแบบเพิ่มหน่วย

รูปแบบ Regex จะถูกแปลงภายในโดย ugrep พร้อมตัวเลือก --index เป็นรูปแบบของตารางแฮชสูงสุด 16 ไบต์แรกของรูปแบบ regex ที่ระบุ ซึ่งอาจสั้นกว่าเพื่อลดเวลาในการก่อสร้างเมื่อรูปแบบ regex มีความซับซ้อน ดังนั้น อักขระ 8 ถึง 16 ตัวแรกของรูปแบบ regex ที่ใช้ค้นหาจึงมีความสำคัญที่สุด และไม่ควรจับคู่มากเกินไปเพื่อจำกัดสิ่งที่เรียกว่าการจับคู่ที่ผิดพลาดซึ่งอาจทำให้การค้นหาช้าลง

ใน ugrep รูปแบบ regex จะถูกแปลงเป็น DFA ระบบอัตโนมัติจำกัดแฮชการจัดทำดัชนี (HFA) ถูกสร้างขึ้นที่ด้านบนของ DFA เพื่อนำเสนอตารางแฮชอย่างกะทัดรัดเป็นการเปลี่ยนสถานะด้วยขอบที่มีป้ายกำกับ HFA นี้ประกอบด้วยมากถึงแปดเลเยอร์ โดยแต่ละเลเยอร์จะถูกเลื่อนไปหนึ่งไบต์เพื่อแสดงหน้าต่างขนาด 8 ไบต์ถัดไปเหนือรูปแบบ แต่ละเลเยอร์ HFA จะเข้ารหัสแฮชดัชนีสำหรับส่วนนั้นของรูปแบบ ฟังก์ชันแฮชดัชนีที่เลือกคือ "ส่วนเพิ่มเติม" ซึ่งหมายความว่าไบต์ถัดไปจะถูกเพิ่มเมื่อแฮชด้วยแฮชก่อนหน้า สิ่งนี้สำคัญมากเนื่องจากจะช่วยลดค่าใช้จ่ายในการก่อสร้าง HFA ลงอย่างมาก ขณะนี้เราสามารถเข้ารหัสการเปลี่ยนผ่าน HFA ที่มีป้ายกำกับเป็นสถานะเป็นหลายขอบด้วยช่วงค่าแฮช 16 บิต แทนที่จะเป็นชุดของขอบเดียวโดยแต่ละอันมีค่าแฮชแต่ละตัว ด้วยเหตุนี้ฉันใช้ไลบรารีช่วงปลายเปิดของฉัน reflex::ORanges<T> ที่ได้มาจาก std::set<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 ได้รับเลือกจากฟังก์ชันแฮชที่เป็นไปได้อื่นๆ มากมาย โดยใช้การตั้งค่าการทดลองที่สมจริง ฟังก์ชันการแฮชของผู้สมัครได้รับการทดสอบโดยการค้นหาคำที่สุ่มขึ้นมาซ้ำๆ จากไฟล์ Wikipedia ขนาด 100MB คำนี้กลายพันธุ์ด้วยตัวอักษรสุ่มหนึ่ง สอง หรือสามตัว การกลายพันธุ์นี้ได้รับการตรวจสอบเพื่อให้แน่ใจว่าไม่สอดคล้องกับคำที่ถูกต้องจริงในไฟล์ Wikipedia จากนั้นอัตราผลบวกลวงจะถูกบันทึกเมื่อใดก็ตามที่คำกลายพันธุ์ตรงกับไฟล์ ฟังก์ชันแฮชที่มีอัตราผลบวกลวงน้อยที่สุดควรเป็นตัวเลือกที่ดีโดยรวม

ด้วยการใช้หน้าต่าง 8 (หรือสั้นกว่านั้นขึ้นอยู่กับความยาวของรูปแบบ) อัตราผลบวกลวงจะต่ำกว่าเมื่อเทียบกับตัวกรอง Bloom มาตรฐาน โดยเฉพาะอย่างยิ่ง ฟังก์ชันแฮช N² ถูกใช้แทน N ในตัวกรอง Bloom สำหรับรูปแบบที่สั้นกว่า N มักจะน้อยเกินไปที่จะจำกัดผลบวกลวง ดังนั้น N² จึงมีประสิทธิภาพมากกว่า นอกจากนี้ยังปฏิเสธรูปแบบใดๆ จากการจับคู่ที่มีอักขระอยู่ที่ใดก็ได้ใน 8 ไบต์แรกของรูปแบบซึ่งไม่ได้เกิดขึ้นจริงที่ใดก็ได้ในไฟล์ที่จัดทำดัชนี ในขณะที่ตัวกรอง Bloom มาตรฐานอาจมีการจับคู่ที่เป็นผลบวกลวง นอกจากนี้ การกำหนดบิตแอดเดรสที่ใช้ในการจัดทำดัชนีตารางแฮชยังช่วยให้การบีบอัดตารางมีประสิทธิภาพอีกด้วย

ถาม: ความแม่นยำในการจัดทำดัชนีคืออะไร

การทำดัชนีเป็นรูปแบบหนึ่งของการบีบอัดข้อมูลแบบสูญเสีย ยิ่งความแม่นยำในการจัดทำดัชนีสูงเท่าใด ประสิทธิภาพการค้นหา 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 จะละเว้นไบนารีเหล่านี้

ถาม: เหตุใดเวลาเริ่มต้นของ ugrep จึงสูงกว่าด้วยตัวเลือก --index

ค่าใช้จ่ายในการเริ่มต้นของ ugrep --index เพื่อสร้างตารางแฮชการจัดทำดัชนีขึ้นอยู่กับรูปแบบ regex หากรูปแบบ regex "อนุญาต" มาก เช่น จับคู่รูปแบบที่เป็นไปได้จำนวนมาก เวลาเริ่มต้นของ ugrep --index จะเพิ่มขึ้นอย่างมากในการคำนวณตารางแฮช กรณีนี้อาจเกิดขึ้นเมื่อใช้คลาสอักขระ Unicode ขนาดใหญ่และไวด์การ์ด โดยเฉพาะอย่างยิ่งเมื่อใช้การซ้ำ * และ + แบบไม่จำกัด หากต้องการทราบว่าเวลาเริ่มต้นเพิ่มขึ้นอย่างไร ให้ใช้ตัวเลือก ugrep --index -r PATTERN /dev/null --stats=vm เพื่อค้นหา /dev/null ด้วย PATTERN ของคุณ

ถาม: เหตุใดไฟล์ดัชนีจึงไม่ถูกบีบอัด

ไฟล์ดัชนีควรมีเนื้อหาข้อมูลหนาแน่นมากและนั่นคือกรณีของอัลกอริธึมการจัดทำดัชนีใหม่สำหรับ ugrep ที่ฉันออกแบบและนำไปใช้ ยิ่งไฟล์ดัชนีมีความหนาแน่นมากเท่าใด ข้อมูลไฟล์ต้นฉบับก็จะยิ่งมีขนาดกะทัดรัดมากขึ้นเท่านั้น ทำให้การบีบอัดไฟล์ดัชนียากหรือเป็นไปไม่ได้ นี่เป็นตัวบ่งชี้ที่ดีว่าไฟล์ดัชนีจะมีประสิทธิภาพในทางปฏิบัติเพียงใด