דָּוִדdavidov777 (daviddavidov777) wrote,
דָּוִדdavidov777
daviddavidov777

Creative English

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

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто :)
Итак, чем же не устраивает нас дерево? Во-первых, это конечно то, что из за необходимости хранить ссылки на детей, родителя и т.п. размер используемой памяти в этом случае заметно больше, чем если эти ссылки не хранить. Во-вторых, если аллоцировать память под данные каким-нибудь стандартным аллокатором, то их «раскидает по разным углам», в результате обход дерева будет предполагать большое количество переходов в памяти, что плохо сказывается на на работе кэша памяти. Конечно есть уловки, которые позволяют эту проблему подавить: надо размещать узлы дерева в массиве, а вместо указателей использовать индекс в массиве. Тогда дерево будет представляться цельным куском памяти.

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

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


Недавно в интернете наткнулся на интересное предложеие Creative English по изучению иностранного языка.Я считаю что сейчас без иностранного никда.

К тому же там можно сдать Экзамен IELTS недорого.Обращайтесь!
Tags: Экзамен IELTS
Subscribe

  • apple macbook air 13

    То ли весна, то ли упоминание о неделе женщин на Хабре заставили меня задуматься о том, какими женщинами были бы языки программирования. Поиск по…

  • New age.................

    Заниматься еще больше торговлей!Понять куда пойдет тренд. Учиться , как можно больше задавать как можно больше вопросов.не терять время на всякую…

  • music

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments