Проверить, действительно ли данная строка соответствует одному из наборов префиксов

Какой алгоритм использовать для проверки соответствия данной строки одному из наборов префиксов и какому префиксу из этого набора?

Другой вариант: задан путь и набор каталогов, как проверить, находится ли путь в одном из наборов каталогов (при условии, что нет символических ссылок или они не имеют значения)?

Меня интересует описание или название алгоритма, или модуль Perl, который решает эту проблему (или может быть использован для решения этой проблемы).

Редактировать
Бонусные баллы за решение, позволяющее эффективно находить отношение 'is prefix of' между набором строк (набором каталогов)

Например, для данного набора каталогов: foo, foo/bar, foo/baz, quux, baz/quux, baz/quux/plugh алгоритм должен найти, что foo является префиксом foo/bar и foo/baz, и что baz/quux является префиксом baz/quux/plugh... надеюсь, без O(n^2) времени.


match matching perl
person Jakub Narębski    schedule 27.02.2011    source источник
comment
+1 только за тот простой факт, что вы не хотите изобретать велосипед, если вам это не нужно!   -  person corsiKa    schedule 27.02.2011
comment
Я думаю, что мои примеры теперь отражают ваше редактирование, если нет, то, пожалуйста, объясните подробнее   -  person Joel Berger    schedule 27.02.2011
comment
мои примеры, безусловно, могут быть расширены для перебора входных данных и поиска выходных данных, но я думаю, что они будут O (n ^ 2) вплоть до экономии за счет короткого замыкания. Возможно, кто-то более умный, чем я, найдет более эффективный способ сделать это. Я предполагаю, что для этого потребуется что-то вроде объединения и регулярного выражения объединенных наборов; пока у вас есть два списка, которые нужно сравнить, я думаю, что это должно быть O (n ^ 2), насколько я понимаю   -  person Joel Berger    schedule 27.02.2011
comment
посмотрите мое редактирование на сопоставлении Aho-Corasick и Trie, надеюсь, вы найдете что-то в этом или у кого-то еще есть больше. Мы на пределе моих знаний, удачи!   -  person Joel Berger    schedule 27.02.2011

Ответы (3)


arrow_upward
2
arrow_downward

Эффективным способом сделать это будет использование Trie:

http://en.wikipedia.org/wiki/Trie

На CPAN есть пакет для него:

https://metacpan.org/pod/Tree::Trie

(хотя сам никогда не использовал этот пакет)

Вы должны учитывать, какие операции должны быть наиболее эффективными. Поиск в Trie очень дешевый, но если вы строите trie только для одного поиска, это может быть не самый быстрый способ...

person markijbema    schedule 27.02.2011

arrow_upward
1
arrow_downward

Функция first в основном модуле List::Util может определить, соответствует ли префикс строке. . Он просматривает список префиксов и возвращается, как только находит совпадение. Он не выполняет поиск по всему списку, если в этом нет необходимости:

first возвращает первый элемент, где результатом BLOCK является истинное значение. Если BLOCK никогда не возвращает true или LIST был пуст, то возвращается undef.

person toolic    schedule 27.02.2011
comment
Спасибо, заглушил на короткое замыкание, пока искал. Проголосовал за вас, а затем привел пример в моем ответе. - person Joel Berger; 27.02.2011

arrow_upward
1
arrow_downward

Вы задаете интересный вопрос, но когда я пошел искать такую ​​штуку (например, в List::MoreUtils), я все время возвращался к тому, чем это отличается от grep. Вот она, моя базовая реализация, основанная на grep. Если вы не возражаете против поиска по всему списку или хотите найти все совпадения, вот пример:

#!/usr/bin/perl

use strict;
use warnings;

my @prefixes = qw/ pre1 pre2 pre3 /;

my $test = 'pre1fixed';
my @found = grep { $test =~ /^$_/ } @prefixes;

print "$_ is a prefix of $test\n" for @found;

Я также думаю, что должен быть какой-то способ использовать оператор умного сопоставления ~~, чтобы сделать это коротким путем. Кроме того, как указывает toolic, для этого также можно использовать функцию List::Util. Это останавливает поиск после того, как совпадение найдено.

#!/usr/bin/perl

use strict;
use warnings;

use List::Util qw/first/;

my @prefixes = qw/ pre1 pre2 pre3 /;

my $test = 'pre1fixed';
my $found = first { $test =~ /^$_/ } @prefixes;

print "$found is the prefix of $test\n";

Единственный известный мне алгоритм — это Aho-Corasick. оставлю читателю (т.е. я не знаю) в качестве упражнения, чтобы посмотреть, поможет ли это вам. Я вижу, что есть модуль (Algorithm::AhoCorasick). Мне также кажется, что я где-то читал, что структуры this и trie реализуются в сопоставлении Perl при определенных обстоятельствах. Может быть, кто-то знает, где я это читал? Изменить: нашел его в SO question о сопоставлении альтернатив

person Joel Berger    schedule 27.02.2011
comment
grep всегда будет искать по всему списку, тогда как функции List::Util и List::MoreUtils могут прекратить поиск, как только будет найдено совпадение. Это может быть более эффективным для больших списков. - person toolic; 27.02.2011
comment
@toolic, я согласен и только что добавил такой комментарий к моему ответу, однако ОП специально не просит короткого замыкания в своем вопросе. - person Joel Berger; 27.02.2011
comment
Вы спросили, чем List::MoreUtils отличается от grep. Итак, я дал вам один способ, которым они отличаются. - person toolic; 27.02.2011