|
|
| (не показано 19 промежуточных версий 3 участников) |
| Строка 1: |
Строка 1: |
| − | ==Наивный алгоритм==
| + | #перенаправление [[Преобразование Барроуза-Уилера]] |
| − | ===Описание===
| |
| − | Если отсортировать символы последнего столбца матрицы перестановок - а перед началом обратного преобразования нам известен только он - то мы получим первый столбец данной матрицы,так как строки матрицы были отсортированы в лексикографическом порядке.
| |
| − | Известно, что символы последнего столбца предшествуют символам первого, находящимся в той же строке, поскольку использовался циклический сдвиг. Таким образом, мы имеем уже список пар, состоящих из символа последнего столбца и следующего за ним символа первого столбца. После сортировки этих пар мы обретаем знание о двух первых столбцах матрицы. И так далее, пока мы не получим всю матрицу перестановок, на каждом шаге новый префикс получается в результате конкатенации последнего символа и соответствующего ему префикса. В результате получаем матрицу, содержащую все циклические сдвиги, откуда выписываем строку с заданным номером. Рассмотрим этот алгоритм на конкретном примере. Пусть дана строка "абракадабра". В результате преобразования получаем набор ("рдакраааабб", 3).
| |
| − | {|
| |
| − | |
| |
| − | {| border="1"
| |
| − | |а||...||р
| |
| − | |-
| |
| − | |а||...||д
| |
| − | |-
| |
| − | |а||...||а
| |
| − | |-
| |
| − | |а||...||к
| |
| − | |-
| |
| − | |а||...||р
| |
| − | |-
| |
| − | |б||...||а
| |
| − | |-
| |
| − | |б||...||а
| |
| − | |-
| |
| − | |д||...||а
| |
| − | |-
| |
| − | |к||...||а
| |
| − | |-
| |
| − | |р||...||б
| |
| − | |-
| |
| − | |р||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аа||...||р
| |
| − | |-
| |
| − | |аб||...||д
| |
| − | |-
| |
| − | |аб||...||а
| |
| − | |-
| |
| − | |ад||...||к
| |
| − | |-
| |
| − | |ак||...||р
| |
| − | |-
| |
| − | |бр||...||а
| |
| − | |-
| |
| − | |бр||...||а
| |
| − | |-
| |
| − | |да||...||а
| |
| − | |-
| |
| − | |ка||...||а
| |
| − | |-
| |
| − | |ра||...||б
| |
| − | |-
| |
| − | |ра||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |ааб||...||р
| |
| − | |-
| |
| − | |абр||...||д
| |
| − | |-
| |
| − | |абр||...||а
| |
| − | |-
| |
| − | |ада||...||к
| |
| − | |-
| |
| − | |ака||...||р
| |
| − | |-
| |
| − | |бра||...||а
| |
| − | |-
| |
| − | |бра||...||а
| |
| − | |-
| |
| − | |даб||...||а
| |
| − | |-
| |
| − | |кад||...||а
| |
| − | |-
| |
| − | |раа||...||б
| |
| − | |-
| |
| − | |рак||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабр||...||р
| |
| − | |-
| |
| − | |абра||...||д
| |
| − | |-
| |
| − | |абра||...||а
| |
| − | |-
| |
| − | |адаб||...||к
| |
| − | |-
| |
| − | |акад||...||р
| |
| − | |-
| |
| − | |браа||...||а
| |
| − | |-
| |
| − | |брак||...||а
| |
| − | |-
| |
| − | |дабр||...||а
| |
| − | |-
| |
| − | |када||...||а
| |
| − | |-
| |
| − | |рааб||...||б
| |
| − | |-
| |
| − | |рака||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабра||...||р
| |
| − | |-
| |
| − | |абраа||...||д
| |
| − | |-
| |
| − | |абрак||...||а
| |
| − | |-
| |
| − | |адабр||...||к
| |
| − | |-
| |
| − | |акада||...||р
| |
| − | |-
| |
| − | |брааб||...||а
| |
| − | |-
| |
| − | |брака||...||а
| |
| − | |-
| |
| − | |дабра||...||а
| |
| − | |-
| |
| − | |кадаб||...||а
| |
| − | |-
| |
| − | |раабр||...||б
| |
| − | |-
| |
| − | |ракад||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабрак||...||р
| |
| − | |-
| |
| − | |абрааб||...||д
| |
| − | |-
| |
| − | |абрака||...||а
| |
| − | |-
| |
| − | |адабра||...||к
| |
| − | |-
| |
| − | |акадаб||...||р
| |
| − | |-
| |
| − | |браабр||...||а
| |
| − | |-
| |
| − | |бракад||...||а
| |
| − | |-
| |
| − | |дабраа||...||а
| |
| − | |-
| |
| − | |кадабр||...||а
| |
| − | |-
| |
| − | |раабра||...||б
| |
| − | |-
| |
| − | |ракада||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабрака||...||р
| |
| − | |-
| |
| − | |абраабр||...||д
| |
| − | |-
| |
| − | |абракад||...||а
| |
| − | |-
| |
| − | |адабраа||...||к
| |
| − | |-
| |
| − | |акадабр||...||р
| |
| − | |-
| |
| − | |браабра||...||а
| |
| − | |-
| |
| − | |бракада||...||а
| |
| − | |-
| |
| − | |дабрааб||...||а
| |
| − | |-
| |
| − | |кадабра||...||а
| |
| − | |-
| |
| − | |раабрак||...||б
| |
| − | |-
| |
| − | |ракадаб||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабракад||...||р
| |
| − | |-
| |
| − | |абраабра||...||д
| |
| − | |-
| |
| − | |абракада||...||а
| |
| − | |-
| |
| − | |адабрааб||...||к
| |
| − | |-
| |
| − | |акадабра||...||р
| |
| − | |-
| |
| − | |браабрак||...||а
| |
| − | |-
| |
| − | |бракадаб||...||а
| |
| − | |-
| |
| − | |дабраабр||...||а
| |
| − | |-
| |
| − | |кадабраа||...||а
| |
| − | |-
| |
| − | |раабрака||...||б
| |
| − | |-
| |
| − | |ракадабр||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабракада||...||р
| |
| − | |-
| |
| − | |абраабрак||...||д
| |
| − | |-
| |
| − | |абракадаб||...||а
| |
| − | |-
| |
| − | |адабраабр||...||к
| |
| − | |-
| |
| − | |акадабраа||...||р
| |
| − | |-
| |
| − | |браабрака||...||а
| |
| − | |-
| |
| − | |бракадабр||...||а
| |
| − | |-
| |
| − | |дабраабра||...||а
| |
| − | |-
| |
| − | |кадабрааб||...||а
| |
| − | |-
| |
| − | |раабракад||...||б
| |
| − | |-
| |
| − | |ракадабра||...||б
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |аабракадаб||р
| |
| − | |-
| |
| − | |абраабрака||д
| |
| − | |-
| |
| − | |абракадабр||а
| |
| − | |-
| |
| − | |адабраабра||к
| |
| − | |-
| |
| − | |акадабрааб||р
| |
| − | |-
| |
| − | |браабракад||а
| |
| − | |-
| |
| − | |бракадабра||а
| |
| − | |-
| |
| − | |дабраабрак||а
| |
| − | |-
| |
| − | |кадабраабр||а
| |
| − | |-
| |
| − | |раабракада||б
| |
| − | |-
| |
| − | |ракадабраа||б
| |
| − | |}
| |
| − | |}
| |
| − | Зная номер исходной строки - 3, мы воспроизводим входные данные - "абракадабра".
| |
| − | ===Сложность===
| |
| − | Как несложно посчитать сложность данного алгоритма <tex> 0(N^3logN) </tex>, также он требует <tex>0(N^2)</tex> памяти.
| |
| − | ==Оптимизация==
| |
| − | ===Описание===
| |
| − | Однако, данный алгоритм можно оптимизировать. Заметим, что при каждом проявлении доселе неизвестного столбца выполнялись одни и те же действия. А именно, из строки, начинающейся с некоторого символа последнего столбца получалась строка, в которой этот символ находится на первой позиции. Теперь если определить порядок получения символов 1ого столбца из символов последнего, то полученные значения будут являться вектором обратного преобразования. Для получения исходной строки надо выписать символы из преобразованной строки в порядке, соответствующему данному вектору, начиная с номера, содержащегося в исходных данных. Рассмотрим данный алгоритм на том же примере.
| |
| − | {|
| |
| − | |
| |
| − | {| border="1"
| |
| − | |0||а|| ||р||9
| |
| − | |-
| |
| − | |1||а||||д||7
| |
| − | |-
| |
| − | |2||а|| ||a||0
| |
| − | |-
| |
| − | |3||а|| ||к||8
| |
| − | |-
| |
| − | |4||а|| ||р||10
| |
| − | |-
| |
| − | |5||б|| ||a||1
| |
| − | |-
| |
| − | |6||б|| ||a||2
| |
| − | |-
| |
| − | |7||д|| ||a||3
| |
| − | |-
| |
| − | |8||к|| ||a||4
| |
| − | |-
| |
| − | |9||р|| ||б||5
| |
| − | |-
| |
| − | |10||р|| ||б||6
| |
| − | |}
| |
| − | | ||
| |
| − | |
| |
| − | {| border="1"
| |
| − | |9|| ||2
| |
| − | |-
| |
| − | |7||||5
| |
| − | |-
| |
| − | |0||||6
| |
| − | |-
| |
| − | |8||||7
| |
| − | |-
| |
| − | |10||||8
| |
| − | |-
| |
| − | |1||||9
| |
| − | |-
| |
| − | |2||||10
| |
| − | |-
| |
| − | |3||||1
| |
| − | |-
| |
| − | |4||||3
| |
| − | |-
| |
| − | |5||||0
| |
| − | |-
| |
| − | |6||||4
| |
| − | |}
| |
| − | |}
| |
| − | Выписывая элементы исходной строки в порядке полученного вектора, начиная с 3-его номера, получаем :
| |
| − | {| border="1"
| |
| − | |6
| |
| − | |=>
| |
| − | |10
| |
| − | |=>
| |
| − | |4
| |
| − | |=>
| |
| − | |8
| |
| − | |=>
| |
| − | |3
| |
| − | |=>
| |
| − | |7
| |
| − | |=>
| |
| − | |1
| |
| − | |=>
| |
| − | |5
| |
| − | |=>
| |
| − | |9
| |
| − | |=>
| |
| − | |0
| |
| − | |=>
| |
| − | |2
| |
| − | |-
| |
| − | |а
| |
| − | |
| |
| − | |б
| |
| − | |
| |
| − | |р
| |
| − | |
| |
| − | |а
| |
| − | |
| |
| − | |к
| |
| − | |
| |
| − | |а
| |
| − | |
| |
| − | |д
| |
| − | |
| |
| − | |а
| |
| − | |
| |
| − | |б
| |
| − | |
| |
| − | |р
| |
| − | |
| |
| − | |а
| |
| − | |}
| |
| − | ===Сложность===
| |
| − | Данный алгоритм работает за <tex>0(NlogN)</tex> действий и требует <tex>0(N)</tex> памяти. Однако, если размер алфавита не очень большой, то для выяснения 1ого столбца матрицы можно использовать сортировку подсчетом, в этом случае алгоритм работает за <tex>0(N+M)</tex> действий и требует <tex>0(N+M)</tex> памяти, где <tex>M</tex> - размер алфавита.
| |
| − | ===Псевдокод===
| |
| − | Пусть N - количество символов во входной строке, M - количество символов в алфавите, k - номер исходной строки в матрице перестановок, s - входящая строка, count - массив для сортировки подсчетом, t - вектор обратного преобразования.
| |
| − | | |
| − | //считаем частоты символов
| |
| − | for i = 0..M count[i] = 0
| |
| − | for i = 0..N count[s[i]]++
| |
| − | //упорядочиваем символы, чтобы получить первый столбец исходной матрицы
| |
| − | //count[i] указывает на первую позицию символа i в первом столбце
| |
| − | sum = 0
| |
| − | for i = 0..M
| |
| − | sum = sum + count[i]
| |
| − | count[i] = sum - count[i]
| |
| − | //создаем вектор обратного преобразования
| |
| − | for i = 0..N
| |
| − | t[count[s[i]]]] = i
| |
| − | count[s[i]]++
| |
| − | //восстанавливаем исходный текст
| |
| − | j = t[x]
| |
| − | for i = 0..N
| |
| − | print(s[j])
| |
| − | j = t[j]
| |
| − | | |
| − | ==См. также==
| |
| − | *[[Преобразование Барроуза-Уиллера]]
| |
| − | *[[Преобразование MTF]]
| |
