asp.NET 脏字过滤算法 修改版

旧的算法是简单对每一个脏字调用一遍 string.replace，当然是用了StringBuilder。http://www.jb51.net/article/20575.htm。在我这里测试的时候，RegEx要快一倍左右。但是还是不太满意，应为我们网站上脏字过滤用的相当多，经过一番思考后，自己做了一个算法。在自己的机器上测试了一下，使用原文中的脏字库，0x19c的字符串长度，1000次循环，文本查找耗时1933.47ms，RegEx用了1216.719ms，而我的算法只用了34.125ms.

算法的关键，还是使用空间来换时间，使用了2个全局的BitArray, 长度均为Char.MaxValue。其中一个BitArray用来判断是否有某个char开头的脏字，另一个BitArray用来判断所有脏字中是否包含某个char。经过这两个BitArray，可以做出快速判断，之后就使用Hash Code来判断完整的脏字，通过预先获取的最大脏字长度优化遍历过程。

需要的变量如下：


代码如下:

private Dictionary<string, object> hash = new Dictionary<string, object>();
private BitArray firstCharCheck = new BitArray(char.MaxValue);
private BitArray allCharCheck = new BitArray(char.MaxValue);
private int maxLength = 0;

其中hash只使用到了key，value都置为null。也可以使用.NET 3.5中的HashSet，或者使用Dictionary<string, int>，记录脏字的出现次数。

初始化这些数据的方法如下：


代码如下:

foreach (string word in badwords)
{
if (!hash.ContainsKey(word))
{
hash.Add(word, null);
maxlength = Math.Max(maxlength, word.Length);
firstCharCheck[word[0]] = true;

foreach (char c in word)
{
allCharCheck[c] = true;
}
}
}

判断脏字是否出现在一个字符串中的代码如下：

代码如下:

int index = 0;
int offset = 0;
while (index < text.Length)
{
if (!firstCharCheck[text[index]])
{
while (index < text.Length - 1 && !firstCharCheck[text[++index]]) ;
}

for (int j = 1; j <= Math.Min(maxlength, text.Length - index); j++)
{
if (!allCharCheck[text[index + j - 1]])
{
break;
}

string sub = text.Substring(index, j);

if (hash.ContainsKey(sub))
{
return true;
}
}

index++;
}

return false;

替换的代码就不贴了，跟判断包含类似，只不过不能发现一个脏字后就退出循环。如果出现脏字的可能不是很高，就没有必要创建一个临时的StringBuilder。

进一步，可以通过借鉴.NET源码中string.GetHashCode()的实现，避免一次Substring的调用，提高性能。也可以设计递进的HashCode实现，比如"helloworld"可以用"helloworl"的hash进一步计算，优化效率。

另外，也可以抛弃Hash，改用排序过的string[]，用BinarySearch来判断sub是否为脏字。BinarySearch的结果是可以递进的，即可以用查找"helloworl"的结果来加速判断"helloworld"。 （已测试，700个脏字，BinarySearch的效率有时会低很多。）
最后发一点牢骚，当初最早发的时候（http://www.jb51.net/article/20576.htm），仅仅是为了说明下自己的算法，具体的代码甚至还有一点错误。两个事情让我觉得心里不很爽，一个是被乱七八糟的无数网站转载而不说明出处，导致我后来的改进和错误修正达不到效果，二是一些人都愿意看到最终的代码，而不是理解我想要表达的最核心的设计，然后自己去考虑实现。

赞 (0)

