Преобразование Шиндлера

Преобразование Шиндлера

Преобразование Шиндлера(Schindler Transformation)- эффективный алгоритм упорядочивания элементов с большой длиной ключа, использованием обычной поразрядной сортировки.

Спустя год после опубликования алгоритма BWT, Михаэлем Шиндлером было предложено альтернативное преобразования данных, являющееся главным образом обобщением BWT и решением главной его проблематики - выбора эффективного алгоритма упорядочивания элементов с большой длиной ключа, использованием обычной поразрядной сортировки.

Особенности

Различают вариации преобразования Шиндлера (ST) по числу элементов каждой из строк матрицы участвующих в сортировке. Математически доказано, что при обработке текстов ST-2, ST-3 или ST-4 (в зависимости от лингвистических особенностей формирования единиц информации в тексте) дают 90% от эффективности BWT (ST-k - преобразование Шиндлера k-го порядка) притом, что скорость сортировки увеличивается на порядок (в зависимости от выбранного алгоритма упорядочивания, слово "порядок" может находиться в пределах от log3 (n-ek), где n - размер блока, и выше).

Эффективность ST во многом определяется возможностью обработки намного больших, по сравнению с BWT, блоков за счет экономии памяти (не нужно хранить n·(n-k) символов). Так, при наличии 512 Мб оперативной памяти, алгоритм BWT может обрабатывать блоки не более, чем из n = 23170 элементов (n·n ~ 512 Мб), тогда как ST-3 уже из n = 178956970 элементов (3·n ~ 512 Мб) - почувствуйте разницу :-)

Пример

Рассмотрим работу алгоритма ST-1 на примере преобразования слова "ЛОГОВО".

-- Строим матрицу циклических сдвигов исходного блока (на 0 символов влево в первой строке и на 1 символ влево во второй) 1. ЛОГОВО 2. ОГОВОЛ Примечание: Для ST-k, при k = n и BWT - матрицы будут эквивалентны. -- Считая элементы первой строки ключами, а соответствующие им символы второй строки данными, отсортируем ключи в лексикографическом порядке 1. ВГЛООО 2. ОООГВЛ—Склеивая значение второй строки (для ST-k это будет k+1 строка) и первый символ исходного блока ("Л"), получаем результат работы ST-1: "ОООГВЛЛ".

Абсолютно аналогично действует алгоритм ST-k, только матрица будет состоять уже из k строк, а сортировка производится по первым k элементам. Обратное к ST преобразование—Восстановим матрицу, построенную на последнем этапе работы ST, отсортировав "ОООГВЛ" по возрастанию 1. ВГЛООО 2. ОООГВЛ—Исходный блок начинается с символа "Л", соответствующий ему элемент второй строки ("О") является следующим символом исходного блока (элементы второй строки предшествуют соответствующим элементам первой). Вычеркиваем символ "Л" из первой строки. 1. ВГЛООО 2. ОООГВЛ—Ищем первое вхождение символа "О" в первой строке, соответствующий элемент второй строки ("Г") будет следующим символом исходного блока. Далее вычеркиваем символ "О" из первой строки. Продолжаем этот процесс до тех пор, пока все элементы первой строки не будут исчерпаны 1. ВГЛООО 2. ОООГВЛ—Выпишем элементы первой строки в порядке их вычеркивания: "ЛОГОВО", тем самым, выполнив обратное к ST преобразование.

• Для лучшего понимания работы алгоритма напишем программу, выполняющую обратное к ST-1 преобразование (unST-1):

Указан неподдерживаемый язык.

Вы должны указать язык следующим образом: <source lang="html4strict">...</source>

Поддерживаемые языки:

abap, actionscript, actionscript3, ada, apache, applescript, apt_sources, asm, asp, autoit, avisynth, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_mac, caddcl, cadlisp, cfdg, cfm, cil, cmake, cobol, cpp, cpp-qt, csharp, css, d, dcs, delphi, diff, div, dos, dot, eiffel, email, erlang, fo, fortran, freebasic, genero, gettext, glsl, gml, gnuplot, groovy, haskell, hq9plus, html4strict, idl, ini, inno, intercal, io, java, java5, javascript, kixtart, klonec, klonecpp, latex, lisp, locobasic, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, make, matlab, mirc, modula3, mpasm, mxml, mysql, nsis, oberon2, objc, ocaml, ocaml-brief, oobas, oracle11, oracle8, pascal, per, perl, php, php-brief, pic16, pixelbender, plsql, povray, powershell, progress, prolog, properties, providex, python, qbasic, rails, rebol, reg, robots, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, sql, tcl, teraterm, text, thinbasic, tsql, typoscript, vb, vbnet, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xml, xorg_conf, xpp, z80

• Если для unST-1 все предельно просто и быстро, то алгоритм unST-3 хотя и действует по тому же принципу, но заметно медленнее и сложнее в реализации:

Указан неподдерживаемый язык.

Вы должны указать язык следующим образом: <source lang="html4strict">...</source>

Поддерживаемые языки:

abap, actionscript, actionscript3, ada, apache, applescript, apt_sources, asm, asp, autoit, avisynth, bash, basic4gl, bf, bibtex, blitzbasic, bnf, boo, c, c_mac, caddcl, cadlisp, cfdg, cfm, cil, cmake, cobol, cpp, cpp-qt, csharp, css, d, dcs, delphi, diff, div, dos, dot, eiffel, email, erlang, fo, fortran, freebasic, genero, gettext, glsl, gml, gnuplot, groovy, haskell, hq9plus, html4strict, idl, ini, inno, intercal, io, java, java5, javascript, kixtart, klonec, klonecpp, latex, lisp, locobasic, lolcode, lotusformulas, lotusscript, lscript, lsl2, lua, m68k, make, matlab, mirc, modula3, mpasm, mxml, mysql, nsis, oberon2, objc, ocaml, ocaml-brief, oobas, oracle11, oracle8, pascal, per, perl, php, php-brief, pic16, pixelbender, plsql, povray, powershell, progress, prolog, properties, providex, python, qbasic, rails, rebol, reg, robots, ruby, sas, scala, scheme, scilab, sdlbasic, smalltalk, smarty, sql, tcl, teraterm, text, thinbasic, tsql, typoscript, vb, vbnet, verilog, vhdl, vim, visualfoxpro, visualprolog, whitespace, whois, winbatch, xml, xorg_conf, xpp, z80

Связать^?

См. также

• Сжатие данных с потерями
• Сжатие без потерь
• Список алгоритмов

Ссылки

[1]