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

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

Модератор: Olej

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

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

Непрочитанное сообщение Olej » 19 дек 2017, 00:11

Совершенно новая алгоритмическая техника.
Позволяющая решить многие не решаемые до этих пор задачи контекстного поиска, сравнений текстов, нахождения общих вхождений в текстах и т.д.
Начинать перечисление источников нужно с книги: Гасфилд Д. "Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология":
Изображение
Издательство: Невский диалект
ISBN: 5-7940-0103-8; 5-94517-321-9
Год: 2003
Страниц: 654
Свободно скачать книгу (и оно того стоит!) можете здесь
12.06 МБ

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

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

Непрочитанное сообщение Olej » 19 дек 2017, 00:22

Olej писал(а):Начинать перечисление источников
Интересно и полезно:

Простое суффиксное дерево
18 мая 2015 в 18:03
Построение суффиксного дерева за линейное время
Лекция № 1 курса
«Алгоритмы для Интернета»
Юрий Лифшиц∗
28 сентября 2006 г.
Будем называть текстом T строку из n символов t1 . . . tn, а каждое окончание текста ti . . . tn — его суффиксом.
Суффиксное дерево (ST) — это способ представления текста. Неформально говоря, чтобы построить ST для текста T = t1 . . . tn, нужно приписать специальный символ $ в конец текста, взять все n + 1 суффиксов, подвесить их за начала и склеить все ветки, идущие по одинаковым буквам. В каждом листе записывается номер суффикса, заканчивающегося в этом листе. Номером суффикса является индекс его
начала в тексте T.
Суффиксное дерево. Алгоритм Укконена
редактировано: 4 Feb 2013 0
Суффиксные деревья

Второй курс, осенний 2017/18
Конспект лекций по алгоритмам
Собрано 23 октября 2017 г. в 19:17
Глава 3. Деревья суффиксов

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

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

Непрочитанное сообщение Olej » 20 дек 2017, 00:20

Взяв за основу одну из опубликованных реализаций алгоритма Укконена построения суффиксного дерева за линейное время O(n), построил такую вот демонстрационную задачу...
На ней, на примерах, хорошо видно структуру того, что представляет из себя суффиксное дерево ... например те строки-тексты, которые используются в вышеприведенных публикациях (потому что так тестирование можно проверить):

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

[olej@dell Ukkonen]$ ./suftest 
> abcabb0
узлов 10 рёбер 9 длиной:
5  5  5  2  2  1  2  1  1  => 24
0[6:1]:0
a[0:2]:ab
    b[5:2]:b0
    c[2:5]:cabb0
b[1:1]:b
    0[6:1]:0
    b[5:2]:b0
    c[2:5]:cabb0
c[2:5]:cabb0
> abcabdabcabdab$
узлов 24 рёбер 23 длиной:
7  7  7  2  7  1  7  7  6  1  6  1  6  1  3  1  3  1  3  1  1  1  1  => 81
$[14:1]:$
a[0:2]:ab
    $[14:1]:$
    c[2:6]:cabdab
	$[14:1]:$
	c[8:7]:cabdab$
    d[5:3]:dab
	$[14:1]:$
	c[8:7]:cabdab$
b[1:1]:b
    $[14:1]:$
    c[2:6]:cabdab
	$[14:1]:$
	c[8:7]:cabdab$
    d[5:3]:dab
	$[14:1]:$
	c[8:7]:cabdab$
c[2:6]:cabdab
    $[14:1]:$
    c[8:7]:cabdab$
d[5:3]:dab
    $[14:1]:$
    c[8:7]:cabdab$
> ^C

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

[olej@dell Ukkonen]$ ./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 : 
0[6:1]:0
a[0:2]:ab
    b[5:2]:b0
    c[2:5]:cabb0
b[1:1]:b
    0[6:1]:0
    b[5:2]:b0
    c[2:5]:cabb0
