☰

대소문자 구분 검색에 비해 대소문자 구분 검색의 비용은 얼마나 됩니까?

tag-icon • tag-icon grep
대소문자 구분 검색에 비해 대소문자 구분 검색의 비용은 얼마나 됩니까?

나는 grep -i 런타임이 크게 다르지 않기 때문에 일반 grep (grep의 문자 수에 비해)보다 기하 급수적으로 (시간 측면에서) 더 비싸다고 생각하지 않습니다.

하지만 이론상으로는 이렇게 되어야 합니다. 예를 들어

egrep -i abc *

동등하다

egrep "abc|abC|aBc|aBC|Abc|AbC|ABc|ABC" *

grep과 같은 유틸리티는 대소문자를 구분하지 않는 쿼리에서 기하급수적인 시간을 어떻게 방지할 수 있습니까? 그러한 유틸리티가 사용할 수 있는 Unix에서 기본적으로 지원되는 대소문자 구분 비교 연산자가 있습니까?

답변1

abCi와 i의 매칭은 소문자로 변환 aBc하면(1회) 쉽게 할 수 있고, 같은 입력 도 각각 소문자로 변환하면 된다. 그러면 정상적으로 일치합니다.abCaBc

하지만 어쩌면 일부를 무시하는 것만으로도 가능할 수도 있습니다. 'A'는 65, 'a'는 97입니다. 그 차이는 32로 2의 거듭제곱이므로 쉽게 가릴 수 있습니다. 'ä'(228)과 'ä'(196)도 32의 차이가 있지만 확장 ASCII의 모든 문자에 적용되는지는 확실하지 않습니다.

답변2

grep대부분의 정규식 엔진과 마찬가지로 지정한 패턴을 다음으로 변환합니다.결정론적 유한 상태 오토마타(DFA).

대소 문자를 구분하지 않음을 표현하는 일반적인 방법은 각 문자에 문자 클래스를 사용하는 것이므로 예제는 다음과 같습니다 [aA][bB][cC]. 단일 문자 클래스 일치는 일반적으로 1s 비트가 해당 위치에 포함되는 비트 세트 조회로 구현됩니다. 세트는 Regex->DFA 컴파일 타임에 빌드됩니다.aA

즉 [aA], DFA를 일치시키려면 입력 문자의 값을 가져와 비트 세트에 대한 인덱스로 사용하면 됩니다.산소(1) 액션 - 콤보 시간 폭발에 해당하는 것을 볼 수 없습니다.

"abc|abC|aBc|aBC|Abc|AbC|ABc|ABC"

추천합니다. 정규식에서 DFA를 구축하는 것은 "미리 시간을 투자할 의향이 있다면(DFA 구축) 나중에 주기를 절약할 수 있습니다(DFA 식별)" 애플리케이션 중 하나입니다.

관련 정보