Rating@Mail.ru

Форум по операционной системе GNU/Linux и свободному программному обеспечению


Текущее время: 21 май 2018, 13:58

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
Непрочитанное сообщениеДобавлено: 19 дек 2017, 00:11 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Совершенно новая алгоритмическая техника.
Позволяющая решить многие не решаемые до этих пор задачи контекстного поиска, сравнений текстов, нахождения общих вхождений в текстах и т.д.
Начинать перечисление источников нужно с книги: Гасфилд Д. "Строки, деревья и последовательности в алгоритмах. Информатика и вычислительная биология":
Цитата:
Изображение
Издательство: Невский диалект
ISBN: 5-7940-0103-8; 5-94517-321-9
Год: 2003
Страниц: 654

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


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: суффиксные деревья
Непрочитанное сообщениеДобавлено: 19 дек 2017, 00:22 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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. Деревья суффиксов


Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: суффиксные деревья
Непрочитанное сообщениеДобавлено: 20 дек 2017, 00:20 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Взяв за основу одну из опубликованных реализаций алгоритма Укконена построения суффиксного дерева за линейное время 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 КБ]
Скачиваний: 5
Вернуться к началу
 Профиль Отправить личное сообщение  
 
 Заголовок сообщения: Re: суффиксные деревья
Непрочитанное сообщениеДобавлено: 20 дек 2017, 23:32 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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 КБ]
Скачиваний: 5
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 23 дек 2017, 14:43 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Вот ещё одна работающая реализация алгоритма Укконена + поиск всех вхождений патерна в строку - от студента (МВТУ Баумана или, может быть, МАИ) который и обратил моё внимание на эту тематику, обратившись за помощью, но затем самостоятельно сделал приводимое решение.
Цитата:
Необходимо реализовать алгоритм Укконена построения суффиксного дерева за линейное время.
Найти образец в тексте используя статистику совпадений.

Я не вникал внутрь его реализации ... но более-менее обстоятельно проверил тестированием, что работает оно, похоже, исправно:
Код:
[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 КБ]
Скачиваний: 5
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 дек 2017, 16:54 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Olej писал(а):
P.S. Относительно статистики совпадений (это термин!) см. очень кратко здесь Свободные материалы преподавателей кафедры 806 МАИ

Собственно, относительно статистики совпадений обстоятельно читаем всё в той же книге, с которой всё началось:
Изображение
стр.171 (страницы по переводному изданию):
Цитата:
7.8.1. Статистика совпадений: те же границы и меньшая память.

стр.171 - стр.173


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 дек 2017, 17:23 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
На вот таком вот занятном ресурсе:
КОНСУЛЬТАНТ СТУДЕНТА
Цитата:
Электронная библиотека медицинского колледжа

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

Для начального или поверхностного ознакомления с техникой суффиксных деревьев это может быть удобнее.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 дек 2017, 20:39 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
Olej писал(а):
Совершенно новая алгоритмическая техника.
Позволяющая решить многие не решаемые до этих пор задачи контекстного поиска, сравнений текстов, нахождения общих вхождений в текстах и т.д.

Подобные техники - это революция в технологиях контекстного поиска и других родственных задач!
Из книги Гасфилда (см. выше)...
- (стр.158)
Цитата:
Такова задача о наибольшей общей подстроке, рассматриваемая в п.7.4. Кнут предположил, что в ней линейный по времени алгоритм невозможен [24, 278], а такой алгоритм прямо получается при использовании суффиксных деревьев.

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


Из книги (всей целиком), кстати, становится понятно, почему разнообразные задачи поиска и идентификации строк так актуальны в биологии и медицине, ещё более чем в ИТ.


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 27 дек 2017, 17:54 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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 КБ]
Скачиваний: 5
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 05 янв 2018, 16:38 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 10718
Откуда: Харьков
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 );
      }


Мне было этим в облом заниматься, хотя всё, в принципе, понятно...
Возможно, если будет время и желание, я код на соответствие такой динамике и переделаю... ;-)


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Часовой пояс: UTC + 3 часа


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

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB
[ Time : 0.152s | 20 Queries | GZIP : On ]