ITMO University
“Programming Technologies” Department



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Биоинформатика
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



    / Visualizers / Ukkonen Algorithm (версия для печати)


Ukkonen Algorithm



© 2004 I.R. Akhmetov

Saint-Petersburg State University of Information Technologies, Mechanics and Optics

Project documentation (in Russian)
Source code
Visualizer (online)

Annotation

Suffix tree is a data structure, that allows to present a string in a way, that is very useful in many tasks of string processing. In particular, this data structure is widely used in computational biology presently. This has become possible thanks to the algoriths that build the suffix tree for the string of length n in the O(n) time.

This work contains an implementation of the algorithm, which was recently (in 1995) suggested by E. Ukkonen. It has certain advantages over the earlier suggested by P. Weiner and E.M. McCreight algorithms. For the sake of simplicity a version of the algorithm that works in the O(n2) time is implemented. It reveals the essense of the algorithm more completely and with several modifications can be turned into a version that works in the O(n) time.

The implementation of the algorithm uses the Vizi technology and is a Java-applet, which can demonstrate the algorithm step-by-step on different strings. This technology uses an automata-based approach to visualizer development. The documentation includes algorithm details, description of the applet and source codes of the visualizer.




© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com