c[2:5]:cabb0
> qababaz$
узлов 12 рёбер 11 длиной:
8  4  4  2  2  2  2  1  2  2  1  => 30
{pos,len,link}: {1:0,8,0} {2:4,4,0} {3:4,4,0} {4:2,2,6} {5:6,2,0} {6:2,2,8} {7:6,2,0} {8:1,1,0} {9:6,2,0} {10:6,2,0} {11:7,1,0} 
0: map size 5 : [$,11] [a,8] [b,6] [q,1] [z,10] 
1: map size 0 : 
2: map size 0 : 
3: map size 0 : 
4: map size 2 : [b,2] [z,5] 
5: map size 0 : 
6: map size 2 : [b,3] [z,7] 
7: map size 0 : 
8: map size 2 : [b,4] [z,9] 
9: map size 0 : 
10: map size 0 : 
11: map size 0 : 
$[7:1]:$
a[1:1]:a
    b[2:2]:ba
	b[4:4]:baz$
	z[6:2]:z$
    z[6:2]:z$
b[2:2]:ba
    b[4:4]:baz$
    z[6:2]:z$
q[0:8]:qababaz$
z[6:2]:z$
> ^C
Вложения
stu.tgz
(4.56 КБ) 101 скачивание

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

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

Непрочитанное сообщение Olej » 20 дек 2017, 23:32

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

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

[olej@dell Ukkonen]$ ./ukkonen 
> xabxa$
{pos,len,link}: {1:2,4,0} {2:2,4,0} {3:2,4,0} {4:0,2,6} {5:5,1,0} {6:1,1,0} {7:5,1,0} {8:5,1,0} 
0: map size 4 : [$,8] [a,6] [b,3] [x,4] 
1: map size 0 : 
2: map size 0 : 
3: map size 0 : 
4: map size 2 : [$,5] [b,1] 
5: map size 0 : 
6: map size 2 : [$,7] [b,2] 
7: map size 0 : 
8: map size 0 : 
узлов 9 рёбер 8 длиной:
4  4  4  2  1  1  1  1  => 18
<8>$[5:1]:$
<6>a[1:1]:a
	<7>$[5:1]:$
	<2>b[2:4]:bxa$
<3>b[2:4]:bxa$
<4>x[0:2]:xa
	<5>$[5:1]:$
	<1>b[2:4]:bxa$
> ^C

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

[olej@dell Ukkonen]$ ./weiner 
> xabxa$
{pos,len,par}: {1:0,1,0} {2:6,1,1} {3:6,1,6} {4:6,1,8} {5:6,4,1} {6:5,1,1} {7:6,4,6} {8:5,2,1} {9:6,4,8} 
1: map size 4 : [$,2] [a,6] [b,5] [x,8] 
2: map size 0 : 
3: map size 0 : 
4: map size 0 : 
5: map size 0 : 
6: map size 2 : [$,3] [b,7] 
7: map size 0 : 
8: map size 2 : [$,4] [b,9] 
9: map size 0 : 
узлов 9 рёбер 8 длиной:
1  1  1  4  1  4  2  4  => 18
<2>$[5:1]:$
<6>a[4:1]:a
	<3>$[5:1]:$
	<7>b[2:4]:bxa$
<5>b[2:4]:bxa$
<8>x[3:2]:xa
	<4>$[5:1]:$
	<9>b[2:4]:bxa$
> ^C
Видно, что порядок формирования дерева суффиксов в 2-х методах совершенно разный, узлы дерева перенумерованы по-разному, но конечный вид дерева-графа совпадает.
Это и понятно, потому что сам цикл формирования дерева в Укконена записан так (побуквенно слева-направо):

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

      for( unsigned i = 0; i < sinp.size(); i++ )
         add_letter( sinp[ i ] );
А у Вейнера (побуквенно справа-налево):

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

      for( int i = s.size() - 1; i >= 0; i-- )
         extend( i );
Вложения
sftree.tgz
(5.05 КБ) 102 скачивания

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

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

