Проверьте, соответствует ли данная строка одному из множества префиксов, эффективно - PullRequest
Новая
       14

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

2 голосов
/ 27 февраля 2011

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

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

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

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

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

Ответы [ 3 ]

2 голосов
/ 27 февраля 2011

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

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

Существует пакет для этого на CPAN:

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

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

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

1 голос
/ 27 февраля 2011

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

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

1 голос
/ 27 февраля 2011

Вы задаете интересный вопрос, но когда я отправился искать такую ​​вещь (например, в 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;

Я также думаю, что должен быть какой-то способ использования оператора умного совпадения ~~сделать это в коротком замыкании.Кроме того, как указывает инструмент, для этого тоже можно использовать функцию 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 при определенных обстоятельствах.Возможно, кто-то знает, где я это прочитал?Редактировать: нашел в ТАК вопрос о соответствующих альтернативах

...