我有一个字符串数组，可以用正斜杠分隔，例如754或754/128。这些字符串可以有一个未定义的长度，换句话说：可能出现如下情况：1234/34/21/120/3在数组中，我只想保留包含其他模式的更专业的模式例如，在上面的第一个示例中754/128包含754，因此可以从数组中删除754。
这种包含的概念正如人们所期望的那样广泛，甚至可能更广泛：它类似于您如何看待一个有向图，其中模式中的每一个斜线都指向前进一步。包含的模式可以是任意长度的，只要它以某种方式位于包含的模式中。这意味着小路径可以以任何形式（按时间顺序正确）出现。例如，903/900包含在903/902/900中，即使模式是“split open”。一种可视化的方法是：在小径上，我们从A点到B点。在大径上，我们也从A桥到B桥，但我们在C点停留。大径比小径访问更多的地方，而不会遗漏任何东西。因此，只要遵守路径的顺序，较小的路径可以以任何拆分形式出现。例如：
2/5 - 1/2/3/4/5
# included
5/2 - 1/2/3/4/5
# not included
我在这里的意思是“包含”项在大路径中的位置应该相同例如：
1/3/2中的“matches”，因为大小路径中的顺序相同：1/5/3/4/2位于1之前的某个位置，而3则位于2之前的某个位置1/2/3、2/1/3等将不匹配较大的路径，即使它们是具有相同项的有效路径。这是因为发生的顺序不同。上面的示例还说明了小模式中的项可以出现在大模式中的任何位置；而不仅仅出现在第一个和最后一个位置或随后的位置。换句话说，
1/5/3/4/2的所有包含路径都是：1/2
1/2/3
1/3
1/4
2/3
2/3/4
2/4
3/4
我正在寻找一种有效的方法，从同一个数组中删除包含在其他数组中的给定数组中的路径。
我得到了this far，但我不确定应该如何有效地检查两个项目之间的包含关系。
#!/usr/bin/perl
my @arr = ("903/900", "903/902/900", "903/904/902/901", "903/904/902/908/900", "903");
my @res = ();
OUTER: for (my $i = 0; $i < @arr; $i++) {
my $first = $arr[$i];
my $j = $i+1;
INNER: while($j < @arr) {
my $second = $arr[$j];
&compare_paths($first, $second);
$j++;
}
}
sub compare_paths {
my ($first, $second) = @_;
@first_items = split(/\//, $first);
@second_items = split(/\//, $second);
# Compare values from 1 and 2
}
上面代码的预期输出是
@res = ("903/904/902/901", "903/904/902/908/900");
搬迁原因：
1/2/3/4包含在903/900中903/902/900包含在903/902/900中903/904/902/908/900包含在903中如何有效地实现这种算法？我的主要想法是检查
903/904/902/901的项是否存在于@first_items中（如果不继续），但如果存在，则检查是否还存在第二个项，如果存在：检查其子字符串位置这必须大于第一个项目子字符串位置。对每个项继续（对$second和@second_items则相反），直到所有字符串都匹配为止（如果这有助于提高速度，则可以将初始数组替换为散列，前一个数组作为密钥。） 最佳答案
我希望有一些通用算法可以解决这个问题，可能还有一些库可以利用。不过，这是一个手卷的。
首先，我们根据路径中的项数对数组进行排序。然后我们上那个数组，比较每个元素和所有更长的元素。这样，每个路径都会尽早被排除。
比较是在/上分裂得到的阵列。它检查小数组中的所有元素是否作为一个精确的子序列在大数组中，以便大数组只通过删除元素（不重新排列）产生小数组。
use warnings;
use strict;
my @arr = qw(902/904 903/900 903/902/900 903/904/902/901
903/904/902/908/900 903);
my @sorted = sort { (split '/', $a) > (split '/', $b) } @arr;
my @primes;
OUTER:
for my $i (0..$#sorted) {
for my $j ($i+1..$#sorted) {
next OUTER if is_contained($sorted[$i], $sorted[$j]);
}
push @primes, $sorted[$i];
}
print "@primes\n";
sub is_contained
{
my ($small, $large) = @_;
my @small = split '/', $small;
my @large = split '/', $large;
# There can be no duplicates so equal-length paths are distinct
return 0 if @small == @large;
# Indices of elements of @small in @large cannot decrease
my ($match, $index) = (0, 0);
for my $sm (@small) {
for my $i (0..$#large) {
$sm == $large[$i] || next;
return 0 if $i < $index; # out of order
$index = $i;
$match = 1;
last;
}
return 0 if not $match; # $sm from @small not in @large
$match = 0;
}
return 1;
}
打印行：
902/904 903/904/902/901 903/904/902/908/900。关于如何检查
@smaller是否与@larger中的子序列匹配的说明。一旦在
@smaller中找到@larger元素，它的索引就在@larger不能低于以前找到的值。元素必须在前一个元素之后，而不是之前。请参阅下面的其他过程。
因此，对于
2/7/5和1/2/5/7/8，首先在索引1处发现2，然后在索引3处发现7，然后在索引2处发现5。子序列2-5-7与2-7-5不匹配我在数据中添加了902/904来测试这一点。这是另一个检查路径是否包含在另一个路径中的过程。
一旦在
@smaller中找到@larger元素，它将从@larger中的下一个索引开始搜索下一个元素这样，它跳过了路径的搜索部分，但也无法及早检测出无序元素。以
2/7/5和1/2/5/7/8为例，在索引3处找到7后，它从索引4开始，通过在目标路径的其余部分找不到5来检测失败。sub is_contained_2
{
my @large = split '/', $_[0];
my @small = split '/', $_[1];
# Is @small found in @large as an exact sub-sequence?
my ($match, $j) = (0, 0);
for my $sm (@small) {
for my $i ($j..$#large) {
$sm == $large[$i] || next;
$j = $i+1, $match = 1;
last;
}
return 0 if not $match;
$match = 0;
}
return 1;
}
对于这个数据集，这个速度要慢一些（10-15%），请参见下面的benchmark注释。
我在这里对这两个基于数组的版本和ikegami的regex+trie进行了基准测试。到目前为止，我只使用了问题中的特定数据集，并添加了
902/904。use warnings;
use strict;
use Benchmark qw(cmpthese);
my $secs_to_run = shift || 10;
my @arr = ('902/904', '903/900', '903/902/900', '903/904/902/901',
'903/904', '/902/908/900', '903');
# sorted array checked shorter-to-longer, manual iterations
sub contained {
my ($rarr) = @_; my @arr = @$arr;
# program copied from this post
return \@primes;
}
sub is_contained { ... } # copied
# Same program, but using is_contained_2()
sub contained_2 { ... }
sub is_contained_2 { ... }
# Regex-trie, copied from ikegami's post
sub add { my $p = \shift; $p = \( $$p->{$_} ) for @_, ''; }
sub as_pat { my $trie = shift; ... } # copied
sub regex_trie {
my ($rpaths) = @_; my @paths = @$rpaths;
# program copied from ikegami's post
return \@filtered_paths;
}
cmpthese(-$secs_to_run, {
containted => sub { my $rprimes = contained(\@arr) },
cont_next => sub { my $rprimes = contained_2(\@arr) },
regex_trie => sub { my $rfiltered = regex_trie(\@arr) },
});
在v5.16的较新工作站笔记本电脑（2.5ghz）上使用
bench_cont.pl 300。Rate regex_trie cont_next containted regex_trie 15264/s -- -15% -27% cont_next 17946/s 18% -- -14% containted 20939/s 37% 17% --
on an older server (2.8GHz) with v5.16
Rate regex_trie cont_next containted regex_trie 11750/s -- -13% -27% cont_next 13537/s 15% -- -16% containted 16042/s 37% 19% --
on an older server (3.5GHz) with v5.10
Rate cont_next regex_trie containted cont_next 12266/s -- -17% -17% regex_trie 14832/s 21% -- -0% containted 14845/s 21% 0% --
This surprised me, as I expected the regex-based solution to be fastest.
I expect the trend to reverse for data composed of longer paths, having more distinct (not contained) paths, with containment found later in the path, and with a few out-of-order dismissals.
I'll add tests once I get to generate such data, or once it is provided.
To track some of the processing change the body to
use feature 'say';
OUTER:
for my $i (0..$#sorted) {
say "Check $sorted[$i]";
for my $j ($i+1..$#sorted) {
my $is_inside = is_contained($sorted[$i], $sorted[$j]);
say "\t$is_inside: $sorted_arr[$i] inside $sorted_arr[$j]";
next OUTER if $is_inside;
}
push @primes, $sorted[$i];
}
say "\nNot contained: @primes";
这个指纹
支票903
0:903对902/904
1:903对903/900
支票902/904
0:902/904对903/900
0:902/904对903/902/900
0:902/904对903/904/902/901
0:902/904对903/904/902/908/900
支票903/900
1:903/900对903/902/900
支票903/902/900
0:903/902/900对903/904/902/901
1:903/902/900对903/904/902/908/900
支票903/904/902/901
0:903/904/902/901与903/904/902/908/900
支票903/904/902/908/900
未包含：902/904 903/904/902/901 903/904/902/908/900
关于algorithm - 比较字符串并在Perl中删除更多常规模式，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41252191/