Непрочитанное сообщение Olej » 23 дек 2017, 14:43

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

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

[olej@dell dskr5]$ g++ -Wall -std=c++11 main.cpp SuffTree.cpp -o dskr

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

[olej@dell dskr5]$ ./dskr
ab
abcabdabcabdab
1
4
7
10
13
^C
[olej@dell dskr5]$ ./dskr
aw
awyawxawxz
1
4
7
^C
[olej@dell dskr5]$ ./dskr
xa
xabxa
1
4
^C
P.S. Относительно статистики совпадений (это термин!) см. очень кратко здесь Свободные материалы преподавателей кафедры 806 МАИ
Вложения
dskr.tgz
(1.48 КБ) 91 скачивание

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

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

Непрочитанное сообщение Olej » 24 дек 2017, 16:54

Olej писал(а): P.S. Относительно статистики совпадений (это термин!) см. очень кратко здесь Свободные материалы преподавателей кафедры 806 МАИ
Собственно, относительно статистики совпадений обстоятельно читаем всё в той же книге, с которой всё началось:
Изображение
стр.171 (страницы по переводному изданию):
7.8.1. Статистика совпадений: те же границы и меньшая память.
стр.171 - стр.173

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

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

Непрочитанное сообщение Olej » 24 дек 2017, 17:23

На вот таком вот занятном ресурсе:
КОНСУЛЬТАНТ СТУДЕНТА
Электронная библиотека медицинского колледжа
Находим вот такое издание ... которое можно читать на этом ресурсе онлайн (но неудобно):
Алгоритмы обработки строк [Электронный ресурс] / Окулов С.М. - М. : БИНОМ, 2012.
Авторы Окулов С.М.
Издательство БИНОМ
Год издания 2012
Для начального или поверхностного ознакомления с техникой суффиксных деревьев это может быть удобнее.

А скачать книгу в PDF можете совершенно свободно здесь:
Изображение

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

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

Непрочитанное сообщение Olej » 24 дек 2017, 20:39

Olej писал(а):Совершенно новая алгоритмическая техника.
Позволяющая решить многие не решаемые до этих пор задачи контекстного поиска, сравнений текстов, нахождения общих вхождений в текстах и т.д.
Подобные техники - это революция в технологиях контекстного поиска и других родственных задач!
Из книги Гасфилда (см. выше)...
- (стр.158)
Такова задача о наибольшей общей подстроке, рассматриваемая в п.7.4. Кнут предположил, что в ней линейный по времени алгоритм невозможен [24, 278], а такой алгоритм прямо получается при использовании суффиксных деревьев.
- (стр.161)
Одно, несколько патологическое применение, этой задачи о подстроке можно найти в упрощённом варианте процедуры, которая используется в США для идентификации останков военнослужащих. Собираются митохондриальные ДНК от живых военнослужащих, и по небольшому участку секвентируется ДНК от каждого человека. ... Этот интервал используется как "почти уникальный" идентификатор. Если требуется опознать убитого военнослужащего, митохондриальную ДНК извлекают из его останков. После выделения и расшифровки того же участка строку из останков можно сравнить с общей базой данных военнослужащих (или более узкой базой данных строк для пропавших военнослужащих).
Из книги (всей целиком), кстати, становится понятно, почему разнообразные задачи поиска и идентификации строк так актуальны в биологии и медицине, ещё более чем в ИТ.

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

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

Непрочитанное сообщение Olej » 27 дек 2017, 17:54

Olej писал(а): Подобные техники - это революция в технологиях контекстного поиска и других родственных задач!
Варианты алгоритмов Укконена и Вейнера (программы по Укконену имеют в имени суффикс u, а по Вейнеру, соответственно - w):
- обернутые в классы C++;
- в тех же классах реализован метод

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

vector<int> find_pos( const string& pattern );

- это поиск уже в построенном суффиксном дереве всех вхождений паттерна.

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

