[探討]字符串匹配算法擴(kuò)展算法

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 的結(jié)構(gòu)，還有 do .. end 的結(jié)構(gòu)，這些結(jié)構(gòu)都是可嵌套的。

如果你的算法是優(yōu)秀的，那么試試能不能擴(kuò)展一下，可以計(jì)算多種結(jié)構(gòu)的嵌套。

我發(fā)布的算法，已經(jīng)有解決方案了，只是想把這些有用的算法需求，分享給大家，娛樂一下：

前面發(fā)布的一個(gè)算法需求很簡單，但得到的代碼已經(jīng)非常復(fù)雜了。實(shí)際的需求更加復(fù)雜。

一個(gè)最簡單的語言中，可嵌套的結(jié)構(gòu)除了循環(huán)，判斷語句，還有數(shù)據(jù)結(jié)構(gòu)，函數(shù)定義。這些結(jié)構(gòu)要是一起來的話，您的算法要怎么擴(kuò)展呢？

也許我的算法讓大家很受打擊，但真實(shí)的需求就是這樣的。

Perlvim

String::NestMatch 模塊的 nest_match 方法可以處理：

它接受一個(gè)首尾字符串散列作為參數(shù)，不但可以處理單字符為標(biāo)志的結(jié)構(gòu)，也能處理多字符為標(biāo)志的結(jié)構(gòu)，能夠處理任意深度。使用了最基本的字符串替換算法，可以在 sed, awk, Lua, 等算法簡單的語言中實(shí)現(xiàn)。

測(cè)試代碼：

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' })));

復(fù)制代碼

輸出：

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

復(fù)制代碼

模塊源代碼：

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;
     

復(fù)制代碼

rubyish

3Q~這種算法很好

routesf

回復(fù) 2# Perlvim


這是哪里的module,CPAN上沒查到，perlvim自己寫的?

routesf

回復(fù) 4# routesf


    我試了一下，括號(hào)似乎處理不了，類似這樣的
my $str3 = q(
interfaces {
    fxp0 {  
    unit 0 {
        family inet {
        address 192.168.83.16/24;
        }      
    }      
    }      
}      
);
say(Dump(nest_match($str3, { '{' => '}' })));

Perlvim

是的，代碼算法有問題，已經(jīng)更正。在第29行到30行之間增加一行：
$id_char->{$id} = $id;

followcn

用調(diào)試的方式，好好學(xué)習(xí)了一下。
一個(gè)字符，一個(gè)字符的處理，這樣效率是否有問題？在兩個(gè)關(guān)鍵字之間的字符串能否一起處理呢。

Perlvim

回復(fù) 7# followcn
所有字符串的算法，其實(shí)都是一個(gè)一個(gè)的處理。否則怎么知道到達(dá)了邊界？正則表達(dá)式看似很快，也是一個(gè)一個(gè)字符的處理。如果有分支和分組的話，一個(gè)字符要處理好幾次。所以分支的處理，分開后反而效率更高：

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


   

followcn

可能是我的意思表達(dá)的不清楚，例如對(duì)下例中someting的處理
模塊中對(duì)something這樣的詞要循環(huán)9次，進(jìn)行判斷。
if somethting end

Perlvim

如果想把類似的單詞先替換成一個(gè)字節(jié)的字符，讓掃描的時(shí)候，只掃描一次，這個(gè)算法就快多了。
你提醒了我，可以在將關(guān)鍵字替換成單字節(jié)字符的同時(shí)，將其他的單詞一起替換成單字節(jié)字符。

這樣，就快多了