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

[Olej]

Новый интерес...

Свободно скачать книгу (и оно того стоит!) можете здесь

Здесь скачать уже невозможно
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]

Находим вот такое издание ... которое можно читать на этом ресурсе онлайн (но неудобно):

Алгоритмы обработки строк [Электронный ресурс] / Окулов С.М. - М. : БИНОМ, 2012.
Авторы Окулов С.М.
Издательство БИНОМ
Год издания 2012

Тоже ... не находим
Но зато замечательно находим здесь: Окулов С.М. Алгоритмы обработки строк,pdf

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

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

[Olej]

Простое суффиксное дерево

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]

Новый интерес...

Вот теперь, возобновив то, что было сделано 6 лет назад ... начинаем проверку и подбиваем бабки итогов...

[Olej]

Вот теперь, возобновив то, что было сделано 6 лет назад ... начинаем проверку и подбиваем бабки итогов...

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

Пока я предполагаю использовать в качестве эталонов для быстрых тестов неколько стихотворений моего любимого поэта Иосифа Бродского.

[Olej]

алгоритма Укконена

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

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

[Olej]

Для сравнения 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

[Olej]

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

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

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.

[Olej]

Да и не удивительно, поотому что это могло бы работать не с char*/string, а с wchar_t/wstring.

Тем не менее, как бы оно ои было, к этой точке всё что было сделано в 2017г. - работает ОК, так как оно работало в 2017г.

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

[Olej]

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

Выглядит это как-то так:

Снимок экрана от 2023-01-20 16-12-50.png (147.49 КБ) 123 просмотра

Что примечательно, и что видно по картинке, что этот ресурс работает с русскоязычными входными текстами
О чём и будет главный разговор в этой теме.

Вот ещё одно завершённое минимальное суффиксное дерево для русскоязычного текста:

Снимок экрана от 2023-01-20 19-40-49.png (147.88 КБ) 120 просмотров