与区分大小写的搜索相比，不区分大小写的搜索成本有多高？

Question

我不认为 grep -i 比普通 grep 指数级（相对于要 grep 的字符数）成本更高（时间方面），因为运行时间并没有太大不同。

但理论上应该是这样。例如

egrep -i abc *

相当于

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

grep 等实用程序如何避免不区分大小写的查询中的指数时间？是否存在 Unix 本身支持的不区分大小写的比较运算符可供此类实用程序使用？

Answer 1

abC和之间的 i 匹配aBc可以很容易地完成，ifabC被转换为小写（一次），并且每个输入 likeaBc也被转换为小写。然后正常匹配。

但也许只是通过忽略一些位就可以完成。 'A' 是 65，'a' 是 97。差值是 32，是 2 的幂，因此很容易被屏蔽。即使 'ä' (228) 和 'Ä' (196) 也有 32 的差异，但我不确定它是否适用于扩展 ASCII 中的所有字符。

Answer 2

grep像大多数正则表达式引擎一样，将您指定的模式转换为确定性有限状态自动机（DFA）。

表达不区分大小写的常见方法是使用每个字母的字符类，因此您的示例更像是[aA][bB][cC].单个字符类匹配通常作为位集查找来实现，其中在与和1相对应的位置中包含 s 的位集是在正则表达式 -> DFA 编译时构建的。aA

这意味着要匹配[aA]DFA，只需获取输入字符的值，将其用作位集的索引 - 这是一个氧(1) 操作 - 这样你就不会看到相当于你的组合时间爆炸

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

会建议。从正则表达式构建 DFA 是“如果您愿意预先花一些时间（DFA 构建），那么以后确实可以节省周期（DFA 识别）”的应用。