最近接到一个需求：随便给一个网页，要求检测出里面的广告。
看到这需求，第一时间想到了firefox中的adblock plus，adblock plus是基于规则包来过滤广告，里面的广告描述规则也许能拿来用。于是折腾了一晚上，实现了一个简单的东西来满足需求，效果还不错
。
adblock plus工作原理：
adblock plus是先把过滤规则全部转换成正则表达式。再用这些正则表达式去过滤广告。
我思路如下：
1.实现一个adblock plus规则解析器，把adblock plus的广告过滤规则 转换成正则表达式。
2.得到一个要检测广告的页面后，解析出这个页面的所有链接。遍历所有链接，应用第一步得到的正则表达式规则判断链接是否广告。
第一步基于对正则表达式的理解简单的实现了下，如"."转换成"\\.","*"转换成".*"等，元素隐藏规则暂时不处理。adblock plus规则说明：http://code.google.com/p/adblock-chinalist/wiki/Writing_Adblock_Plus_filters 。
第二步，（adblock plus详细的匹配算法：http://adblockplus.org/blog/investigating-filter-matching-algorithms）经过第一步处理后，得到了几千条广告过滤正则表达式。 怎么解析出一个页面的所有链接就不说了，到这里时，收到有一大堆有待判断的链接，和一大堆用于判断的正则表达式规则，普通的思路是对于每一条链接，遍历所有规则判断是否匹配，代码如下：
for each filter in F
if (filter matches S)
return filter
end if
end for
return null
end function
但这样效率惨不忍睹。还好adblock plus中给出了一个不错的解决方案，对每一条过滤规则抽取出一个代表这条过滤规则的唯一key值，把这些放在哈希表中。于是对一条链接的判断不用遍历所有的规则，而是先在哈希表中查找出有可能匹配的规则再匹配。
对于查找出有可能 匹配的规则，adblock中用来一个奇妙的算法：Boyer-Moore algorithm。
adblock plus中实现如下:
for each c in C
H(c) := filter(c)
for i in (0 .. m/2)
substring := c.substring(i, m/2)
jump := m/2 - i
if substring not in J or J(substring) > jump
J(substring) := jump
end if
end for
end for
end function
function getMatchingFilter3(S, H, J, m)
endPtr := m
while endPtr <= n
substring := S.substring(endPtr - m/2, m/2)
if substring in J and J[substring] > 0
endPtr := endPtr + J[substring]
else if substring in J and J[substring] = 0
substring := S.substring(endPtr - m, m)
if (substring in H and H(substring) matches S)
return H(substring)
else
endPtr := endPtr + 1
end if
else
endPtr := endPtr + m/2 + 1
end if
end while
return null
end function
其中参数说明：
H是存放每一天规则生成的唯一key的哈希表，value是这条规则。
J存放的是跳过多少位字符的信息，Boyer-Moore算法要用到的。
C是是存放每一天规则生成的唯一key的集合。
M是每一条规则生成的key的长度，是8，没为什么。
S是要判断的链接。
我的实现就是,蹬蹬蹬蹬，就是翻译成C#版本：
{
foreach (string[] kv in C)
{
string ruleText = kv[1];
if (!H.ContainsKey(key))
{
H.Add(key, ruleText);
}
for (int i = 0; i <= 4; i++)
{
int jump = 4 - i;
string childKey = key.Substring(i, 4);
if (!J.ContainsKey(childKey) || J[childKey] > jump)
{
J[childKey] = jump;
}
}
}
}
private string GetMatchingFilter(string url,Dictionary<string, string> H, Dictionary<string, int> J)
{
int endPtr = 8;
while (endPtr <= url.Length)
{
string key = url.Substring(endPtr - 4, 4);
if (J.ContainsKey(key) && J[key] > 0)
{
endPtr += J[key];
}
else if (J.ContainsKey(key) && J[key] == 0)
{
key = url.Substring(endPtr - 8, 8);
if (H.ContainsKey(key) && Regex.IsMatch(url, H[key], options))
{
return H[key];
}
else
{
endPtr++;
}
}
else
{
endPtr = endPtr + 5;
}
}
return null;
}
完成，求交流。文中所用到的资料：