Take the 2-minute tour ×
Unix & Linux Stack Exchange is a question and answer site for users of Linux, FreeBSD and other Un*x-like operating systems.. It's 100% free, no registration required.

I dont think grep -i is exponentially (wrt to the number of characters to be grepped) more costly (time wise) than a normal grep because the run times are not too different.

But theoretically it should be. For example

egrep -i abc *

is equivalent to

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

How do utilities like grep avoid the exponential time in case insensitive queries? Is there a case insensitive comparison operator that Unix inherently supports that such utilities can use?

share|improve this question
2  
Just because the first is equivalent to the second it doesn't mean that it "translates to" that. –  alex May 23 '11 at 15:37
    
@alex: I know! I just used it as an example. changed now. –  Lazer May 23 '11 at 16:01

2 Answers 2

An i-match between abC and aBc can easily be done, if "abC" is transformed to lowercase (once), and every input like "aBc" is translated to lowercase too. Than normal matching.

But maybe it is done, just by ignoring some bits. 'A' is 65, and 'a' is 97. The difference is 32, a power of 2, so it can easily be masked. Even 'ä' (228) and 'Ä' (196) have a difference of 32, but I'm not sure whether it holds for all characters in extended ASCII.

share|improve this answer
    
This is a fair guess but would only work for fixed string case folding and therefore doesn't fit with the rest of the mechanism most efficient for general regular expression matching. –  msw May 24 '11 at 15:10

grep like most regular expression engines translates the pattern that you specify into a deterministic finite-state automaton (DFA).

A common way of expressing case insensitivity is by using character classes for each alphabetic, therefore your example would be more like [aA][bB][cC]. Individual character class matches are often implemented as bit-set lookups where a bit set containing 1s in the positions corresponding to a and A is built at regular expression -> DFA compile time.

That means that to match [aA] the DFA need only take the value of the input character, use it as an index to the bit-set - which is an O(1) operation - so you don't see the combinatoric time explosion that your equivalent

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

would suggest. DFA construction from regular expressions is an application of "if you are willing to spend some time up front (DFA building) you can really save cycles later (DFA recognition).

share|improve this answer
    
Two things: Which grep? On linux grep, egrep, fgrep are often or always links t the same executable, but that hasn't traditionally been true. Egrep often used different algorithms than grep, fgrep always used to. See: Andrew Hume, "A tale of two greps", Software Practice and Experience, 18, #11, Nov. 1988. See Russ Cox Regular Expression Matching Can Be Simple And Fast (swtch.com/~rsc/regexp/regexp1.html) for timings of DFA and NFA based regexp matching. –  Bruce Ediger May 24 '11 at 15:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.