Quão caro é a pesquisa insensível a maiúsculas e minúsculas em comparação com a pesquisa sensível a maiúsculas e minúsculas?

Question

Eu não acho que grep -i seja exponencialmente (com relação ao número de caracteres a serem grep) mais caro (tempo sábio) do que um grep normal porque os tempos de execução não são muito diferentes.

Mas teoricamente deveria ser. Por exemplo

egrep -i abc *

é equivalente a

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

Como utilitários como o grep evitam o tempo exponencial em consultas insensíveis? Existe um operador de comparação insensível a maiúsculas e minúsculas que o Unix suporta inerentemente que tais utilitários podem usar?

    

Answer 1

Uma correspondência i entre abC e aBc pode ser feita facilmente, se abC for transformado em minúsculas (uma vez) e todas as entradas como aBc também forem convertidas em minúsculas. Então correspondência normal.

Mas talvez seja feito apenas ignorando alguns bits. 'A' é 65, e 'a' é 97. A diferença é 32, uma potência de 2, então pode ser facilmente mascarada. Mesmo 'ä' (228) e 'Ä' (196) têm uma diferença de 32, mas não tenho certeza se é válido para todos os caracteres em ASCII estendido.

    

Answer 2

grep como a maioria dos mecanismos de expressão regulares traduz o padrão que você especifica para um autômato de estado finito determinístico (DFA).

Uma maneira comum de expressar insensibilidade a maiúsculas e minúsculas é usando classes de caractere para cada alfabético, portanto, seu exemplo seria mais parecido com [aA][bB][cC] . As correspondências de classe de caractere individuais são geralmente implementadas como pesquisas de conjunto de bits em que um conjunto de bits contendo 1 s nas posições correspondentes a a e A é criado na expressão regular - > Tempo de compilação do DFA.

Isso significa que para corresponder a [aA] , o DFA precisa apenas pegar o valor do caractere de entrada, usá-lo como um índice para o conjunto de bits - que é uma operação O (1) - então você não vê a explosão combinatória de tempo que o seu equivalente

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

sugeriria. A construção do DFA a partir de expressões regulares é uma aplicação de "se você estiver disposto a gastar um tempo adiantado (construção do DFA), poderá realmente salvar os ciclos mais tarde (reconhecimento do DFA).