×

Loading...
Ad by
  • 推荐 OXIO 加拿大高速网络,最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务
Ad by
  • 推荐 OXIO 加拿大高速网络,最低月费仅$40. 使用推荐码 RCR37MB 可获得一个月的免费服务

再澄清一下: PATTERN 有几千个; 每个PATTERN的长度不超过50个字符. TEST字符串的长度也不超过50个字符. 其实, 我自己设计了两个行得通的算法, 但是感觉时间复杂度还是大了.

算法1: 把所有的PATTERN 放到一棵TRIE(不记得中文是不是叫字典树)上, 这棵TRIE与普通TRIE不同的地方, 在于它有通配符, 所以用TEST字符串去匹配的算法就复杂很多了. 然后, 修改了一个非递归( 递归算法相对太慢) 的用于比较两个字符串的算法, (此算法接受通配符), 用于匹配TEST字符串和含通配符的TRIE. 但是因为需要回溯, 得用堆栈, 所以还是不是很好.

算法2: 把所有PATTERN的被通配符 * 隔开的子串提取出来, 都放到一棵TRIE里, 用AHO-CORARISK算法, 找出所有匹配TEST子串的PATTERN子串, 从而筛选出可能匹配的PATTERN的子集合, 再对这个子集进行最后的检验. 问题是如果这些PATTERN大部分都有相同的子串, 则筛选的子集可能太大.
Report

