忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
查看: 1938 | 回复: 9

[探讨]字符串匹配算法扩展算法 [复制链接]

论坛徽章:
0
发表于 2013-04-27 13:51 |显示全部楼层
my $str = 'if a then b do f end end'

=>
{
   0 => 'if a then b do f end end',
   1 => 'do f end',
}

注意这里面不只是只有 if ... end 的结构,还有 do .. end 的结构,这些结构都是可嵌套的。

如果你的算法是优秀的,那么试试能不能扩展一下,可以计算多种结构的嵌套。

我发布的算法,已经有解决方案了,只是想把这些有用的算法需求,分享给大家,娱乐一下:

前面发布的一个算法需求很简单,但得到的代码已经非常复杂了。实际的需求更加复杂。

一个最简单的语言中,可嵌套的结构除了循环,判断语句,还有数据结构,函数定义。这些结构要是一起来的话,您的算法要怎么扩展呢?

也许我的算法让大家很受打击,但真实的需求就是这样的。

论坛徽章:
0
发表于 2013-05-02 23:36 |显示全部楼层
本帖最后由 Perlvim 于 2013-05-03 18:26 编辑

String::NestMatch 模块的 nest_match 方法可以处理:

它接受一个首尾字符串散列作为参数,不但可以处理单字符为标志的结构,也能处理多字符为标志的结构,能够处理任意深度。使用了最基本的字符串替换算法,可以在 sed, awk, Lua, 等算法简单的语言中实现。

测试代码:
  1. #!perl

  2. use 5.014;
  3. use YAML qw(Dump);
  4. use String::NestMatch qw(nest_match);

  5. my $str = 'if a then if b then if c then d end end end if f then g end';
  6. say(Dump(nest_match($str, { if => 'end'})));
  7. my $text = "<table><tr><td>aaa</td></tr></table>";
  8. say(Dump(nest_match($text, { '<tr>' => '</tr>', '<td>' => '</td>' })));
  9. my $str1 = 'if a then for b in c end end';
  10. say(Dump(nest_match($str1, { 'if' => 'end', 'for' => 'end' })));
复制代码
输出:
  1. >perl -w test_nest_match.pl
  2. ---
  3. 1:
  4.   - if a then if b then if c then d end end end
  5.   - if f then g end
  6. 2:
  7.   - if b then if c then d end end
  8. 3:
  9.   - if c then d end

  10. ---
  11. 1:
  12.   - '<tr><td>aaa</td></tr>'
  13. 2:
  14.   - '<td>aaa</td>'

  15. ---
  16. 1:
  17.   - if a then for b in c end end
  18. 2:
  19.   - for b in c end

  20. >Exit code: 0    Time: 0.549