$ ls 
findu.cc  Makefile  stu.h   stw.h          suffix.2.hist  suffix.4.hist  suftstw.cc  weiner.cc
findw.cc  stu.cc    stw.cc  suffix.1.hist  suffix.3.hist  suftstu.cc     ukkonen.cc
find* - это именно приложения на тестирование поиска вхождений:

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

[olej@dell Ukkonen]$ ./findu
> xyabczxabcdwabcdr$
? a
xyabczxabcdwabcdr$ <- a - found in position: 12 7 2 
? abcd
xyabczxabcdwabcdr$ <- abcd - found in position: 12 7 
? cd
xyabczxabcdwabcdr$ <- cd - found in position: 14 9 
? $
xyabczxabcdwabcdr$ <- $ - found in position: 17 
? zx
xyabczxabcdwabcdr$ <- zx - found in position: 5 
? r
xyabczxabcdwabcdr$ <- r - found in position: 16 
? xy
xyabczxabcdwabcdr$ <- xy - found in position: 0 
? zy
xyabczxabcdwabcdr$ <- zy - not found!
? bcdx
xyabczxabcdwabcdr$ <- bcdx - not found!
?         
> abcabdabcabdab$
? abd
abcabdabcabdab$ <- abd - found in position: 9 3 
? a
abcabdabcabdab$ <- a - found in position: 12 6 0 9 3 
? cabdab
abcabdabcabdab$ <- cabdab - found in position: 8 2 
? 
> xabxac$
? a
xabxac$ <- a - found in position: 1 4 
? xa
xabxac$ <- xa - found in position: 0 3 
? 
> ^C

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

[olej@dell Ukkonen]$ ./findw
> xyabczxabcdwabcdr$
? a
xyabczxabcdwabcdr$ <- a - found in position: 12 7 2 
? abcd
xyabczxabcdwabcdr$ <- abcd - found in position: 12 7 
? cd
xyabczxabcdwabcdr$ <- cd - found in position: 14 9 
? r
xyabczxabcdwabcdr$ <- r - found in position: 16 
? 
> abcabdabcabdab$
? a
abcabdabcabdab$ <- a - found in position: 12 6 0 9 3 
? abd
abcabdabcabdab$ <- abd - found in position: 9 3 
? cabdab
abcabdabcabdab$ <- cabdab - found in position: 8 2 
? ^C
(при запуске find* с параметром 1 или 2 - это будет уровень отладочного вывода, который покажет и структуру построенного дерева)
Вложения
sftree.tgz
(11.92 КБ) 92 скачивания

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

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

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

Olej писал(а): Варианты алгоритмов Укконена и Вейнера (программы по Укконену имеют в имени суффикс u, а по Вейнеру, соответственно - w):
- обернутые в классы C++;
В принципе, то что здесь показано - вполне пригодно для практического использования ... за исключением одного:
- хэш-таблицы и массивы, используемые в обоих алгоритмах, имеют большие фиксированные размерности

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

...
   static const int maxn = 1e4;
   char s[ maxn ];
...
   int len[ maxn ], spos[ maxn ], link[ maxn ];
   map< char, int > to[ maxn ];
...

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

...
   static const int MAXLEN = 10000;
   int path[ MAXLEN ];
   map< char,int > to[ MAXLEN ], link[ MAXLEN ];
   int sz;
public:
   int pos[ MAXLEN ], len[ MAXLEN ], par[ MAXLEN ];
...
- в принципе, по хорошему, это нужно делать динамически, переразмещением...
- например, vector вместо массива + удвоение его размера при невозможности уместиться ... что-то типа:

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

      try {
         len.at( addr ) = ...;
      }
      catch( out_of_range& e ) {                       // выход за предел массива
         len.resize( addr * 2 );
      }
Мне было этим в облом заниматься, хотя всё, в принципе, понятно...
Возможно, если будет время и желание, я код на соответствие такой динамике и переделаю... ;-)

Ответить

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

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

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