воскресенье, 10 февраля 2013 г.

как пронумеровать массив по порядку php

Рассмотрим пример. Исходная строка «mississippi». Допустим, приходит к нам образец «sip». Простейший способ узнать, встречается ли образец в тексте, используя суффиксный массив, это взять первый символ образца и (массив у нас отсортирован) найти диапазон с суффиксами, начинающимися на такую же букву. Так как все элементы в диапазоне отсортированы, а первые символы одинаковые, то оставшиеся после отбрасывания первого символа суффиксы тоже отсортированы. А значит, можно повторять процедуру сужения диапазона поиска до получения либо пустого диапазона, либо успешного нахождения всех символов образца. Очевидно, что таким образом за O(|X|log|A|) операций мы получим ответ.

Простейший поиск подстроки

Также важное понятие ранг суффикса то место, которое займет суффикс при сортировке, то есть его позиция в суффиксном массиве. Это взаимнообратные величины. Мы не будем их особо как-то различать, так как имея один массив, получить другой можно за O(N), так что можно всегда иметь под рукой оба.

В 1989 году Манбер и Майерс опубликовали статью, в которой описали такую структуру данных, как суффиксный массив, и как ее применять для поиска подстрок. Суффиксный массив это массив лексикографически отсортированных суффиксов строк (если терминология незнакома, то можно глянуть раздел «постановка задачи» в статье). Вообще говоря, хранить сами суффиксы смысла нет, достаточно хранить позицию начала данного суффикса, но определение массива так легче воспринимается. Вот пример для строки «mississippi»:

Суффиксный массив

Можно экономней расходовать память, помещая в некий динамически-изменяемый массив (вектор) только непустые ссылки, но тогда уже проверка наличия соответствующего ребенка узла за O(1) становится весьма сомнительной. Если хранить ссылки в отсортированном виде, то O(log(размер алфавита)). Можно попробовать поиграть с хэш-таблицами, но это будет иметь смысл только для сверхбольших алфавитов, и к тому же вводится еще один уровень косвенности. Да и строить такие деревья уже не O(n). В общем, в любом случае надо будет идти на какой-то компромисс между памятью и производительностью.

Ну это общие проблемы для всех деревьев. А что там с пресловутой алфавитной зависимостью? Посмотрим на практическую реализацию суффиксного дерева (если вы не сталкивались с ним, то для понимания сути проблемы это не важно). В каждом узле такого дерева могут быть ссылки на детей в количестве от 1 (например для терминальной вершины без ветвления) и до размера алфавита. Вот и возникает вопрос как хранить эти ссылки. Можно, например, в каждом узле держать массив ссылок размером с алфавит. Работать это будет быстро узнать, есть ли соответствующий ребенок в данном узле можно за O(1). Но в большинстве ячеек массива будут храниться нулевые ссылки, а память на эти ячейки уйдет. Для небольших алфавитов (например, нуклеотиды в ДНК) черт с ним, но представьте себе китайские иероглифы? В принципе далеко ходить не надо: даже не case-sensitive русский алфавит заставляет призадуматься, а хотим ли мы столько пустых данных иметь.

Итак, чем же не устраивает нас дерево? Во-первых, это конечно то, что из за необходимости хранить ссылки на детей, родителя и т.п. размер используемой памяти в этом случае заметно больше, чем если эти ссылки не хранить. Во-вторых, если аллоцировать память под данные каким-нибудь стандартным аллокатором, то их «раскидает по разным углам», в результате обход дерева будет предполагать большое количество переходов в памяти, что плохо сказывается на на работе кэша памяти. Конечно есть уловки, которые позволяют эту проблему подавить: надо размещать узлы дерева в массиве, а вместо указателей использовать индекс в массиве. Тогда дерево будет представляться цельным куском памяти.

Не все деревья одинаково полезны

Применения суффиксного массива

Материал статьи предполагает знание понятий строки, а также знание того, как работает . Надо также представлять, что такое и , а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке . Ну, в общем, вас предупредили: никто не говорил, что будет просто.

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как . На Хабре уже описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы Xi в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман . О том как его строить и как использовать и пойдет в этой статье.

Суффиксный массив удобная замена суффиксного дерева

Суффиксный массив удобная замена суффиксного дерева / Хабрахабр

Комментариев нет:

Отправить комментарий