#求一字符串匹配高性能方法,最优者100分,顶者有分#

Question

对象obj(假设是List<string>或Dictionary,可自行选择)内有记录数10W(持续增长),
现需求为:
   当输入类似"欢迎来到csdn"之类的字符串时,搜索obj，如果包含有"欢迎来到csdn"任一词则返回true.
   此操作为多线程.
其中"欢迎来到csdn"已分词,如:   string[] str={"欢迎","来到","csdn"};
   //当然，可以直接迭代obj，不过这样子下来性能方面跟不上.不知各位有没有更好的搜索方法呢?
当然，输入的字符你可以自行处理，分不分词自行决定.PS:另求一个高性能的分词类,呵呵，谢谢~~~

Answer 1

可以考虑把list记录数进行拆分成N个，然后用N个线程进行查找，找到后切断所有线程。

Answer 2

从类型开始 吧  （我自己的意见！欢迎攻击）
那么大数据量，用引用类型比较恐怖（开辟-定义-存储）浪费资源。
实际数据--和指针地址那个快。栈的内存分配是自动释放（值）；而堆在.NET中会有GC来释放（引用）
————————————————————————————
sorry ! i will have lunch. after a while  go on !

Answer 3

Hashtable.  key值为对象Key,value为""即可。
然后Key中存放string[] str={"欢迎","来到","csdn"}。
重写Key的GetHashCode().只要string中匹配则返回同样
的hashCode。这样就能找到对象。Equal可以随便重写。
return base.Equal就行。
ps：  个人猜想，利用Hashtable寻址比较迅速。具体可行性
    还得验证，不过List的速度和Hashtable数量多了之后，速度
    不是一个级别上的...
    至于多线程，这种每个线程任务都是饱和的情况下分线程是没有
    用的。多线程适用于有个线程等待、有的处理的情况。

Answer 4

declare @t1 table (n varchar(50))
declare @t2 table (n varchar(50))
insert into @t1 values('abcdefghijkl')
insert into @t2 values('abc')
insert into @t2 values('def')
insert into @t2 values('ghi')
insert into @t2 values('rewrwe')
select * from @t2 a join @t1 b on b.n like '%' + a.n + '%'直接用数据库解决掉算了

Answer 5

谢谢先，hstb加载这批数据，固然它寻址较好，但是也提高不了多少，主要是量大。呵呵

Answer 6

假设:declare @t1 table (n varchar(50))
declare @t2 table (n varchar(50))
insert into @t1 values('我中国人发财')
insert into @t2 values('人无')
insert into @t2 values('黄中')
insert into @t2 values('发财迷')
insert into @t2 values('有朵花')
select * from @t2 a join @t1 b on b.n like '%' + a.n + '%'单个词/字如何解析.sql俺很是门外，见笑. --|

Answer 7

当然，你可以一个一个分解不过你也要去匹配obj这里的记录数。

Answer 8

1. 参考lucene的索引机制(跳跃表实现)
2. 用二叉树：
     发
      |
     工 - 明 - 现 - 财
      |
      资

Answer 9

LZ说的是语义搜索，大量数据快速语义搜索是一个很复杂的问题，与普通字符串搜索有很大的区别，不是到字符串中一个一个的找，网上有一些比较成熟的方法。
大至原理是先预处理被搜索的10W条数据，进行分词，用这些词建立一个哈希表，关键字是分出来的这些词，值是对应的行ID的集合。查找时先对条件字符串分词，然后用这些词作为KEY在哈希表中取对应的行集合，对这些行集合求交集或并集就行了。
网页搜索引擎都是这么做的，咱们一点搜索，0.几秒就能出结果。说起来容易，做起来难，LZ好运。

Answer 10

谢谢分词可以分出来并键值对应存入到哈希表了,现在就是对条件字符串与哈希表存的数据匹配。
你所说的>>"查找时先对条件字符串分词，然后用这些词作为KEY在哈希表中取对应的行集合，对这些行集合求交集或并集就行了"不甚了解。好比我遍历这个hstb          int i=0;
          bool cd=false;
          string[] str={"欢迎","来到","csdn"};
          foreach (DictionaryEntry ts in hstb){
              if(str.Equal(ts.Key.toString()){
                 cd=true;break;
              }
          }也要遍历好多次，而记录数也不少.没做这过方面，不知能否详细告知，不胜感激.

Answer 11

汗，少了个          int i=0;
          bool cd=false;
          string[] str={"欢迎","来到","csdn"};
          foreach (DictionaryEntry ts in hstb){
              if(str[i].Equal(ts.Key.toString()){
                 cd=true;break;
              }
              i++;
          }

Answer 12

用最简单的方式List<string> lists;foreach (string s in lists)
{
if (Regex.IsMatch(s, "(欢迎|来到|csdn)"))
break;
}测试10w条数据，每个字符串1k（总100M），用时4秒（个人认为没什么必要为这4秒钟去优化）

Answer 13

分线程只会更慢，用正则也只会更慢。在用string的条件下没有什么更好的搜索算法和匹配方法，老老实实地 for 和 indexof，要提高搜索效率只能是从数据结构上着手，比如像 hhhh63 所提到的方案。

Answer 14

http://download.csdn.net/source/1951661
一本全面彻底讲解字符串查找算法的书。书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有进一步的参考文献。

Answer 15

根据我的经验,用BM算法(或BM的一些变形算法比较快),特别是对针对楼主这种有一个固定的字符串,然后在成千上万个字符串中去查找这个字符串的情况.

Answer 16

using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;var list = new List<string>();
            for (int i = 0; i < 1000000;i++ )
            {
                list.Add(i.ToString());
            }
            try
            {
                list.Single(x =>
                {
                    if (Regex.IsMatch(x, "(欢迎|美女)"))
                    {
                        return true;
                    }
                    return false;
                });
            }
            catch 
            {
                throw new System.Exception("有多条记录");
            }

Answer 17

关键点：不是遍历哈希表，而是在哈希表中直接取值
object obj1 = hstb["欢迎"]; //行集
object obj2 = hstb["来到"]; //行集
在哈希表中，是根据索引值直接定位取值，而不是查找或遍历。
这两句的用时大约在纳秒级。我最近也在做行业搜索，大约十亿个网页，不好做啊，大家一起讨论吧。

Answer 18

多线程未必能够帮助加速算法。 小心使用，还是可以加速的。 一般经验，加载模式串占 0.5%，加载待处理串占据了31%，而查询处理则占据51%， 
另有10.5%左右需要处理模式串识别，输出结果，需要7%左右 可以据此经验，调整程序结构。多线程可以用在加载待处理串和结果输出上。 但在进行匹配时，就不要了。此时，可以提升匹配线程权重到最高级别，加快运算。 算法方面，可选的有几百种，最简单，常用的strstr() 就是QS算法， 根据模式串的特点，有不同的算法选择。 
另要根据待匹配串的特点，也有不同的算法可供选择。 这些需要经验判别。 简单说下，供你参考。