Дерево положений: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Дерево положений''' (''Position tree'') - Пусть <math>\alpha = a_{1}a_{2}\ldots a_{n}</math>--- слово из м...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>. | |||
==Литература== | ==Литература== | ||
[Словарь] | [Словарь] | ||
Версия от 17:05, 14 октября 2009
Дерево положений (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].
Литература
[Словарь]