相关推荐

  • asp.net 脏字典过滤问题 用正则表达式来过滤脏数据

    方法一:使用正则表达式 复制代码 代码如下: //脏字典数据存放文件路径 private static string FILE_NAME="zang.txt"; //脏数据字典表,如:脏数据一|脏数据二|脏数据三 public static string dirtyStr=""; public ValidDirty() { if (HttpRuntime.Cache["Regex"]==null) { dirtyStr=ReadDic(); //

  • ASP.NET过滤HTML标签只保留换行与空格的方法

    本文实例讲述了ASP.NET过滤HTML标签只保留换行与空格的方法.分享给大家供大家参考.具体分析如下: 自己从网上找了一个过滤HTML标签的方法,我也不知道谁的才是原创的,反正很多都一样.我把那方法复制下来,代码如下: 复制代码 代码如下: ///   <summary> ///   去除HTML标记 ///   </summary> ///   <param name="NoHTML">包括HTML的源码   </param> ///

  • ASP.NET环境下为网站增加IP过滤功能第1/2页

    ASP.NET环境下为网站增加IP过滤功能第1/2页

    1. 需求分析 通过深入的交流和沟通,确认了该发电厂在企业网站用户访问控制方面的改进要求,大致情况如下: a) 网站基于Asp.Net2.0实现,不允许修改源程序 b) 厂内用户可直接访问整个站点的所有页面,员工不需要身份验证 c) 厂外用户只能访问指定的页面 显而易见,他们就是针对企业网站增加一项IP过滤功能,在厂外用户访问某些敏感页面时将其拒之门外.首先我们需要设置一个IP列表和一个Url列表,前者包含所有厂内IP,后者包含厂外用户可访问的全部Url,并且这两个列表都是可维护的:另外一个核心

  • asp.NET 脏字过滤算法

    原文见http://www.jb51.net/article/20575.htm但在我这里测试的时候,RegEx要快一倍左右.但是还是不太满意,因为我们网站上脏字过滤用的相当多,对效率已经有了一些影响,经过一番思考后,自己做了一个算法.在自己的机器上测试了一下,使用原文中的脏字库,0x19c的字符串长度,1000次循环,文本查找耗时1933.47ms,RegEx用了1216.719ms,而我的算法只用了244.125ms. 更新:新增一个BitArray,用于判断某char是否在所有脏字中出现过

  • ASP.NET中的URL过滤实现代码

    下面是类的定义. 复制代码 代码如下: using System; using System.Web; using System.Web.SessionState; namespace QTJZ {     public class Filters : IHttpModule, IRequiresSessionState     {         public void Dispose() { } public void Init(HttpApplication application)   

  • 高效.NET脏字过滤算法与应用实例

    本文实例讲述了高效.NET脏字过滤算法.分享给大家供大家参考,具体如下: BadWordsFilter.cs类 using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Collections; using System.Data; namespace WNF { public class BadWordsFilter { private HashSet<st

  • ASP.NET过滤类SqlFilter，防止SQL注入 原创

    什么是SQL注入? 我理解的sql注入就是一些人可以通过恶意的参数输入,让后台执行这段SQL,然后达到获取数据或者破坏数据库的目的! 举个简单的查询例子,后台sql是拼接的:select * from Test where name='+参数传递+':前台页面要求输入name,那么黑客可以输入: ';DROP TABLE Test;--   不要小瞧这一段SQL代码: select * from Test where name=' ';DROP TABLE Test;--':在SQL中是正确的,

  • asp.net 过滤图片标签的正则

    复制代码 代码如下: public static string replaceImgUrl(string html) { if (html == null) return ""; System.Text.RegularExpressions.Regex regex = new System.Text.RegularExpressions.Regex(@"\<img[^\>]+\>", System.Text.RegularExpressions.R

  • ASP.NET过滤HTML字符串方法总结

    本文实例讲述了ASP.NET过滤HTML字符串的方法,供大家参考使用,具体代码如下: /// <summary>去除HTML标记 /// /// </summary> /// <param name="Htmlstring">包括HTML的源码</param> /// <returns>已经去除后的文字</returns> public static string GetNoHTMLString(string Ht

  • ASP.NET过滤器的应用方法介绍

    在J2EE Web开发中有过滤器filter,该filter可以对指定的URL访问进行拦截,并执行过滤器的方法,根据实际应用情况,在过滤器中修改请求的代码.判断会话信息,也可以做权限控制,总之这个过滤器是非常有意义的,也可以说是责任链设计模式在J2EE中的一个应用. 那么在ASP.NET中是否也可以定义这样的过滤器结构,并在过滤器中进行相应的逻辑操作呢?答案是肯定,本文将告诉你如果编写一个过滤器,又如何配置到IIS的Web应用之中. 过程一:如何编写过滤器 编写过滤器,其实就是编写一个过滤器的类

  • Asp.net之数据过滤浅析

    在Asp.net开如中,引发安全问题最多的大多来自于以下三个方面: 1.上传 2.跨站 3.注入 上传的安全问题不在本文讨论范围内,这里只讨论跨站与注入的问题,而这两者都是基本可以通过过滤来处理的!把注入放在最后面是因为,SQL注入玩了这么多年,大家应当有了一定的防范,只要稍有点注意,能在asp.net上面玩下的注入还是相当少的!注意这以下几点. 1.所有的参数.如果是int类型的,请转换成int再处理! 别拿装箱与拆箱来说事!估计现在大家也不会把sql语句直接在web里面拼接了,起码也要用上几

随机推荐