Аноним

Дерево положений: различия между версиями

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


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


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