Редактирование: Преобразование Барроуза-Уилера

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

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

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 375: Строка 375:
  
 
Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево:
 
Пусть текст <tex>T</tex> состоит из <tex>N + 1</tex> символов, занумерованных с нуля: <tex>T[0..N]</tex>. Буквы <tex>T[i]</tex> принадлежат некоторому алфавиту <tex>A</tex>. Лексикографический порядок (строгий) на строках из алфавита <tex>A</tex> будем обозначать <tex>\preceq (\prec)</tex>. Обозначим через <tex>S_{k}T</tex> циклический сдвиг текста <tex>T</tex> на <tex>k</tex> символов влево:
 +
 
:{|
 
:{|
 
<tex> S_{k}T = T[(j + k) (\bmod\ N + 1)] </tex>
 
<tex> S_{k}T = T[(j + k) (\bmod\ N + 1)] </tex>
Строка 380: Строка 381:
  
 
Существует перестановка <tex>p</tex> чисел <tex>\{0, ..., N\}</tex>, которая удовлетворяет условию:  
 
Существует перестановка <tex>p</tex> чисел <tex>\{0, ..., N\}</tex>, которая удовлетворяет условию:  
 +
 
:{|
 
:{|
 
<tex> S_{p(i)}T \preceq S_{p(i + 1)}T,\ i = 0, ..., N - 1\ \ \textbf{(1)}</tex>
 
<tex> S_{p(i)}T \preceq S_{p(i + 1)}T,\ i = 0, ..., N - 1\ \ \textbf{(1)}</tex>
Строка 385: Строка 387:
  
 
Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением:
 
Преобразование Барроуза-Уилера текста <tex>T</tex> есть текст <tex>B[0..N] = BW(T)</tex>, буквы которого заданы соотношением:
 +
 
:{|
 
:{|
 
<tex>B[i] = S_{p(i)}T[N]</tex>, другими словами <tex>B[i] = S_{p(i) - 1}T[0] = T[(p(i) - 1) (\bmod\ N + 1)] \ \ \textbf{(2)}</tex>
 
<tex>B[i] = S_{p(i)}T[N]</tex>, другими словами <tex>B[i] = S_{p(i) - 1}T[0] = T[(p(i) - 1) (\bmod\ N + 1)] \ \ \textbf{(2)}</tex>
Строка 390: Строка 393:
  
 
Пусть <tex>\sigma</tex> {{---}} перестановка чисел <tex>\{0, ..., N\}</tex>, удовлетворяющая условию:
 
Пусть <tex>\sigma</tex> {{---}} перестановка чисел <tex>\{0, ..., N\}</tex>, удовлетворяющая условию:
 +
 
:{|
 
:{|
 
<tex>B_{\sigma(i)} \preceq B_{\sigma(i + 1)}</tex>, при <tex>i = 0, ..., N - 1\ \ \textbf{(3)}</tex>,
 
<tex>B_{\sigma(i)} \preceq B_{\sigma(i + 1)}</tex>, при <tex>i = 0, ..., N - 1\ \ \textbf{(3)}</tex>,
 
|}
 
|}
 +
 
и в случае равенства <tex>B_{\sigma(i)}</tex> и <tex>B_{\sigma(i + 1)}</tex> выполнено {{---}} <tex>\sigma(i) < \sigma(i + 1)</tex>. Перестановка однозначно определяется текстом <tex>B</tex> и ее можно посчитать за <tex>O(N)</tex>, используя сортировку подсчетом. Рассмотрим перестановку <tex>\sigma</tex> как отображение <tex>\sigma : \{0, ..., N\} \to \{0, ..., N\}</tex>. Пусть <tex>\sigma^{k}</tex> копмозиция <tex>k</tex> отображений <tex>\sigma^{k} = \sigma^{k - 1} \circ \sigma</tex>, где <tex>\sigma^{1} = \sigma, \sigma^{0} \equiv i</tex>.
 
и в случае равенства <tex>B_{\sigma(i)}</tex> и <tex>B_{\sigma(i + 1)}</tex> выполнено {{---}} <tex>\sigma(i) < \sigma(i + 1)</tex>. Перестановка однозначно определяется текстом <tex>B</tex> и ее можно посчитать за <tex>O(N)</tex>, используя сортировку подсчетом. Рассмотрим перестановку <tex>\sigma</tex> как отображение <tex>\sigma : \{0, ..., N\} \to \{0, ..., N\}</tex>. Пусть <tex>\sigma^{k}</tex> копмозиция <tex>k</tex> отображений <tex>\sigma^{k} = \sigma^{k - 1} \circ \sigma</tex>, где <tex>\sigma^{1} = \sigma, \sigma^{0} \equiv i</tex>.
  

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

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

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

Шаблоны, используемые на этой странице: