суффиксные деревья и поиск в строке

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 16:10

Новый интерес...
Olej писал(а):
19 дек 2017, 00:11
Свободно скачать книгу (и оно того стоит!) можете здесь
Здесь скачать уже невозможно :!:
https://www.books.ru/books/stroki-derev ... iya-83670/
Д. Гасфилд Иосиф Владимирович Романовский
Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология
Код 550854
ISBN: 978-5-94157-321-6 январь 2008 BHV-СПб
Зато можно вполне свободно скачать здесь - Строки, деревья и последовательности в алгоритмах:
Строки, деревья и последовательности в алгоритмах
Д. Гасфилд
Книга Д. Гасфилда написана на основе лекций, которые автор читает в Университете Дэвиса, Калифорния. В ней, по-видимому, впервые подробно излагается круг математических вопросов, связанных с применениями математики и информатики в задачах вычислительной молекулярной биологии
Количество страниц: 655

Код: Выделить всё

olej@R420:~/2023/suffix_tree$ 
olej@R420:~/2023/suffix_tree$ ls -l \[D._Gasfild\]_Stroki,_derevya_i_posledovatelnosti_v\(libcats.org\).djvu 
-rw-rw-r-- 1 olej olej 12661494 янв 19 15:38 '[D._Gasfild]_Stroki,_derevya_i_posledovatelnosti_v(libcats.org).djvu'
Или здесь торент: Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 16:20

Olej писал(а):
24 дек 2017, 17:23
Находим вот такое издание ... которое можно читать на этом ресурсе онлайн (но неудобно):
Алгоритмы обработки строк [Электронный ресурс] / Окулов С.М. - М. : БИНОМ, 2012.
Авторы Окулов С.М.
Издательство БИНОМ
Год издания 2012
Тоже ... не находим ;-)
Но зато замечательно находим здесь: Окулов С.М. Алгоритмы обработки строк,pdf

Код: Выделить всё

olej@R420:~/2023/suffix_tree$ ls -l Окулов,\ С.М.\ -\ Алгоритмы\ обработки\ строк.pdf 
-rw-rw-r-- 1 olej olej 4897171 янв 19 15:20 'Окулов, С.М. - Алгоритмы обработки строк.pdf'

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 20:53

Простое суффиксное дерево
18 мая 2015
Суффиксное дерево – мощная структура, позволяющая неожиданно эффективно решать мириады сложных поисковых задач на неструктурированных массивах данных. К сожалению, известные алгоритмы построения суффиксного дерева (главным образом алгоритм, предложенный Эско Укконеном (Esko Ukkonen)) достаточно сложны для понимания и трудоёмки в реализации. Лишь относительно недавно, в 2011 году, стараниями Дэни Бреслауэра (Dany Breslauer) и Джузеппе Италиано (Giuseppe Italiano) был придуман сравнительно несложный метод построения, который фактически является упрощённым вариантом алгоритма Питера Вейнера (Peter Weiner) – человека, придумавшего суффиксные деревья в 1973 году.
Построение суффиксного дерева за линейное время
Лекция No 1 курса
Юрий Лифшиц
28 сентября 2006 г.
Суффиксные деревья
Более эффективный способ решения этой задачи использует построение суффиксного дерева, представляющего текст, где производится поиск. Описание этой структуры данных было приведено в предыдущем разделе, ниже мы повторим его основные моменты. Затем последует описание алгоритма суффиксного дерева Мак-Крейта (McCreight), и наконец, будет рассмотрен способ использования этого дерева для данной задачи.
Суффиксное дерево. Алгоритм Укконена
Этот алгоритм строит суффиксное дерево для данной строки длины n за время O (n \log k), где k — размер алфавита (если его считать константой, то асимптотика получается O (n)).
Входными данными для алгоритма являются строка s и её длина n, которые передаются в виде глобальных переменных.

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 21:11

Olej писал(а):
19 янв 2023, 16:10
Новый интерес...
Вот теперь, возобновив то, что было сделано 6 лет назад ... начинаем проверку и подбиваем бабки итогов...

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 21:23

Olej писал(а):
19 янв 2023, 21:11
Вот теперь, возобновив то, что было сделано 6 лет назад ... начинаем проверку и подбиваем бабки итогов...
Как я понимаю (как я понимаю ) для тестирования этого предмета надо иметь достаточно объёмный исходный текст... Для более коротких текстов лучше применять, даже многократно, алгоритмы оптимизированного поиска контекста, см. Н.Вирта.

Пока я предполагаю использовать в качестве эталонов для быстрых тестов неколько стихотворений моего любимого поэта Иосифа Бродского.
Вложения
Конец_прекрасной_эпохи.txt
(4.99 КБ) 39 скачиваний
На_независимость_Украины.txt
(3.07 КБ) 35 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 21:41

Olej писал(а):
20 дек 2017, 00:20
алгоритма Укконена

Код: Выделить всё

olej@R420:~/2023/suffix_tree/stu$ pwd
/home/olej/2023/suffix_tree/stu

Код: Выделить всё

olej@R420:~/2023/suffix_tree/stu$ make
g++ -Wall -std=c++11 -O3  suftest.cc stu.cc -o suftest

Код: Выделить всё

olej@R420:~/2023/suffix_tree/stu$ ./suftest
> abcabb0
узлов 10 рёбер 9 длиной:
5  5  5  2  2  1  2  1  1  => 24
{pos,len,link}: {1:2,5,0} {2:2,5,0} {3:2,5,0} {4:0,2,6} {5:5,2,0} {6:1,1,0} {7:5,2,0} {8:6,1,0} {9:6,1,0}
0: map size 4 : [0,9] [a,4] [b,6] [c,3]
1: map size 0 :
2: map size 0 :
3: map size 0 :
4: map size 2 : [b,5] [c,1]
5: map size 0 :
6: map size 3 : [0,8] [b,7] [c,2]
7: map size 0 :
8: map size 0 :
9: map size 0 :
<9>0[6:1]:0
<4>a[0:2]:ab
    <5>b[5:2]:b0
    <1>c[2:5]:cabb0
<6>b[1:1]:b
    <8>0[6:1]:0
    <7>b[5:2]:b0
    <2>c[2:5]:cabb0
<3>c[2:5]:cabb0
> ^C
Вложения
stu.cc
(1.28 КБ) 39 скачиваний
stu.h
(1.66 КБ) 37 скачиваний
suftest.cc
(465 байт) 39 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 22:38

Olej писал(а):
20 дек 2017, 23:32
Для сравнения 2 широко обсуждаемых алгоритма построения суффиксного дерева за линейное время O(n): 1-й это Укконен (первоисточник указан), а 2-й - это упрощённый вариант алгоритма Питера Вейнера

Код: Выделить всё

olej@R420:~/2023/suffix_tree/sftree$ pwd
/home/olej/2023/suffix_tree/sftree

Код: Выделить всё

olej@R420:~/2023/suffix_tree/sftree$ make
g++ -Wall -std=c++11 -O3  ukkonen.cc -o ukkonen
g++ -Wall -std=c++11 -O3  weiner.cc -o weiner

Код: Выделить всё

olej@R420:~/2023/suffix_tree/sftree$ ./ukkonen
> abcabb0
{pos,len,linkss}: {1:2,5,0} {2:2,5,0} {3:2,5,0} {4:0,2,6} {5:5,2,0} {6:1,1,0} {7:5,2,0} {8:6,1,0} {9:6,1,0}
0: map size 4 : [0,9] [a,4] [b,6] [c,3]
1: map size 0 :
2: map size 0 :
3: map size 0 :
4: map size 2 : [b,5] [c,1]
5: map size 0 :
6: map size 3 : [0,8] [b,7] [c,2]
7: map size 0 :
8: map size 0 :
9: map size 0 :
узлов 10 рёбер 9 длиной:
5  5  5  2  2  1  2  1  1  => 24
<9>0[6:1]:0
<4>a[0:2]:ab
    <5>b[5:2]:b0
    <1>c[2:5]:cabb0
<6>b[1:1]:b
    <8>0[6:1]:0
    <7>b[5:2]:b0
    <2>c[2:5]:cabb0
<3>c[2:5]:cabb0
> ^C

Код: Выделить всё

olej@R420:~/2023/suffix_tree/sftree$ ./weiner
> abcabb0
{pos,len,par}: {1:0,1,0} {2:7,1,1} {3:7,1,4} {4:6,1,1} {5:7,2,4} {6:7,2,9} {7:7,5,1} {8:7,5,4} {9:5,2,1} {10:7,5,9}
1: map size 4 : [0,2] [a,9] [b,4] [c,7]
2: map size 0 :
3: map size 0 :
4: map size 3 : [0,3] [b,5] [c,8]
5: map size 0 :
6: map size 0 :
7: map size 0 :
8: map size 0 :
9: map size 2 : [b,6] [c,10]
10: map size 0 :
узлов 10 рёбер 9 длиной:
1  1  1  2  2  5  5  2  5  => 24
<2>0[6:1]:0
<9>a[3:2]:ab
    <6>b[5:2]:b0
    <10>c[2:5]:cabb0
<4>b[5:1]:b
    <3>0[6:1]:0
    <5>b[5:2]:b0
    <8>c[2:5]:cabb0
<7>c[2:5]:cabb0
> ^C
Вложения
ukkonen.cc
(2.75 КБ) 43 скачивания
weiner.cc
(2.54 КБ) 37 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 19 янв 2023, 23:55

Olej писал(а):
23 дек 2017, 14:43
Вот ещё одна работающая реализация алгоритма Укконена + поиск всех вхождений патерна в строку - от студента (МВТУ Баумана или, может быть, МАИ) который и обратил моё внимание на эту тематику, обратившись за помощью, но затем самостоятельно сделал приводимое решение.

Код: Выделить всё

olej@R420:~/2023/suffix_tree/dskr$ make
g++ -Wall -std=c++11 main.cpp SuffTree.cpp SuffTree.h -o dskr

Код: Выделить всё

olej@R420:~/2023/suffix_tree/dskr$ ls -l dskr
-rwxrwxr-x 1 olej olej 66288 янв 19 22:46 dskr

Код: Выделить всё

olej@R420:~/2023/suffix_tree/dskr$ ./dskr
ab
abcabdabcabdab
1
4
7
10
13
^C

Код: Выделить всё

olej@R420:~/2023/suffix_tree/dskr$ ./dskr
aw
awyawxawxz
1
4
7
^C

Код: Выделить всё

olej@R420:~/2023/suffix_tree/dskr$ ./dskr
xa
xabxa
1
4
^C
Но как легко видеть, на русскоязычных строках это не работает:

Код: Выделить всё

olej@R420:~/2023/suffix_tree/dskr$ ./dskr
ой
гой вай хлой бой
3
5
3
^C
Да и не удивительно, поотому что это могло бы работать не с char*/string, а с wchar_t/wstring.
Вложения
main.cpp
(313 байт) 44 скачивания
SuffTree.cpp
(3.86 КБ) 41 скачивание
SuffTree.h
(655 байт) 39 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 20 янв 2023, 00:01

Olej писал(а):
19 янв 2023, 23:55
Да и не удивительно, поотому что это могло бы работать не с char*/string, а с wchar_t/wstring.
Тем не менее, как бы оно ои было, к этой точке всё что было сделано в 2017г. - работает ОК, так как оно работало в 2017г.

Теперь это предстоит модифицировать так как это представляется мне, а не авторам кодов которые были взяты за основу этих примеров.

Аватара пользователя
Olej
Писатель
Сообщения: 21338
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

суффиксные деревья и поиск в строке

Непрочитанное сообщение Olej » 20 янв 2023, 17:14

Есть шикарная визуализация алгоритма Уконена построения суффиксного дерева, по шагам: Visualization of Ukkonen's Algorithm.

Выглядит это как-то так:
Снимок экрана от 2023-01-20 16-12-50.png
Снимок экрана от 2023-01-20 16-12-50.png (147.49 КБ) 466 просмотров
Что примечательно, и что видно по картинке, что этот ресурс работает с русскоязычными входными текстами :!:
О чём и будет главный разговор в этой теме.

Вот ещё одно завершённое минимальное суффиксное дерево для русскоязычного текста:
Снимок экрана от 2023-01-20 19-40-49.png
Снимок экрана от 2023-01-20 19-40-49.png (147.88 КБ) 463 просмотра

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 7 гостей