上海百维科技,上海网站建设 上海软件开发公司热线电话:021-57700304  
  首 页 产品与服务 软件定制 成功案例 思源优势 技术学院 关于我们 联系我们
 
 
思源软件学院 >>> 根目录>>.NET技术>>C# >>>撒列实现关键字过滤,速度可快了
科学就是不断地认识,不仅是发现,而且是发明。——鲁巴金(上海网站建设)

撒列实现关键字过滤,速度可快了


Admin
2012年1月20日

一向对搜刮、过滤很好奇,感觉他们很有技巧含量,只有很是NB的人才干做。很想知道他们的道理,实现如许的功能,设计是不是必须得很是NB很是独特,代码是不是要写得很是好,机能很是高。总之这一切都不是我如许级此外人能做的。直到我看了《编程珠玑(第二版)》中的这么一段文字:


“假定我们可以在履行搜刮之前对文本内容进行预处理惩罚,那么我们可以建树一个撒列表(或者搜刮树),为文档中的每个不合的单词建树索引,并为每个单词的每次呈现存储一个链表,如许的逆向索引使得法度可以很快的找到给定的单词,为了查找短语,我们可以对此中包含的每个单词的链表进行交叉,但实现起来斗劲错杂,速度可能会很慢。(不过一些网页搜刮引擎用的就是如许的办法)”


思路就这么简单,我靠!连有的搜刮引擎也用这种思路。这种撒列的体式格式处理惩罚关键字过滤速度的确是蛮快,10000个字组织成一个撒列表也就几毫秒,只要你预分派的内存较好,根蒂根基上没什么操纵,就是向内存中填数据。在撒列表中断定一个键是否存在的时候错杂度为O(1),其实还可以本身重写Dictionary<TKey, TValue>,关键字过滤的效力可能会更好点。


实现的思路斗劲简单:


1:处理惩罚关键字,生成一个关键字字典表


2:处理惩罚要过滤的文本,同样生成一个字典表


3:将文本,两个字典表三者进行比对


 


如今来测试下面一段文字(我上篇博客中的一段文字):


"看云风博客关于解决12306并发题目的启发:我如今做骏卡接口,可能呈现并发题目,就是一个订单可能向我们的接口发送多个恳求,而我如今做的办法是去数据库中对应的表验证,看订单是否存在,若是存在就提示一下,若是不存在按流程走,然则这个样每来一个订单我都须要去数据库查,若是我在内存中保护一个订单凑集,如许就能很快解决断定订单是否存在的题目,惯性思维太严重了,什么都去数据库查,如许的机能是最差的,其实很多题目在内存中就可以搞定的,比来还有一个希罕感触感染,不要做井底之蛙,多看牛人的器材收成真的比本身居心写代码进步快很多,其实很多时辰我写的法度机能差,效力低都是因为办法的原因,没有找到好的办法,没有灵光一闪的感触感染,用了最烂的办法解决题目"


 


测试代码:



class Program
{
static void Main(string[] args)
{
string keys = "云风博客|并发题目|最烂的办法|内存|凑集|数据库|机能";

usingnew OperationTimer("keyWords:"))
{
WordSearch ws = new WordSearch(keys);
string str = "看云风博客关于解决12306并发题目的启发:我如今做骏卡接口,可能呈现并发题目,就是一个订单可能向我们的接口发送多个恳求,而我如今做的办法是去数据库中对应的表验证,看订单是否存在,若是存在就提示一下,若是不存在按流程走,然则这个样每来一个订单我都须要去数据库查,若是我在内存中保护一个订单凑集,如许就能很快解决断定订单是否存在的题目,惯性思维太严重了,什么都去数据库查,如许的机能是最差的,其实很多题目在内存中就可以搞定的,比来还有一个希罕感触感染,不要做井底之蛙,多看牛人的器材收成真的比本身居心写代码进步快很多,其实很多时辰我写的法度机能差,效力低都是因为办法的原因,没有找到好的办法,没有灵光一闪的感触感染,用了最烂的办法解决题目";
ConsoleColor color = Console.ForegroundColor;
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("原文:");
Console.ForegroundColor = color;
Console.WriteLine(str);
Console.WriteLine();
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("过滤后:");
Console.ForegroundColor = color;
Console.WriteLine(ws.Filter(str));
}
Console.Read();
}

}


输出成果截图:



 


别的奉上一个简单实用的代码运行时候测试类,测试某段代码的运行时候可是很便利的哦



using System;
using System.Diagnostics;

namespace WordFilter
{
/// <summary>
/// 测试代码运行时候帮组类
/// </summary>
public class OperationTimer : IDisposable
{
private string Text;
private Int32 collectCount;
private Stopwatch stopWatch;

public OperationTimer(string txt)
{
PerpareForOperation();
this.Text = txt;
collectCount = GC.CollectionCount(0);
stopWatch = new Stopwatch();
stopWatch.Start();
}

public void Dispose()
{
stopWatch.Stop();
Console.WriteLine("{0} Milliseconds (GCs={1}) {2}", stopWatch.ElapsedMilliseconds, GC.CollectionCount(0) - collectCount, Text);
}

private static void PerpareForOperation()
{
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
}
}
}


 


实现撒列的项目组核心代码:



      public Dictionary<char, IList<char>> HandleKeyWords(IEnumerable<string> text, int size)
{
Dictionary<char, IList<char>> dicList = new Dictionary<char, IList<char>>(size);//预分派很是关键
int len, i;
foreachstring s in text)
{
if (s == string.Empty)
{
continue;
}
len = s.Length - 1;
for (i = 0; i < len; i++)
{
if (dicList.ContainsKey(s[i]))
{
if (dicList[s[i]] != null && !dicList[s[i]].Contains(s[i + 1]))
{
dicList[s[i]].Add(s[i + 1]);
}
}
else
{
dicList.Add(s[i], new List<char>(2) { s[i + 1] });
}
}
if (!dicList.ContainsKey(s[len]))
{
dicList.Add(s[len], null);
}
}

return dicList;
}


 


我也想贴出全部代码,然则还有一些BUG,功能还有待完美,完美一些了会贴出源码的,在截一张图给大师看看



 


关键字过滤,欲望能过滤掉大师不想听的,陈太汉祝大师新年康乐


 


作者:陈太汉


博客:http://www.cnblogs.com/hlxs/

 

上海软件开发公司业务部:黄浦区重庆北路211号602室 | 上海软件开发公司技术部:松江区天云路259号| 上海软件开发公司综合部:松江区南期昌路346弄50号401室
上海软件开发 Copyright © 2005-2010 All Rights Reserved 电话:021-57616508  传真:57661889
沪ICP备05011021号