[探讨]字符串匹配算法扩展算法

Perlvim

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 的结构，这些结构都是可嵌套的。

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

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

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

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

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

Perlvim

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

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

测试代码：

1. #!perl
   
2. 
   
3. use 5.014;
   
4. use YAML qw(Dump);
   
5. use String::NestMatch qw(nest_match);
   
6. 
   
7. my $str = 'if a then if b then if c then d end end end if f then g end';
   
8. say(Dump(nest_match($str, { if => 'end'})));
   
9. my $text = "<table><tr><td>aaa</td></tr></table>";
   
10. say(Dump(nest_match($text, { '<tr>' => '</tr>', '<td>' => '</td>' })));
    
11. my $str1 = 'if a then for b in c end end';
    
12. 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. ---
    
12. 1:
    
13.   - '<tr><td>aaa</td></tr>'
    
14. 2:
    
15.   - '<td>aaa</td>'
    
16. 
    
17. ---
    
18. 1:
    
19.   - if a then for b in c end end
    
20. 2:
    
21.   - for b in c end
    
22. 
    
23. >Exit code: 0    Time: 0.549

复制代码

模块源代码：

1. package String::NestMatch;
   
2. 
   
3. use Exporter;
   
4. our @ISA = qw(Exporter);
   
5. our @EXPORT_OK = qw(nest_match);
   
6. 
   
7. use 5.010;
   
8. use strict;
   
9. use warnings;
   
10. use YAML qw(Dump);
    
11. 
    
12. my $count = 127;
    
13. my $id_char = {};
    
14. my $char_id = {};
    
15. 
    
16. sub apply_id_char {
    
17.   my $id = shift;
    
18.   $count++;
    
19.   my $char = chr($count);
    
20.   $id_char->{$id} = $char;
    
21.   $char_id->{$char} = $id;
    
22.   return $char;
    
23. }
    
24. 
    
25. sub char_id_in_text {
    
26.   my ($text, @id) = @_;
    
27.   foreach my $id (@id) {
    
28.     if (length($id) == 1) {
    
29.       $char_id->{$id} = $id;
    
30.       $id_char->{$id} = $id;
    
31.       next;
    
32.     }
    
33.     next if (exists $id_char->{$id});
    
34.     my $char = apply_id_char($id);
    
35.     if ($id =~ /^\w+$/) {
    
36.       $text =~ s/\b$id\b/$char/g;
    
37.     }
    
38.     elsif ($id =~ /\w$/) {
    
39.       $text =~ s/\Q$id\E\b/$char/g;
    
40.     }
    
41.     elsif ($id =~ /^\w/) {
    
42.       $text =~ s/\b\Q$id\E/$char/g;
    
43.     }
    
44.     else {
    
45.       $text =~ s/\Q$id\E/$char/g;
    
46.     }
    
47.   }
    
48.   return $text;
    
49. }
    
50. 
    
51. sub nest_match {
    
52.   my ($str, $rule) = @_;
    
53.   my $match_start = {};
    
54.   my $start_end_id = {};
    
55.   while (my ($start_str, $end_str) = each %$rule) {
    
56.     $str = char_id_in_text($str, $start_str, $end_str);
    
57.     # say $str;
    
58.     my $start_char = $id_char->{$start_str};
    
59.     my $end_char   = $id_char->{$end_str};
    
60.     if (exists $match_start->{$start_char}) {
    
61.       $match_start->{$start_char}{$end_char} = 1;
    
62.     }
    
63.     else {
    
64.       $match_start->{$start_char} = { $end_char => 1 };
    
65.     }
    
66.   }
    
67.   # default depth
    
68.   my $depth = 0;
    
69.   my $depth_chars = { 0 => [] };
    
70.   # according depth to save matched string
    
71.   my $depth_match_str = { };
    
72.   my $depth_start_char = { 0 => '' };
    
73.   my $expect_end_chars = {};
    
74. 
    
75.   my @text_chars = split //, $str;
    
76.   foreach my $char (@text_chars) {
    
77.     if (exists $expect_end_chars->{$char}) {
    
78.       push @{$depth_chars->{$depth}}, $char_id->{$char};
    
79.       my $depth_str = join '', @{ $depth_chars->{$depth} };
    
80.       if (exists $depth_match_str->{$depth}) {
    
81.         push @{$depth_match_str->{$depth}}, $depth_str;
    
82.       }
    
83.       else {
    
84.         $depth_match_str->{$depth} = [ $depth_str ];
    
85.       }
    
86.       $depth = $depth - 1;
    
87.       push @{ $depth_chars->{$depth} }, $depth_str;
    
88.       my $current_start_char = $depth_start_char->{$depth};
    
89.       if ($depth == 0) {
    
90.         $expect_end_chars = {};
    
91.       } else {
    
92.         $expect_end_chars = $match_start->{$current_start_char};
    
93.       }
    
94.       if (exists $match_start->{$char}) {
    
95.         $depth = $depth + 1;
    
96.         $depth_chars->{$depth} = [ $char_id->{$char} ];
    
97.         $expect_end_chars = $match_start->{$char};
    
98.         $depth_start_char->{$depth} = $char;
    
99.       }
    
100.     }
     
101.     else {
     
102.       if (exists $match_start->{$char}) {
     
103.         $depth = $depth + 1;
     
104.         $depth_chars->{$depth} = [ $char_id->{$char} ];
     
105.         $expect_end_chars = $match_start->{$char};
     
106.         $depth_start_char->{$depth} = $char;
     
107.       }
     
108.       else {
     
109.         push @{ $depth_chars->{$depth} }, $char;
     
110.       }
     
111.     }
     
112.   }
     
113.   $count = 127; $id_char = {}; $char_id = {};
     
114.   return $depth_match_str;
     
115. }
     
116. 
     
117. 1;
     

复制代码

rubyish

3Q~这种算法很好

routesf

回复 2# Perlvim


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

routesf

回复 4# routesf


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

Perlvim

是的，代码算法有问题，已经更正。在第29行到30行之间增加一行：
$id_char->{$id} = $id;

followcn

用调试的方式，好好学习了一下。
一个字符，一个字符的处理，这样效率是否有问题？在两个关键字之间的字符串能否一起处理呢。

Perlvim

回复 7# followcn
所有字符串的算法，其实都是一个一个的处理。否则怎么知道到达了边界？正则表达式看似很快，也是一个一个字符的处理。如果有分支和分组的话，一个字符要处理好几次。所以分支的处理，分开后反而效率更高：

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


   

followcn

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

Perlvim

如果想把类似的单词先替换成一个字节的字符，让扫描的时候，只扫描一次，这个算法就快多了。
你提醒了我，可以在将关键字替换成单字节字符的同时，将其他的单词一起替换成单字节字符。

这样，就快多了