Алгоритмическая задача
Dec. 1st, 2005 10:35 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
catpadЗадача пришла из жизни. Это не просто упражнение, а совершенно реальная задача, которую мне необходимо решить на работе. Я её решил, но, может быть, кто-то придумает лучше.
Дано множество строк, например:
voda
eric
nec
и так далее - размер множества любой.
На входе алгоритм получает произвольную строку, например: "vodafone.com".
Как наиболее быстрым способом определить, что эта строка содержит в качестве подстроки (substring) одну из данного множества ?
(В приведённом примере ответ положительный, потому что "voda" - это подстрока "vodafone.com").
Задача простая, но ключевые слова здесь, конечно - "наиболее быстро".
Я придумал как это сделать почти за линейное время. "Почти" в смысле, что я не очень хорошо помню, что такое "amortized complexity", но, кажется, получается как раз O(n).
Завтра опубликую ответ, но хотелось бы посмотреть на разные предложения.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2005-12-01 02:05 am (UTC)no subject
Date: 2005-12-01 04:18 am (UTC).*((voda)|(eric)|(nec)).*
откомпилировать в детерминированый КА и за линейное время определить принадлежит ли одно из ключевых слов входному и заодно определить какое.
расходы на компиляцию константные. матчинг по детерминированному КА - линейное время.
подробнее читать - Ахо и Ульмана, либо найти либу по работе с regexp'ами, которая так уже делает.
no subject
Date: 2005-12-01 10:24 am (UTC)Кроме того, для одной строки известны алгоритмы, которые ищут ее быстрее, чем если ее интерпретировать как регулярное выражение (они заглядывают вперед, и смотрят на сколько символов надо сместиться - получается в константу, зависящую от длины искомой строки, раз быстрее). Эти алгоритмы должны обобщаться и на регулярные выражения, но мне такие не известны.
no subject
Date: 2005-12-01 10:30 am (UTC)ногами не бить - я не программист :)
Date: 2005-12-01 05:40 am (UTC)Если у тебя K заданных строчек и входящая строка длиной N, то тебе нужно сравнить N^2/2 подстрочек заданной строки с K заданными строчками.
Если заданные строчки организованы в таблицу по алфавиту (константная сложность), то сравнение N^2/2 подстрочек заданной строки - сложность О(N^2), а не линейная...
Re: ногами не бить - я не программист :)
Date: 2005-12-01 05:50 am (UTC)Тогда да, сложность задачи линейна по N - проверка каждой подстроки (всего их К^2/2) на идентичность с одной из N заданных строк - О(N*К^2/2).
(скромное мнение)
Date: 2005-12-01 06:50 am (UTC)отсев заведомо непригодных вариантов - взаимное сравнение "сэт перых букв подстрок" с набором букв строки - и подстроки просеятся если там хоть что-то есть
а потом тупой поиск подстроки в строке, в идеальном случае разбить на вменяемые подмножества и распараллелить...
no subject
Date: 2005-12-01 06:59 am (UTC)Препроцессинг: хэщируем строки, таким образом, доступ к нужной строке будет О(1).
Определяем множество (это может быть связный список, это не важно) кандидатов, в котором будут сидеть строки (или их инжекс в хэше) и для каждой строки еще поле "проверено до Х буквы". Сейчас это множество пусто.
Для каждой буквы из инпута проделываем следущее: для каждого кандидата из множества сравниваем букву из инпута с Х+1 (где Х - "проверено до ... буквы") буквой кандидата. Если эти буквы разные, выкидываем кандидата из списка, если одинаковые инкрементируем его "проверено до ... буквы". Далее, берем из хэша все слова начинающиеся на эту букву (ту, что считали из инпута) и добавляем в список кандидатов, устанавливая "проверено до ... буквы" в 1.
Алгоритм останавливается, если "проверено до ... буквы" для некоторого кандидата будет равно количеству букв в нем. В этом случае ответом будет этот самый кандидат. Если такового не нашлось, а инпут кончился - значит не судьба...
В нормальном случае сложность такого алгоритма О(длина инпута).
no subject
Date: 2005-12-01 07:04 am (UTC)Понятно, что одна и та же строка может быть в списке кандидатов несколько раз с разным "проверено до ... буквы".
no subject
Date: 2005-12-02 02:12 am (UTC)Следующий вариант вырисовывается.
Предварительно по множеству строк строим "дерево чтения строк". Построение начинается с помечнного пустым символом корня дерева. К нему добавляются дочерние вершины, помеченные первыми буквами строк данного множества. Затем к каждой из этих вершин - дочерние вершины, помеченные вторыми буквами слов, начинающихся с соответствующей буквы. И так далее. Таким образом, продвигаясь вглубь по ветвям дерева мы будем читать слова данного множества.
Причем при построении "дерева" часть строк из исходного множества может отпасть. А именно те из них, которые начинаются со вхождения более короткой строки из данного множества. Например, если во множестве строк имеются строки "eric" и "ericson", то вторую строку можно очевидно не принимать в расчет (поскольку уж если большая подстрока встречается во "входной строке", то уж меньшая и подавно) и не включать в "дерево чтения".
Далее нам понадобится множество для хранения указателей на текущие анализируемые вершины дерева. Изначально оно пусто.
Теперь для каждого символа из "входной строки" выполняем:
(фактически указатель на вершину дерева будет нам говорить о том, что мы смогли начиная с некоторой позиции "входной строки" прочитать последовательность букв, ведущую от корня "дерева строк" к указанной вершине дерева)
Если мы проанализировали все символы "входной строки", значит ни одна из заданного множества строк не является подстрокой "входной строки".
Чтобы оценить трудозатраты алгоритма, заметим, что для каждого символа "входной строки" мы должны проверить каждый указатель вершины из множества. Значит нам нужно оценить верхнюю границу мощности множества указателей на текущие вершины "дерева чтения строк". Поскольку на каждом шаге :
- мы можем добавить ко множеству указателей один единственный указатель (на текущую букву "входной строки" в корне "дерева чтения строк")
- каждый ранее введенный указатель продвигается на один уровень вглубь "дерева чтения" или исчезает (в случае если нет соответствующих букв для продвижения)
то максимально возможная мощность множества указателей равна глубине дерева. Итого, в худшем случае нам придется выполнить N*M операций проверки-перемещения указателей. Где N - длина "входной строки", а M - глубина "дерева чтения", или максимальная длина строки из заданного множества.no subject
Date: 2005-12-02 02:31 am (UTC)Ну вот, вы тоже изобрели trie, поздравляю! :)
no subject
Date: 2005-12-02 03:02 pm (UTC)no subject
Date: 2005-12-02 08:59 am (UTC)И - как следствие - архивирование (за названием к Кнуту), где дерево строится так, что наиболее частые символы висят ближе к корню, т.е. кодируются меньшим количеством бит. Только у твоего дерева алфавит больше.
no subject
Date: 2005-12-02 03:00 pm (UTC)Но главное, ты, по-моему запутался в двух алфавитах :-) У Хаффмана (http://algolist.manual.ru/compress/standard/huffman.php), про которого ты судя по всему и вспомнил, есть два алфавита: кодируемый {a..z} (то что ты называешь символами, "висящими ближе к корню") и кодирующий {0,1} (то что ты называешь "алфавитом"). Да, в результате алгоритма построения бинарного словаря по Хаффману получается trie для кодирующего алфавита {0, 1}. Фактически, мы получаем частный случай trie - бинарное дерево. А символами кодируемого алфавита {a-z} помечаются только листья. Тогда, читая закодированный (сжатый поток) посимвольно (побитно) и перемещаясь по trie (бинарному дереву), мы сможем прочесть закодированное сообщение в алфавите {a..z}, если будем запоминать последовательность посещенных листьев. А тот факт, что мы строим trie таким специальным образом, что чаше встречающиеся символы кодируемого алфавита подвешены на конце более коротких "веточек", позволяет нам закодировать исходное сообщение в алфавите {a..z} более компактным образом в алфавите {0,1}.
no subject
Date: 2005-12-02 03:22 pm (UTC)Я разницу вижу, я просто и сходство заметил :-)
no subject
Date: 2005-12-02 05:53 am (UTC)Спасибо за ссылки.
no subject
Date: 2005-12-02 09:00 am (UTC)no subject
Date: 2005-12-02 09:04 am (UTC)это называется Access Point Name. Когда ты с телефона пользуешься каким-то интернет-сервисом, эта штука записывается в call description record, а мне её надо искать в таблице и извлекать всякие данные, которые с этим адресом связаны.