Rivalry2

HTML Diff

1 added 17 removed

Original 2026-01-01

Modified 2026-02-26

1 Древовидные структуры можно использовать для хранения и организации, причем не только цельных, но и группируемых данных.

2 Например, такие данные могут состоять из последовательности одинаковых символов. Рассмотрим в качестве исходной точки несколько слов из толкового словаря:

3 <blockquote>ОБЕСПЕЧИВАТЬ. Несовершенный вид к "обеспечить"...

4 ОБЕСПЕЧИТЬ. Совершенный вид к "обеспечивать". Предоставить материальные средства для жизни...

5 ОБЕСПЕЧИТЬСЯ. Совершенный вид к "обеспечиваться". Запастись, стать обеспеченным...

6 </blockquote>Как можно видеть из примера, существует несколько слов, которые начинаются на одну и ту же последовательность символов. В нашем случае у слов один и тот же корень, меняются только суффиксы и окончания.

7 В информатике часть последовательности данных, которая не меняется и находится перед суффиксом, называетсяпрефиксной частью.

8 В этом уроке мы более подробно познакомимся с принципами работы префиксных деревьев, их производными версиями и механизмами работы.

9 <h2>Зачем нужны префиксные деревья</h2>

10 При помощи одинаковых префиксов можно сгруппировать наши слова в следующем виде:

11 Префиксные деревья специально разработаны, чтобы помогать нам организовывать, хранить и группировать данные в таком виде. Префиксное дерево для нашего примера будут иметь следующий вид:

12 Префиксные деревья помогают прогнозировать пользовательский ввод - например, предлагая слово, наиболее близкое по составу введенных букв. Так работают системы проверки орфографии или дополнитель кода в среде разработки.

13 Механизм префиксов нашел свое место и в работе интернет-маршрутизации. Там он помогает эффективно хранить IP-адреса, группируемые по префиксам:

14 <h2>Как устроены префиксные деревья</h2>

15 В качестве примера префиксного дерева рассмотрим хранение слов или некоторых ассоциативных массивов.

16 Префиксным деревомназывается дерево, в котором каждая вершина помечена некоторой буквой и имеет дополнительный<a>признак терминальности</a>. Если мы читаем вершины по порядку, мы получаем последовательность символов, соответствующую некоторому слову.

17 Если полученная последовательность заканчивается признаком терминальности, то такое слово считается существующим в этой структуре данных.

18 При этом два узла не могут быть связаны с общим предком с помощью одной и той же буквы.

19 <h2>Операции над деревом</h2>

20 Для начала представим префиксное дерево в виде кода на JavaScript:

21 - Javascript

22 - Java

23 - Python

24 - PHP

25 С префиксными деревьями можно проводить разные операции, в том числе поиск слов, вставка нового слова и удаление слова. Разберем их подробнее.

21 С префиксными деревьями можно проводить разные операции, в том числе поиск слов, вставка нового слова и удаление слова. Разберем их подробнее.

26 <h3>Поиск слова в дереве</h3>

22 <h3>Поиск слова в дереве</h3>

27 Для выполнения поиска сперва необходимо обратиться к корневой вершине. Обычно считается, что значение корневой вершины равно пустоте.

23 Для выполнения поиска сперва необходимо обратиться к корневой вершине. Обычно считается, что значение корневой вершины равно пустоте.

28 Далее мы перемещаемся по указателям, соответствующим каждой следующей букве в искомом слове.

24 Далее мы перемещаемся по указателям, соответствующим каждой следующей букве в искомом слове.

29 Как только все переходы будут выполнены, нужно выполнить проверку на наличие флага терминальности в поле end нашего класса.

25 Как только все переходы будут выполнены, нужно выполнить проверку на наличие флага терминальности в поле end нашего класса.

30 - Если флаг конца слова присутствует, то поис�� считаем завершенным успешно - искомое слово найдено.

26 + Если флаг конца слова присутствует, то поиск считаем завершенным успешно - искомое слово найдено.

31 Представим теперь эту операцию в виде метода:

27 Представим теперь эту операцию в виде метода:

32 - Javascript

33 - Java

34 - Python

35 - PHP

36 <h3>Вставка слова</h3>

28 <h3>Вставка слова</h3>

37 В таком случае операция вcтавки слова в дерево будет выглядеть следующим образом:

29 В таком случае операция вcтавки слова в дерево будет выглядеть следующим образом:

38 - Javascript

39 - Java

40 - Python

41 - PHP

42 <h3>Удаление слова</h3>

30 <h3>Удаление слова</h3>

43 Операция удаления слова принимает следующий вид:

31 Операция удаления слова принимает следующий вид:

44 - Javascript

45 - Java

46 - Python

47 - PHP

48 <h2>Сжатые префиксные деревья</h2>

32 <h2>Сжатые префиксные деревья</h2>

49 Это особый подвид префиксных деревьев, заслуживающий отдельного внимания.

33 Это особый подвид префиксных деревьев, заслуживающий отдельного внимания.

50 В таких деревьях мы сжимаем структуру за счет размещения в вершине не одной буквы, а сразу целого фрагмента префикса. При этом из каждого элемента этого префикса существует строго одна связь с другим элементом префикса.

34 В таких деревьях мы сжимаем структуру за счет размещения в вершине не одной буквы, а сразу целого фрагмента префикса. При этом из каждого элемента этого префикса существует строго одна связь с другим элементом префикса.

51 Такие деревья гораздо удобнее использовать для чтения информации за счет уменьшения количества переходов по ссылкам между вершинами.

35 Такие деревья гораздо удобнее использовать для чтения информации за счет уменьшения количества переходов по ссылкам между вершинами.

52 Рассмотрим пример такого дерева на рисунке ниже:

36 Рассмотрим пример такого дерева на рисунке ниже:

53 А так это дерево выглядит без сжатия:

37 А так это дерево выглядит без сжатия:

54 Как видите, количество переходов между вершинами действительно сокращается. Но важно помнить, что такой способ хранения требует более сложную организацию процедур. При сжатии вставка и удаление слов могут потребовать более неочевидной организации вершин - например, их дополнительного разбиения или объединения.

38 Как видите, количество переходов между вершинами действительно сокращается. Но важно помнить, что такой способ хранения требует более сложную организацию процедур. При сжатии вставка и удаление слов могут потребовать более неочевидной организации вершин - например, их дополнительного разбиения или объединения.

55 Сжатые префиксные деревья отлично подходят для хранения данных, которые редко подвергаются изменениям.

39 Сжатые префиксные деревья отлично подходят для хранения данных, которые редко подвергаются изменениям.

56 <h2>Выводы</h2>

40 <h2>Выводы</h2>

57 В этом уроке вы познакомились с классическими и сжатыми префиксными деревьями. Это отличный механизм организации хранения группируемых данных. Такой способ хранения уменьшает объем хранимых данных, помогает предсказывать пользовательский ввод, автоматически исправлять ошибки и организовывать маршрутизацию в вычислительных сетях.

41 В этом уроке вы познакомились с классическими и сжатыми префиксными деревьями. Это отличный механизм организации хранения группируемых данных. Такой способ хранения уменьшает объем хранимых данных, помогает предсказывать пользовательский ввод, автоматически исправлять ошибки и организовывать маршрутизацию в вычислительных сетях.