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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

а) T(\alpha) имеет (n + 1) листьев, помеченных 1, 2, \ldots, n+1;

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

Литература

  • Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.