Дерево положений

Материал из WEGA
Версия от 13:32, 13 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево положений''' (''Position tree'') - Пусть <math>\alpha = a_{1}a_{2}\ldots a_{n}</math>--- слово из м...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Дерево положений (Position tree) - Пусть [math]\displaystyle{ \alpha = a_{1}a_{2}\ldots a_{n} }[/math]--- слово из множества всех слов в алфавите [math]\displaystyle{ \Sigma }[/math]. Пусть символ [math]\displaystyle{ \# }[/math] является символом алфавита [math]\displaystyle{ \Sigma }[/math]. Тогда деревом положений [math]\displaystyle{ T(\alpha) }[/math] для [math]\displaystyle{ \alpha \# }[/math] является дерево, границы которого помечены элементами из [math]\displaystyle{ \Sigma \cup \{\#\} }[/math], и которое строится в соответствии с правилами:

а) [math]\displaystyle{ T(\alpha) }[/math] имеет [math]\displaystyle{ (n + 1) }[/math] листьев, помеченных [math]\displaystyle{ 1, 2, \ldots, n+1 }[/math];

б) последовательность меток на дугах маршрута, начиная от корня к листьям, с индексом [math]\displaystyle{ i }[/math], является подсловом-идентификатором для положения [math]\displaystyle{ i }[/math] в дереве [math]\displaystyle{ \alpha \# }[/math].

Литература

[Словарь]