ugrep indexer
v1.0.0
ugrep-indexer 유틸리티는 파일을 재귀적으로 색인화하여 재귀적 수집 속도를 높입니다.
또한 명령줄 옵션을 사용하여 지정하면 아카이브 및 압축 파일의 내용이 색인화됩니다. 이렇게 하면 해당 내용이 지정된 패턴과 일치하지 않을 때 검색이 제거됩니다.
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
인덱싱이 없는 콜드 파일 시스템에서 일반 검색은 drive 마운트 해제하고 다시 마운트하여 FS 캐시를 지워 인덱싱 효과를 기록한 후 1.02초가 걸립니다.
$ 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
이와 대조적으로 인덱싱을 사용하면 ugrep을 사용하여 콜드 파일 시스템을 검색하는 데 0.0487초만 소요됩니다. 이는 drive 마운트 해제하고 인덱싱 효과를 기록하기 위해 FS 캐시를 지우기 위해 다시 마운트한 후 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초(21배 속도 향상)에서 0.0983초(10배 속도 향상)의 검색 시간 범위를 생성한 4회 검색 실행 중 가장 좋은 시간인 0.0487초로 경과 시간에는 항상 약간의 차이가 있습니다.
여러 요인, 인덱싱된 파일의 크기, 파일 시스템의 읽기 속도 및 대부분의 파일이 콜드 상태라는 가정하에 따라 일반적으로 이 작은 데모에 비해 속도 증가가 훨씬 더 높을 수 있습니다.
내가 디자인한 인덱싱 알고리즘은 단조로운 것으로 입증되었습니다 . 정확도가 높을수록 거짓 긍정 비율을 줄여 검색 성능이 향상되지만 인덱스 저장 오버헤드도 증가합니다. 마찬가지로 정확도가 낮을수록 검색 성능이 저하되지만 인덱스 저장 오버헤드도 줄어듭니다. 따라서 나는 내 인덱서를 단조로운 인덱서 라고 명명했습니다.
파일 저장 공간이 부족한 경우 인덱싱 정확도를 더 낮게 지정하여 인덱스 저장 오버헤드를 줄일 수 있습니다.
위의 예제를 레벨 0(옵션 -0 )으로 인덱싱하면 인덱싱 저장소 오버헤드가 파일당 4256바이트에서 파일당 490바이트로 8.6배 줄어듭니다.
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' 에 대한 검색 속도와 거짓 긍정 비율이 표시됩니다.
| acc. | 인덱스 스토리지(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개 파일 중에서 더 높은 비율의 오탐률을 관찰할 수 있습니다. 결과적으로 검색 시간이 약간 길어집니다.
| acc. | 거짓 긍정 | 검색 시간(초) |
|---|---|---|
-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에 캐시되어 있는 경우 최근에 파일을 검색했거나 읽었기 때문에 인덱싱이 반드시 검색 속도를 높이지는 않는다는 것을 의미합니다. 이 경우 색인화되지 않은 검색이 더 빠를 수 있습니다. 또한 인덱스 기반 검색은 시작 시간이 더 깁니다. 해시 테이블로 변환해야 하는 유니코드 문자 클래스와 와일드카드를 사용하면 이 시작 시간이 늘어납니다.
요약하자면, 인덱스 기반 검색은 많은 콜드 파일을 검색할 때와 정규식 패턴이 너무 많이 일치하지 않을 때 가장 효과적입니다. 즉, 무제한 반복 * 및 + 의 사용을 제한하고 다음과 같은 경우 유니코드 문자 클래스의 사용을 제한하려고 합니다. 가능한. 이렇게 하면 ugrep 시작 시간이 줄어들고 잘못된 긍정 패턴 일치 비율이 제한됩니다(아래 Q&A 참조).
진행 상황을 표시하는 모든 비바이너리 파일을 재귀적으로 증분적으로 색인화합니다.
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-그램 블룸 필터에는 해시 충돌을 방지하기 위해 해시 테이블에 자체 "비트 계층"이 있습니다. 예를 들어 2그램은 3그램과 어떤 비트도 공유하지 않습니다. 이렇게 하면 실제로 패턴의 일부가 아닌 문자가 잘못 일치하여 잘못된 긍정이 발생하지 않습니다. 그러나 1그램(단일 문자) 비트 공간은 작습니다(최대 256비트). 따라서 해시 테이블이 더 클 때 일부 비트를 낭비합니다. 낭비를 줄이기 위한 가능한 접근 방식은 1그램과 2그램을 결합하여 동일한 비트 공간을 공유하는 것입니다. 1그램이 두 번째 문자가 (NUL)으로 설정된 2그램과 같다고 생각하면 쉽게 수행할 수 있습니다. 다른 해시 방법을 기반으로 한 두 번째 2그램 해시를 사용하면 거짓양성률을 낮출 수 있습니다. 또는 "비트 계층"을 8에서 9로 확장하여 9그램을 저장할 수 있습니다. 그러면 추가 비용 없이 더 긴 패턴(9개 이상)에 대한 인덱싱 정확도가 높아집니다. 반면, 이러한 변경으로 인해 패턴의 일부가 아닌 문자가 잘못 일치하는 경우 더 많은 잘못된 긍정이 발생할 수 있습니다. 우리는 완벽한 1그램 정확도의 이점을 잃게 됩니다.
인덱싱은 인덱싱된 각 디렉터리에 숨겨진 인덱스 파일 ._UG#_Store 추가합니다. 인덱스 파일을 생성하기 위해 ugrep-indexer가 인덱스된 파일을 검사합니다(변경되지 않음!).
인덱스 파일의 크기는 지정된 정확도에 따라 달라지며, -0 이 가장 낮고(작은 인덱스 파일) -9 가장 높습니다(큰 인덱스 파일). 기본 정확도는 -4 입니다. 정확도가 인덱싱 크기와 검색 속도에 미치는 영향에 대한 자세한 내용은 다음 Q를 참조하세요.
인덱싱은 절대 디렉토리에 대한 심볼릭 링크를 따르지 않습니다 . 왜냐하면 심볼릭 링크된 디렉토리는 파일 시스템이나 인덱스 파일을 추가하고 싶지 않은 다른 파일 시스템 어디에나 위치할 수 있기 때문입니다. ugrep-indexer 옵션 -S 를 사용하여 파일에 대한 심볼릭 링크를 계속 인덱싱할 수 있습니다.
옵션 -v ( --verbose )는 인덱싱 진행 상황과 인덱싱된 각 파일의 "노이즈"를 표시합니다. 노이즈는 입력의 엔트로피 또는 무작위성을 측정한 것입니다. 노이즈 수준이 높을수록 파일 내용을 표시하는 데 있어 인덱싱의 정확성이 떨어졌음을 의미합니다. 예를 들어, 무작위 데이터가 포함된 대용량 파일은 정확하게 인덱싱하기 어렵고 노이즈 수준이 높습니다.
인덱싱의 복잡성은 인덱싱할 특정 파일의 크기에 비례합니다. 실제로 이는 빠른 프로세스가 아니며 검색만큼 빠르지도 않으며 대규모 디렉터리 트리에 대한 전체 인덱싱 과정을 완료하는 데 시간이 걸릴 수 있습니다. 인덱싱이 완료되면 ugrep-indexer가 인덱싱 결과를 표시합니다. 추가된 인덱스의 전체 크기와 평균 인덱싱 노이즈도 보고됩니다.
파일을 스캔하여 색인을 생성하면 64KB 색인 해시 테이블이 생성됩니다. 그런 다음 ugrep-indexer는 목표 정확도를 초과하지 않는 한 비트별 및 비트 압축을 사용하여 테이블을 절반으로 줄입니다. 이등분은 테이블이 인덱스 해싱 테이블 셀당 8비트에 해당하는 패턴 시작 부분의 오프셋에서 8개 창에 대한 해시를 인코딩한다는 사실에 의해 가능해집니다. 테이블의 두 부분을 결합하면 일부 비트가 1에서 0으로 바뀔 수 있으며 이로 인해 잘못된 긍정 일치가 발생할 수 있습니다. 이는 인덱서의 단조성을 증명합니다. 0비트 해시 값은 가능한 일치를 나타냅니다.
ugrep-indexer는 ugrep-indexer 옵션 -I ( --ignore-binary )를 사용하여 무시하고 인덱싱할 수 없는 "바이너리 파일"을 감지합니다. 이는 일반적인 시나리오인 바이너리 파일을 무시하기 위해 ugrep 옵션 -I ( --ignore-binary )를 사용하여 검색할 때 유용합니다.
ugrep-indexer는 -X 옵션( --ignore-files )으로 지정된 경우 .gitignore 파일 제외를 따릅니다. 무시된 파일과 디렉터리는 파일 시스템 공간을 절약하기 위해 색인화되지 않습니다. 이는 ugrep 옵션 --ignore-files 사용하여 파일을 검색할 때 잘 작동합니다.
예를 들어 CTRL-C를 사용하여 인덱싱을 중단할 수 있습니다. 이렇게 하면 ugrep을 사용한 검색 기능이 손실되지 않지만 디렉터리 구조는 부분적으로만 인덱싱됩니다.
옵션 -c 오래된 참조와 색인화되지 않은 파일 및 디렉토리에 대한 색인을 확인합니다.
ugrep-indexer 옵션 -d 를 사용하면 인덱스가 삭제됩니다.
ugrep-indexer는 ugrep --index 검색 결과를 수천 개의 무작위 검색 패턴이 있는 수천 개의 파일에 대한 "느린" 비인덱싱된 ugrep 검색 결과와 비교하여 광범위하게 테스트되었습니다.
색인 기반 검색은 -v ( --invert-match ), --filter , -P ( --perl-regexp ) 및 -Z ( --fuzzy ) 옵션을 제외한 모든 ugrep 옵션에서 작동합니다. --index 포함된 옵션 -c ( --count )는 --min-count=1 자동으로 설정하여 일치 항목이 없는 모든 파일을 건너뜁니다.
인덱싱 후 파일이나 디렉터리가 업데이트, 추가 또는 삭제된 경우 ugrep --index 이러한 파일과 디렉터리가 재귀 검색 경로에 있을 때 항상 검색합니다. ugrep-indexer를 다시 실행하여 모든 인덱스를 증분적으로 업데이트할 수 있습니다.
정규식 패턴은 --index 옵션을 사용하여 ugrep에 의해 지정된 정규식 패턴의 최대 처음 16바이트에 대한 해시 테이블 형식으로 내부적으로 변환됩니다. 정규식 패턴이 복잡한 경우 구성 시간을 줄이기 위해 더 짧을 수도 있습니다. 따라서 검색할 정규식 패턴의 처음 8~16자는 가장 중요하며 검색 속도를 늦출 수 있는 소위 거짓 긍정 일치를 제한하기 위해 너무 많이 일치해서는 안 됩니다.
ugrep에서는 정규식 패턴이 DFA로 변환됩니다. 인덱싱 해시 유한 자동 장치(HFA)는 DFA 위에 구성되어 해시 테이블을 레이블이 지정된 가장자리가 있는 상태 전환으로 간결하게 표현합니다. 이 HFA는 최대 8개의 레이어로 구성되며, 각 레이어는 패턴의 다음 8바이트 창을 나타내기 위해 1바이트씩 이동됩니다. 각 HFA 계층은 패턴의 해당 부분에 대한 인덱스 해시를 인코딩합니다. 선택된 인덱스 해시 함수는 "추가적"입니다. 즉, 이전 해시로 해시될 때 다음 바이트가 추가된다는 의미입니다. 이는 HFA 구축 오버헤드를 크게 줄여주기 때문에 매우 중요합니다. 이제 각각 개별 해시 값을 갖는 단일 에지 세트 대신 16비트 해시 값 범위를 갖는 다중 에지로 상태로 레이블이 지정된 HFA 전환을 인코딩할 수 있습니다. 이를 위해 std::set<T> 에서 파생된 개방형 범위 라이브러리 reflex::ORanges<T> 사용합니다.
단일 문자열의 인덱스 기반 검색을 보여주기 위해 소수 61 인덱스 해시 함수를 사용하는 매우 간단한 단일 문자열 maybe_match() 함수가 아래에 제공됩니다.
// 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 Wikipedia 파일에서 무작위로 추출된 단어를 반복 검색하여 테스트되었습니다. 단어가 1개, 2개 또는 3개의 임의 문자로 변경되었습니다. 이 돌연변이는 Wikipedia 파일의 실제 유효한 단어와 일치하지 않는지 확인하기 위해 검사됩니다. 그런 다음 변형된 단어가 파일과 일치할 때마다 거짓양성률이 기록되었습니다. 최소한의 거짓양성률을 갖는 해시 함수는 전반적으로 좋은 후보가 되어야 합니다.
8개의 창(또는 패턴 길이에 따라 더 짧음)을 사용하면 표준 Bloom 필터에 비해 잘못된 긍정 비율이 더 낮습니다. 보다 구체적으로, Bloom 필터에서는 N 대신 N² 해시 함수가 사용됩니다. 더 짧은 패턴의 경우 N 은 잘못된 긍정을 제한하기에는 너무 작은 경우가 많습니다. 따라서 N²가 더 효과적입니다. 또한 패턴의 처음 8바이트에 문자가 있는 일치 항목에서 패턴이 실제로 색인된 파일의 어느 위치에도 발생하지 않는 경우를 거부합니다. 반면 표준 Bloom 필터에는 거짓 긍정 일치 항목이 있을 수 있습니다. 또한 해시 테이블을 인덱싱하는 데 사용되는 비트 주소 지정을 통해 효율적인 테이블 압축이 가능합니다.
인덱싱은 손실 압축의 한 형태입니다. 인덱싱 정확도가 높을수록 일치하지 않는 더 많은 파일을 건너뛰어 ugrep 검색 성능이 빨라집니다. 정확도가 높을수록 노이즈가 줄어듭니다(손실이 적음). 높은 수준의 노이즈로 인해 ugrep이 일치하지 않는 색인 파일을 검색하는 경우가 있습니다. 우리는 이것을 "가양성 일치"라고 부릅니다. 정확도가 높을수록 더 큰 인덱스 파일이 필요합니다. 일반적으로 파일당 평균 4K 이하의 인덱싱 스토리지를 예상합니다. 파일 이름과 4바이트 인덱스 헤더를 제외하고 최소 파일당 인덱스 저장소는 128바이트입니다. 노이즈가 매우 큰 파일의 경우 파일당 최대 저장 공간은 64K 바이트입니다.
ugrep --index --stats 사용하여 색인화된 파일을 검색할 때 --stats 옵션은 색인 기반 검색이 완료된 후 검색 통계를 표시합니다. 인덱싱 노이즈(예: 거짓 긍정)로 인해 많은 파일이 검색에서 건너뛰지 않는 경우 정확도가 높을수록 인덱싱 효율성이 높아져 검색 속도가 빨라질 수 있습니다.
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 의 시작 시간이 크게 늘어납니다. 이는 대규모 유니코드 문자 클래스와 와일드카드를 사용할 때, 특히 무제한 * 및 + 반복을 사용할 때 발생할 수 있습니다. 시작 시간이 어떻게 증가하는지 알아보려면 ugrep --index -r PATTERN /dev/null --stats=vm 옵션을 사용하여 PATTERN으로 /dev/null을 검색하세요.
인덱스 파일은 정보 콘텐츠가 매우 밀집되어 있어야 하며, 제가 설계하고 구현한 ugrep용 새 인덱스 알고리즘이 바로 그런 경우입니다. 인덱스 파일의 밀도가 높을수록 원본 파일 데이터를 더 정확하게 표현합니다. 이로 인해 인덱스 파일을 압축하는 것이 어렵거나 불가능해집니다. 이는 인덱스 파일이 실제로 얼마나 효과적인지를 보여주는 좋은 지표이기도 합니다.