Replies, comments and Discussions:

  • 工作学习 / 专业技术讨论 / 一个实际项目的算法问题:关于模式匹配.
    需要支持的通配符:
    *: 0~多个字符
    -:1个字符

    需求:
    输入: 多(几千个)PATTERN字串 ARRAY OF PATTERN, 和一个需要MATCH的字串 STR_A
    输出: ARRAY OF PATTERN 中,所有和STR_A MATCH 的PATTERN.

    如:
    输入: ARRAY OF PATTERN 为( A*, -BB, *B, DB-)
    STR_A 为 ABB
    输出: ( A*, -BB, *B )

    需要设计一个最小数量级的算法.
    • *,- 在字符的左右分别是什么意思?还是搂主的笔误?这一点需要解释清楚,比如 A*A 和 *A-B- 到底该怎么理解?
      • *代表0到多个字符, -代表一个字符.
        A*A 代表所有A开头并且A结束的字串.
        *A-B-代表所有倒数第四个字符为A并且倒数第二个字符为B的字串.
    • 在简单一点,比如 A-B*C-D,按照左右不同有2种解释:1-〉(A-)(B*)(C-)D , 2-> A(-B)(*C)(-D)... 这2种Patten所匹配的是完全不同的字符串
    • 啊,我明白了,呵呵,我理解成必须和前一个字母有关,sorry 啊
    • pattern= "A*A"能匹配string "A" 么?
      • 不行,但可以匹配AA
        • 写个NFA就可以了吧?应该不麻烦的。
          • 在网上找到某人用DFA来解决这个问题的测试结果, 他有40个带通配符(*)的PATTERN, 结果生成了大约130,000个状态, 把1.5G内存全用光了. 而我的应用里有几千个这种PATTERN.
            在网上找到某人用DFA来解决这个问题的测试结果, 他有40个带通配符(*)的PATTERN, 结果生成了大约130,000个状态, 把1.5G内存全用光了. 而我的应用里有几千个这种PATTERN.
            但是他MATCH的是PATTERN, 我要MATCH的是整个字符串, 这一点不同, 不知道是不是可以也用DFA, 但不用这么繁复.
        • 什么是 NFA?
          • 你没系统学过计算机课吧?
          • 不满您说,我就没学过计算机,我大学专业是物理,只是对逻辑挺感兴趣
          • 不知道是否准确: NFA是不确定有限自动机, DFA是确定有限自动机.
    • 算法关键:
      1)将patten 串中的 * 转换成与MARTH字串 STR_A等长的单字通配符号(例如#);
      2) 将MARTH字串 STR_A滑过patten 串比较即可;


      如:
      输入: ARRAY OF PATTERN 为( A*, -BB, *B, DB-)
      转化为: A###,-BB,###B,DB-)
      STR_A 为 ABB
      中间输出: A##, ###, -BB, ###,##B)
      反转换 :##..----> *;
      A*,*,-BB,*,*B; 再扔掉 单个*; 得最后
      输出: ( A*, -BB, *B )

      需要设计一个最小数量级的算法.
      • '*' 表示0到多个字符串, 请问怎么匹配 *CD* 跟 'ACDWFGAB'
        • ########CD########匹配ACDWFGAB; 得匹配窜#CD#####; 转换为*CD*;
          • ''*' 表示0到多个字符串' 的意思是说字符串的长度事先是不知道的, 所以不可能预先知道把它换成多少个 '#' 号.
            • 匹配时动态转;
              • 怎么动态转法?
                • 回头看看你们的算法,总觉得把简单的事情搞复杂了; 动态转是这样的
                  如和 'ACDWFGAB' 匹配,将*转成8个#; 和"abc"匹陪时将*转成3个#;
                  当然这只是算法描述; 实现时可做优化
    • 我的建议
      input: str as string, pattern as string

      扫描string, 同时取下一个pattern,

      如果pattern_char == '*' 取下一个pattern_char

      如果pattern 不等于*/-, 则string_char 必须等于pattern_char, 不等于就是不匹配;
      如果last_pattern_char等于*,则滑过若干string_char直到pattern_char ==string_char,
      如果pattern_char等于-, 责任字符都匹配,

      loop.
      • 你这好象是逐个PATTERN进行比较吧?这是最慢的算法, 不到万不得已不会用的. 我有几千个PATTERN, 这种做法会太慢了.
        • 还不至于是最慢的算法吧?O(n)的算法了,莫非你能搞出更快的?
          • 假设每个PATTERN和测试字符串的长度都为n. 在只用一个PATTERN的情况下, 考虑到MATCH '*' 需要回溯, 其算法时间是 O(n^2). 有k个PATTERN, 其时间就是 O(k*n^2)了.
            • 恩,你讲得有道理,我开始的确没有仔细考虑这个问题。
      • 兄弟,你的算法有错误,最后一行
    • 如果每个PATTERN没有什么联系,或者联系少,即使你作什么PRE-PROCESS,也不能确定能减少COMPLEXITY,除了逐个比较,还能怎么样?很多语言都支持RE,几千个不算什么。
      • 这些PATTERN有相似的可能性很大. 特别是前缀, 或者后缀.
        • 可能性很大也只是可能,极端的情况就是毫不相干,有可能PRE-PROCESS的时间和逐一比较的有一拼。实际你是在问PRE-PROCESS的算法
          • 就让我们当这些PATTERN有很多相同的前缀吧. 除了逐一比较, 还有什么方法?
            • 难,不确定因素太多,相同也是比过才知道的吧,*也算相同吧,实际上你是把以后的逐一比较的COMPLEXITY放在了PRE-PROCESS里了,具体你省了多少很难估算。
        • 搂主,你那几千数组是什么意思?是pattern数组的长度是几千还是pattern里面每一个unit的长度是几千? 如果追求速度可以把我的程序改在C++下运行会比在.net下运行快一些,不知能否满足你的要求?
    • 各位老大,你们那些算法我怎么都看不懂呀!没有人实际编程是一下吗?
      • 这儿都是10万年薪以上的Architect,没人亲自写code
    • 我来给出程序,C#版,递归算法。欢迎大家测试,有错误及时通知我!别说,这题比前几天的排列组合是难一些
      本文发表在 rolia.net 枫下论坛程序里有2个重要变量

      string array = "ACDWFGAB"; 为被测试字符串
      string[] pattern = { "*CD*", "*-GA*","--D-F*","--D-G*" }; 为Pattern数组,用来找出匹配的

      兄弟们只要修改这2个变量就可以测试我的程序了,用递归的好处就是以后再有什么新花花肠子可以相对容易的把算法加进去

      我也不知道这是不是你们说的那个NFL,AFL.....呵呵
      Rolia排版混乱,没办法,如果愿意可以留下邮箱,我把源码发给你们

      同样的,在VS2005中建立一个Console Project,把我的Codes拷贝进去就可运行
      奥,对了,本人还在找工作欧,还希望大家能帮忙,多谢多谢


      using System;
      using System.Collections.Generic;
      using System.Text;

      namespace ConsoleApplication1
      {
      class Program
      {
      static void Main(string[] args)
      {
      string array = "ACDWFGAB";
      string[] pattern = { "*CD*", "*-GA*","--D-F*","--D-G*" };
      Console.WriteLine("I am still seeking job now....");
      foreach (string s in pattern)
      {
      Pattern p = new Pattern(s, array);
      if (p.Result())
      Console.WriteLine("Pattern ( " + s + " ) match " + array);
      }
      Console.ReadLine();
      }
      }

      public class Pattern
      {
      List<string> realArray = new List<string>();
      List<string> pattern = new List<string>();

      public Pattern(string pString, string rString)
      {
      foreach (char c in pString.ToCharArray())
      pattern.Add(c.ToString());

      foreach (char c in rString.ToCharArray())
      realArray.Add(c.ToString());
      }

      public bool Result()
      {
      return Process(pattern, realArray);
      }

      public bool Process(List<string> currentPattern, List<string> currentArray)
      {
      List<string> tmpPattern = new List<string>(currentPattern);
      List<string> tmpArray = new List<string>(currentArray);

      if (currentPattern[0] == "*" && currentPattern.Count == 1) //边界
      {
      return true;
      }
      else if (currentPattern[0] == "-" && currentPattern.Count == 1 && currentArray.Count == 1) //边界
      {
      return true;
      }
      else if (currentPattern[0] == "*" && currentPattern.Count > 1 && currentPattern[1] == "-" && currentArray.Count > 0) // *--- AA
      {
      tmpPattern.RemoveAt(1);
      tmpArray.RemoveAt(0);
      return Process(tmpPattern, tmpArray);
      }
      else if (currentPattern[0] == "*" && currentPattern.Count > 1 && currentPattern[1] != "-")
      {
      for (int i = 0; i < currentArray.Count; i++)
      {
      if (currentArray[i] == currentPattern[1])
      {
      if (i == currentArray.Count - 1)
      return true;
      else
      {
      tmpArray.RemoveRange(0, i + 1);
      tmpPattern.RemoveRange(0, 2);

      if (tmpPattern.Count == 0 && tmpArray.Count > 0)
      return false;
      else
      return Process(tmpPattern, tmpArray);
      }
      }
      }
      }
      else if (currentPattern[0] == "-" && currentPattern.Count > 1)
      {
      if (currentArray.Count == 1)
      {
      return false;
      }
      else
      {
      tmpPattern.RemoveAt(0);
      tmpArray.RemoveAt(0);
      return Process(tmpPattern, tmpArray);
      }
      }
      else if (currentPattern[0] == currentArray[0])
      {
      if (currentPattern.Count == 1 && currentArray.Count == 1)
      {
      return true;
      }
      else if (currentArray.Count > 1 && currentPattern.Count > 1)
      {
      tmpPattern.RemoveAt(0);
      tmpArray.RemoveAt(0);
      return Process(tmpPattern, tmpArray);
      }
      }
      else
      return false;

      return false;
      }
      }
      }更多精彩文章及讨论,请光临枫下论坛 rolia.net
      • 感谢rolia网友有情提醒,程序有个小小的bug,但不影响大局,晚上改正
      • 不好意思, 我不懂C#. 请简单介绍一下算法.
    • 再澄清一下: PATTERN 有几千个; 每个PATTERN的长度不超过50个字符. TEST字符串的长度也不超过50个字符. 其实, 我自己设计了两个行得通的算法, 但是感觉时间复杂度还是大了.
      算法1: 把所有的PATTERN 放到一棵TRIE(不记得中文是不是叫字典树)上, 这棵TRIE与普通TRIE不同的地方, 在于它有通配符, 所以用TEST字符串去匹配的算法就复杂很多了. 然后, 修改了一个非递归( 递归算法相对太慢) 的用于比较两个字符串的算法, (此算法接受通配符), 用于匹配TEST字符串和含通配符的TRIE. 但是因为需要回溯, 得用堆栈, 所以还是不是很好.

      算法2: 把所有PATTERN的被通配符 * 隔开的子串提取出来, 都放到一棵TRIE里, 用AHO-CORARISK算法, 找出所有匹配TEST子串的PATTERN子串, 从而筛选出可能匹配的PATTERN的子集合, 再对这个子集进行最后的检验. 问题是如果这些PATTERN大部分都有相同的子串, 则筛选的子集可能太大.
      • 所以希望有过类似经验的大侠指点则个.
        • 先说一下,我也没什么经验。刚才用fgrep测试了一下, 首先用程序生成一个包含5000个随机pattern的文件,每个pattern的长度从25-50不等。然后找了一段5K的文本,用fgrep match了一下,连一秒钟都没用。
          • 嗯,这个有问题,fgrep好像不对。grep 慢得多了。
          • 您的PATTERN都包含通配符了吗? 另外, 我只需要EXACT MATCH, 即用来匹配的'文本' 跟某一个或某几个PATTERN正好匹配, 而不是只包含这些PATTERN.
            • 那个结果并不正确,我也是被answers.com忽悠了。但是用grep花的时间也是不很长,大概5分钟左右。
              另外我有个想法,不很成熟,征求你的看法。 我的想法是这样的,目标字符串str_a只有一个,pattern有若干;我们要逐一取出pattern, 匹配str_a. 原则上,每用一个pattern 匹配过一次,就会得到str_a的一些信息,如果能够把这些信息保存下来,就有可能为后面的匹配提供一些“经验”。 所以就有这样一个想法: 假设str_a = "ABCDEF" 1. 建立一个数据结构: A -> B -> C -> D -> E -> F 2. 取一个pattern, 假设:ABC*F, 匹配, 并得到下面的结构: A -> B -> C -> D -> E -> F \-> * -> 3. 取下一个pattern, 假设:A*C-F, 匹配, 并得到下面的结构: A -> B -> C -> D -> E -> F \-> * ->/ \-> * ->/ \-> - ->/ 4. 在未来的match过程中,* 首先被当成字符'*', 与旁支上的*匹配,找不到以后在作正则匹配. ... 只是个粗粗的想法,没有证明过,所以是否正确都不知道。 Free Image Hosting
              • 5分钟实在太太太长了. 不过, 你试试用50BYTE的文本, 而不是5k的文本, 可能不会这么吓人. 另外, 您的IDEA, 不是很好懂, 能否更具体点. :)
                • 看一下这个图可能说得清楚些
                  • 进不去看这个图, 出错信息: 403 Forbidden: You don't have permission to access /uploads/67cd1648e2.png on this server.
      • 搂主,我的程序5000次匹配测试用了不到1秒钟(640毫秒),这还是用效率最低的string来做,改成byte优化后会更快,我不知你要快到什么地步?
        我的测试字符串
        string array = "1234567890123456789012345678901234567890"; // 40个字符
        string[] pattern = { "*123456789-*", "1234567890----------1234567890----*", "----------1234567890------*--1234567890", "----------1234*--234567890-" };

        这是4个测试pattern, 我把它简单的*1250,最后实际的pattern数组长度是5000,我想这样能大概反映出平均运算速度。

        实际运算时间640毫秒,AMD Athlon XP 2200+, 1G RAM

        现在太忙,晚上回家我简单写一下算法
        • 有趣,发现grep德pattern个数和搜索事件不是线性关系。1000各pattern飞快,2000个就开始慢得难受了。
        • 这个,sorry 啊,grep是什么软件?我从没听说过
          • grep
    • 数据结构学过一个匹配算法,不过基本忘了。我觉得它的原理可以用在这里:逐字比较string和所有pattern, 不回头。设一个大数组存每个patten的状态。一遍就完。
      • 不知是否Karp-Rabin算法?
    • 你是要完全匹配?string AAA 匹不匹配 模式A-? 如果不,那可以先处理这几千个模式,他们肯定有矛盾的, 匹配A-就就不可能匹配B-
      • 有道理, 让我想想...
        • 关键还是看这些patten什么样。我觉得可以先按长度建个数组1~50, 每个数组里放可能的模式。有*就放到最小长度~50,
          再在每个数组里找一种算法(简单的就按第一个字符分,肯定有什么复杂的更好的算法)细分到二极数组, 这样如果模式比较均匀的话(最好不要太多*) 可能只需要比较 原来模式的1/100。
    • 各位, 我找到这篇文章, 似乎可以解决这个问题, 其算法时间复杂度是 O((|t|+|P|)*log|P|) http://citeseer.ist.psu.edu/cachedpage/132839/1 一时半刻还没看懂, 有兴趣的可以一起分析分析.
    • 我的测试结果: 进行1百万次匹配(2000个Pattern,来匹配500个字符串),费时五秒。

      Regular Expression 是Perl 语言的强项,虽然现在其他的语言都支持Regular Expression,其差别还是有的。这里算法关键是:

    • 使用预编译Reguler Expression:
      $_ = qr/$_/;
    • 使用grep函数:
      @matches = grep( { $string =~ /$_/ } @patterns); 
    • 测试用的是1.4Ghz Dell Laptop PC, Windows XP with Perl 5.8.

      这里是测试的Perl Code:
      #!/usr/bin/perl
      use strict;
      use POSIX qw(strftime);
      
      my ($string, @strings,$pattern, @subpatterns, @patterns, @matches, $totalmatches);
      
      #输入字符串和Pattern.
      $string = "1234567890123456789012345678901234567890";  # 40个字符
      #最后一个不匹配!
      @subpatterns = (  "*123456789-*",    "1234567890----------1234567890----*", 
         "----------1234567890------*--1234567890",   "----------1235*--234567890-");
      
      # 转化到Perl Patterns,并预编译patterns。
      @subpatterns = map { $_=~s/\*/.*/g; $_=~ s/-/./g; $_ = qr/$_/; $_; } @subpatterns;
      
      # 产生测试数据 :  2000个Pattern,500个字符串
      push (@patterns, @subpatterns) foreach (1..500);  # 2000 patterns 
      push (@strings, $string) foreach (1..500);  # 500 string arrays
      print "Total patterns: ", scalar(@patterns), 
            ", Total number of strings: ", scalar(@strings), 
            ", Total matches to be tested: ", scalar(@patterns) * scalar(@strings), "\n";
      
      
      #进行匹配测试。
      print "Start match at ", strftime("%Y/%m/%d,%H:%M:%S", localtime()), "\n"; 
      $totalmatches =0;
      foreach $string (@strings)
      {       @matches = grep( { $string =~ /$_/ } @patterns);
              $totalmatches += scalar(@matches);
      }
      print "Stop match at ", strftime("%Y/%m/%d,%H:%M:%S", localtime()), "\n",
            "Total matched: $totalmatches.\n";
      

      这里是测试的输出结果:

      Total patterns: 2000, Total number of strings: 500, Total matches to be tested: 1000000
      Start match at 2006/03/13,09:27:24
      Stop match at 2006/03/13,09:27:29
      Total matched: 750000.