复制代码
模块源代码:
  1. package String::NestMatch;

  2. use Exporter;
  3. our @ISA = qw(Exporter);
  4. our @EXPORT_OK = qw(nest_match);

  5. use 5.010;
  6. use strict;
  7. use warnings;
  8. use YAML qw(Dump);

  9. my $count = 127;
  10. my $id_char = {};
  11. my $char_id = {};

  12. sub apply_id_char {
  13.   my $id = shift;
  14.   $count++;
  15.   my $char = chr($count);
  16.   $id_char->{$id} = $char;
  17.   $char_id->{$char} = $id;
  18.   return $char;
  19. }

  20. sub char_id_in_text {
  21.   my ($text, @id) = @_;
  22.   foreach my $id (@id) {
  23.     if (length($id) == 1) {
  24.       $char_id->{$id} = $id;
  25.       $id_char->{$id} = $id;
  26.       next;
  27.     }
  28.     next if (exists $id_char->{$id});
  29.     my $char = apply_id_char($id);
  30.     if ($id =~ /^\w+$/) {
  31.       $text =~ s/\b$id\b/$char/g;
  32.     }
  33.     elsif ($id =~ /\w$/) {
  34.       $text =~ s/\Q$id\E\b/$char/g;
  35.     }
  36.     elsif ($id =~ /^\w/) {
  37.       $text =~ s/\b\Q$id\E/$char/g;
  38.     }
  39.     else {
  40.       $text =~ s/\Q$id\E/$char/g;
  41.     }
  42.   }
  43.   return $text;
  44. }

  45. sub nest_match {
  46.   my ($str, $rule) = @_;
  47.   my $match_start = {};
  48.   my $start_end_id = {};
  49.   while (my ($start_str, $end_str) = each %$rule) {
  50.     $str = char_id_in_text($str, $start_str, $end_str);
  51.     # say $str;
  52.     my $start_char = $id_char->{$start_str};
  53.     my $end_char   = $id_char->{$end_str};
  54.     if (exists $match_start->{$start_char}) {
  55.       $match_start->{$start_char}{$end_char} = 1;
  56.     }
  57.     else {
  58.       $match_start->{$start_char} = { $end_char => 1 };
  59.     }
  60.   }
  61.   # default depth
  62.   my $depth = 0;
  63.   my $depth_chars = { 0 => [] };
  64.   # according depth to save matched string
  65.   my $depth_match_str = { };
  66.   my $depth_start_char = { 0 => '' };
  67.   my $expect_end_chars = {};

  68.   my @text_chars = split //, $str;
  69.   foreach my $char (@text_chars) {
  70.     if (exists $expect_end_chars->{$char}) {
  71.       push @{$depth_chars->{$depth}}, $char_id->{$char};
  72.       my $depth_str = join '', @{ $depth_chars->{$depth} };
  73.       if (exists $depth_match_str->{$depth}) {
  74.         push @{$depth_match_str->{$depth}}, $depth_str;
  75.       }
  76.       else {
  77.         $depth_match_str->{$depth} = [ $depth_str ];
  78.       }
  79.       $depth = $depth - 1;
  80.       push @{ $depth_chars->{$depth} }, $depth_str;
  81.       my $current_start_char = $depth_start_char->{$depth};
  82.       if ($depth == 0) {
  83.         $expect_end_chars = {};
  84.       } else {
  85.         $expect_end_chars = $match_start->{$current_start_char};
  86.       }
  87.       if (exists $match_start->{$char}) {
  88.         $depth = $depth + 1;
  89.         $depth_chars->{$depth} = [ $char_id->{$char} ];
  90.         $expect_end_chars = $match_start->{$char};
  91.         $depth_start_char->{$depth} = $char;
  92.       }
  93.     }
  94.     else {
  95.       if (exists $match_start->{$char}) {
  96.         $depth = $depth + 1;
  97.         $depth_chars->{$depth} = [ $char_id->{$char} ];
  98.         $expect_end_chars = $match_start->{$char};
  99.         $depth_start_char->{$depth} = $char;
  100.       }
  101.       else {
  102.         push @{ $depth_chars->{$depth} }, $char;
  103.       }
  104.     }
  105.   }
  106.   $count = 127; $id_char = {}; $char_id = {};
  107.   return $depth_match_str;
  108. }

  109. 1;
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2013-05-03 08:46 |显示全部楼层
3Q~这种算法很好

论坛徽章:
0
发表于 2013-05-03 10:40 |显示全部楼层
回复 2# Perlvim


这是哪里的module,CPAN上没查到,perlvim自己写的?

论坛徽章:
0
发表于 2013-05-03 14:52 |显示全部楼层
回复 4# routesf


    我试了一下,括号似乎处理不了,类似这样的
my $str3 = q(
interfaces {
    fxp0 {  
    unit 0 {
        family inet {
        address 192.168.83.16/24;
        }      
    }      
    }      
}      
);
say(Dump(nest_match($str3, { '{' => '}' })));

论坛徽章:
0
发表于 2013-05-03 18:13 |显示全部楼层
是的,代码算法有问题,已经更正。在第29行到30行之间增加一行:
$id_char->{$id} = $id;

论坛徽章:
0
发表于 2013-05-06 11:46 |显示全部楼层
用调试的方式,好好学习了一下。
一个字符,一个字符的处理,这样效率是否有问题?在两个关键字之间的字符串能否一起处理呢。

论坛徽章:
0
发表于 2013-05-06 12:55 |显示全部楼层
回复 7# followcn
所有字符串的算法,其实都是一个一个的处理。否则怎么知道到达了边界?正则表达式看似很快,也是一个一个字符的处理。如果有分支和分组的话,一个字符要处理好几次。所以分支的处理,分开后反而效率更高:

/branch1/ && /branch2/  => /branch1|branch2/


   

论坛徽章:
0
发表于 2013-05-07 15:32 |显示全部楼层
本帖最后由 followcn 于 2013-05-07 15:34 编辑

可能是我的意思表达的不清楚,例如对下例中someting的处理
模块中对something这样的词要循环9次,进行判断。
if somethting end

论坛徽章:
0
发表于 2013-05-07 18:37 |显示全部楼层
如果想把类似的单词先替换成一个字节的字符,让扫描的时候,只扫描一次,这个算法就快多了。
你提醒了我,可以在将关键字替换成单字节字符的同时,将其他的单词一起替换成单字节字符。

这样,就快多了
您需要登录后才可以回帖 登录 | 注册

本版积分规则

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP