Редактирование: Суффиксный автомат

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 68: Строка 68:
 
! Изображение !! Описание
 
! Изображение !! Описание
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s1.png|x180px|center|Шаг 1.]]
+
|[[Файл:Suffix_automaton_s1.png|x180px|center|Шаг 1.]]
 
|Изначально автомат состоит из одного начального состояния. <tex>\mathrm{last} = 0, \mathrm{len(0)} = 0</tex>
 
|Изначально автомат состоит из одного начального состояния. <tex>\mathrm{last} = 0, \mathrm{len(0)} = 0</tex>
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s2.png|x180px|center|Шаг 2.]]
+
|[[Файл:Suffix_automaton_s2.png|x180px|center|Шаг 2.]]
 
|Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>\mathrm{link_{1}} = 0</tex>. <tex>\mathrm{last} = 1, \mathrm{len(1)} = 1</tex>
 
|Добавляем символ <tex>a</tex>. Создаем состояние <tex>1</tex>. Переходов из начального состояния по символу <tex>a</tex> нет, перейти по суффиксным ссылкам некуда, значит добавим суффиксную ссылку <tex>\mathrm{link_{1}} = 0</tex>. <tex>\mathrm{last} = 1, \mathrm{len(1)} = 1</tex>
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s3.png|x180px|center|Шаг 3.]]
+
|[[Файл:Suffix_automaton_s3.png|x180px|center|Шаг 3.]]
 
|Добавляем символ <tex>b</tex>. Создаем состояние <tex>2</tex>. Добавим переход из <tex>1</tex>, откатимся по суффиксной ссылке и добавим переход из <tex>0</tex>. Добавим суффиксную ссылку <tex>\mathrm{link_{2}} = 0</tex>. <tex>\mathrm{last} = 2, \mathrm{len(2)} = 2</tex>
 
|Добавляем символ <tex>b</tex>. Создаем состояние <tex>2</tex>. Добавим переход из <tex>1</tex>, откатимся по суффиксной ссылке и добавим переход из <tex>0</tex>. Добавим суффиксную ссылку <tex>\mathrm{link_{2}} = 0</tex>. <tex>\mathrm{last} = 2, \mathrm{len(2)} = 2</tex>
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s4.png|x180px|center|Шаг 4.]]
+
|[[Файл:Suffix_automaton_s4.png|x180px|center|Шаг 4.]]
 
|Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>\mathrm{last} = 3, \mathrm{len(3)} = 3</tex>
 
|Аналогично добавим символ <tex>c</tex> и обновим автомат. <tex>\mathrm{last} = 3, \mathrm{len(3)} = 3</tex>
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s5.png|x180px|center|Шаг 5.]]
+
|[[Файл:Suffix_automaton_s5.png|x180px|center|Шаг 5.]]
 
|Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex>
 
|Добавляем символ <tex>b</tex>. Добавим переход из <tex>3</tex> и перейдем по суффиксной ссылке в начальное состояние. Из состояния <tex>0</tex> существует переход по символу <tex>b</tex>
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s6.png|x180px|center|Шаг 6.]]
+
|[[Файл:Suffix_automaton_s6.png|x180px|center|Шаг 6.]]
 
|Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0)} + 1 \neq \mathrm{len(2)}</tex>.
 
|Рассмотрим состояние <tex>2</tex>, куда существует переход. Имеем <tex>\mathrm{len(0)} + 1 \neq \mathrm{len(2)}</tex>.
 
# Создаем новое состояние <tex>5</tex>.
 
# Создаем новое состояние <tex>5</tex>.
Строка 89: Строка 89:
 
# Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.
 
# Перенаправим суффиксную ссылку из <tex>2</tex> в <tex>5</tex> и добавим ссылку из <tex>4</tex> в <tex>5</tex>. Перенаправим переход <tex>0 \rightarrow 2</tex> в состояние <tex>5</tex>.
 
|-
 
|-
|style="background-color:#FFF" |[[Файл:Suffix_automaton_s7.png|x180px|center|Шаг 7.]]
+
|[[Файл:Suffix_automaton_s7.png|x180px|center|Шаг 7.]]
 
|Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.
 
|Построение автомата завершено. Чтобы пометить терминальные вершины, найдём состояние, которое принимает строку <tex>abcb</tex> и пройдём по суффиксным ссылкам, помечая все посещенные состояния терминальными.
 
|-
 
|-

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)