Среда, 20.01.2021, 22:59
Информатика и ИКТ
Приветствую Вас Гость | RSS
Главная Регистрация Вход
Меню сайта

Yandex_tech

Хабр-news

mail_news

Rambler

Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0

oszone.net

IT-N-образование

Главная » 2020 » Декабрь » 24 » Алгоритм Укконена: от простого к сложному
19:14
Алгоритм Укконена: от простого к сложному

Алгоритм Укконена: от простого к сложному

Изучая курс Алгоритмы на строках столкнулся с задачей о построении суффиксного дерева. Перейдя по ссылке на дополнительные материалы наткнулся на рекомендацию "просмотреть этот замечательный комментарий на Stack Overflow". Изучив и реализовав по приведённому вольному описанию алгоритм Укконена решил поделиться переводом.

Ниже приводится попытка описания алгоритма Укконена; сначала показав, как он работает на простой строке (т.е. строка не содержит повторяющихся символов), постепенно расширяясь до полного алгоритма.

Несколько предварительных утверждений:

  1. То, что мы строим - это в основе похоже на префиксное дерево. Это корневая вершина, чьи ребра выходят из неё в новые вершины, и последующие ребра выходят из них и так далее

  2. Но, в отличие от префиксного дерева, метки ребра - не одиночные символы, у каждого ребра метка это пара чисел [от, до] - указатели на позиции в тексте. В таком случае, каждое ребро содержит строку произвольной длины, но занимает только O(1) памяти (два указателя)

Базовый принцип

Сначала автор хочет продемонстрировать как создать суффиксное дерево чрезвычайно простой строки, строки без повторяющихся символов:

Просмотров: 32 | Добавил: niko | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Поиск

Календарь
«  Декабрь 2020  »
ПнВтСрЧтПтСбВс
 123456
78910111213
14151617181920
21222324252627
28293031

Форма входа

nixp.ru

OpenNet

Новые программы

SLO.ru

Погода
Яндекс.Погода

Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz

  • Архив записей

    Copyright MyCorp © 2021