О возможности инкрементальной реализации BWT 0. Терминология. "некоторый" = вполне определенный, но какой именно, не скажу :) "обычно" = иногда :) "значение", "память", "часть" и пр. = пока не придумал :) "целое" = integer. "область" = часть целого. "множество" = совокупность всех значений некоторой области памяти. "элемент множества" = одно из значений некоторой области памяти. "принадлежать множеству" = являться элементом множества. "упорядоченное множество" = множество, значение каждого элемента которого можно однозначно определить по значению элемента какого-то другого множества. "объект", "число" = элемент некоторого множества. "символ" = некоторое число, принадлежащее некоторому множеству; обычно применяется для кодирования букв, цифр и прочих иероглифов. "данное" = известный (мне :) объект. "строка", "блок", "последовательность" = упорядоченное множество объектов. "текст", "таблица" = последовательность строк; при желании может состоять из одной строки. "бред" = строка символов, текст, блок данных и т.п. "сдвиг" = новый бред, получаемый из старого путем разбиения его на две части (с начала до некоторого символа и от следующего символа до последнего), причем одна из этих частей, в принципе, может быть пустой (тогда получается "бессмысленный сдвиг" :), а затем склейкой этих частей в обратном порядке. "столбец" = строка, состоящая из символов, находящихся в одинаковых позициях последовательных строк таблицы. "колонка" = столбец таблицы, находящейся в _этом_ тексте :) BWT = Burrows-Wheeler Transform MTF = move-to-front 1. С чего бы начать. Мысль о возможности кодирования исходной строки с помощью последнего столбца таблицы лексикографически упорядоченных сдвигов этой строки достаточно интересна сама по себе. Но, раз уж она вызывает к жизни массу разнообразных вариаций на тему (например, кодирование с помощью _не последнего_ столбца этой таблицы :), то, вероятно :), совсем неплохо бы убедиться в правомерности самого такого кодирования, то есть доказать однозначность декодирования :). Я попытался вывести это доказательство, в процессе чего сам собой изобрелся некий альтернативный вариант достижения той же цели (нахождения последнего столбца таблицы), и, кроме того, появились некоторые еще мысли, которые делают это самое доказательство вообще не совсем осмысленным, по причине необязательности применения именно _этого_ алгоритма. Так, что, несмотря на то, что даже я :) несколько сомневаюсь в строгости данного доказательства, тем не менее... 1.1. Доказательство Идея следующая: любой бред можно получить, начав с одного символа и, затем, по очереди добавляя _в начало_ соответствующие символы. При этом получается, что последовательность, в которой расположатся сдвиги исходной строки после лексикографической сортировки практически не изменится, за исключением того, что в нее будет добавлена новая "исходная" строка. Это произойдет по той причине, что даже если при сортировке сравнение дойдет до одного из символов , то на этом оно и закончится, так как не может встречаться в одной позиции в разных сдвигах строки. То есть то, что в строки добавлен новый символ не отразится на их порядке. Нас же, на самом деле, интересует столбец таблицы состоящий из последних символов отсортированных сдвигов исходной строки. Так вот, последний столбец новой таблицы, полученной путем вышеописанного добавления символа, можно получить из старого заменой на добавляемый символ и вставкой в позицию, определяемую сортировкой. О новом положении пока достаточно трудно что-то сказать точно, но это и не нужно. Как минимум, последние столбцы таблиц, полученных добавлением различных символов, будут различаться значением этого символа. ------------------T------------------T------------------T------------------ "a" added ¦ "b" added ¦ "c" added ¦ "d" added ------------------+------------------+------------------+------------------ aababaac¦¦aac¦abab aac¦babab¦aac¦abab aac¦cabab¦aac¦abab aac¦dabab aac¦abab aac¦aabab¦abaac¦ab abaac¦bab¦abaac¦ab abaac¦cab¦abaac¦ab abaac¦dab abaac¦ab abaac¦aab¦ababaac¦ ababaac¦b¦ababaac¦ ababaac¦c¦ababaac¦ ababaac¦d ababaac¦ ababaac¦a¦ac¦ababa ac¦bababa¦ac¦ababa ac¦cababa¦ac¦ababa ac¦dababa ac¦ababa ac¦aababa¦baac¦aba baac¦baba¦baac¦aba baac¦caba¦baac¦aba baac¦daba baac¦aba baac¦aaba¦babaac¦a babaac¦ba¦babaac¦a babaac¦ca¦babaac¦a babaac¦da babaac¦a babaac¦aa¦ bababaac¦¦ cababaac¦¦c¦ababaa c¦dababaa c¦ababaa c¦aababaa¦c¦ababaa c¦bababaa¦c¦ababaa c¦cababaa¦ dababaac¦ ¦ababaac ¦aababaac¦¦ababaac ¦bababaac¦¦ababaac ¦cababaac¦¦ababaac ¦dababaac ------------------+------------------+------------------+------------------ Таким образом, если у нас на входе есть таблица для некой строки и символ, то мы _однозначно_ можем построить таблицу для строки, образованной конкатенацией символа и старой строки. Мало того, по положению в каждом сдвиге мы можем определить местонахождение в этом сдвиге добавленного символа и удалить его, также мы можем удалить из таблицы и новую "исходную" строку (которая заканчивается на ). В результате мы снова получим таблицу для строки без добавленного символа, причем совершенно однозначным образом. То есть, мы можем по исходной строке (добавляя по символу) получить таблицу с последним столбцом, изоморфным этой строке. 1.2. Сомнения. Для начала, на самом деле я если что и доказал, так это изоморфизм некоторого бреда и лексикографической таблицы сдвигов, по этому бреду построенной. О последнем же столбце оной таблицы можно сказать лишь то, что его значение однозначно определяется значением исходной строки, а вот верно ли обратное, так и осталось неизвестным. Стало быть, теперь требуется доказать, что последний столбец таблицы однозначно определяет исходную строку или, по крайней мере, последний столбец таблицы для этой строки без первого символа, или саму таблицу для исходной строки целиком :) Вот. В результате, я решил, что здесь требуется поставить эксперимент. И так и сделал. Взявши любимое слово. ( Как можно понять, "¦" обозначает . Причем это ценный символ, с кодом, большим, чем коды всех остальных (используемых здесь) ) ---T--T---T----¬ ¦ ¦+а¦+р ¦ +б ¦ \ +--+--+---+----+ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦ ¦ ¦ ¦ \ ¦ ¦а¦¦а¦р¦а¦бр¦ >-- Это левая часть нижеследующей таблицы. ¦ ¦ ¦ ¦ ¦ / Ну не помещается она в 78 символов целиком :) ¦ ¦ ¦ ¦брদ / ¦ ¦ ¦ ¦ ¦ / ¦ ¦ ¦ ¦ ¦ / ¦ ¦ ¦ ¦ ¦ / ¦ ¦ ¦рদра¦б¦ / ¦¦¦¦¦а¦¦рদбра¦/ L--+--+---+----- ------T------T-------T--------T---------T----------T-----------T------------¬ ¦ +а ¦ +д ¦ +а ¦ +к ¦ +а ¦ +р ¦ +б ¦ +а ¦ +-----+------+-------+--------+---------+----------+-----------+------------+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦абракадабрদ ¦абрদабра¦д¦абра¦ад¦абра¦кад¦абра¦акад¦абра¦ракад¦абра¦бракад¦абра¦абракад¦ ¦ ¦ ¦адабрদадабра¦к¦адабра¦ак¦адабра¦рак¦адабра¦брак¦адабра¦абрак¦ ¦ ¦ ¦ ¦ ¦акадабрদакадабра¦р¦акадабра¦бр¦акадабра¦абр¦ ¦а¦абр¦а¦дабр¦а¦адабр¦а¦кадабр¦а¦акадабр¦а¦ракадабр¦а¦бракадабр¦а¦абракадабр¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦бракадабрদбракадабра¦а¦ ¦бра¦а¦бра¦да¦бра¦ада¦бра¦када¦бра¦акада¦бра¦ракада¦бра¦бракада¦бра¦абракада¦ ¦ ¦дабрদдабра¦а¦дабра¦ка¦дабра¦ака¦дабра¦рака¦дабра¦брака¦дабра¦абрака¦ ¦ ¦ ¦ ¦кадабрদкадабра¦а¦кадабра¦ра¦кадабра¦бра¦кадабра¦абра¦ ¦ ¦ ¦ ¦ ¦ ¦ракадабрদракадабра¦б¦ракадабра¦аб¦ ¦ра¦аб¦ра¦даб¦ра¦адаб¦ра¦кадаб¦ра¦акадаб¦ра¦ракадаб¦ра¦бракадаб¦ра¦абракадаб¦ ¦¦абрদдабрদадабрদкадабрদакадабрদракадабрদбракадабрদабракадабра¦ L-----+------+-------+--------+---------+----------+-----------+------------- А вот то же самое, только от таблиц оставлены лишь первые и последние столбцы. ---T--T--T--T--T--T--T--T--T--T--T--¬ ¦ ¦+а¦+р¦+б¦+а¦+д¦+а¦+к¦+а¦+р¦+б¦+а¦ +--+--+--+--+--+--+--+--+--+--+--+--+ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦а¦¦ ¦ ¦ ¦ ¦ ¦а¦¦ад¦ад¦ад¦ад¦ад¦ад¦ад¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦а¦¦ак¦ак¦ак¦ак¦ак¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦а¦¦ар¦ар¦ар¦ ¦ ¦а¦¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ар¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦б¦¦ба¦ ¦ ¦ ¦ ¦б¦¦ба¦ба¦ба¦ба¦ба¦ба¦ба¦ба¦ ¦ ¦ ¦ ¦ ¦ ¦д¦¦да¦да¦да¦да¦да¦да¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦к¦¦ка¦ка¦ка¦ка¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦р¦¦рб¦рб¦ ¦ ¦ ¦р¦¦рб¦рб¦рб¦рб¦рб¦рб¦рб¦рб¦рб¦ ¦¦¦¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦¦а¦ L--+--+--+--+--+--+--+--+--+--+--+--- Эмпирически, можно выдать следующее заключение: а) следующая колонка получается из предыдущей таким образом: - в последнем столбце заменяется на добавляемый символ; - считается порядковый номер добавляемого символа среди других таких символов в последнем столбце (или в первом :) ; - добавляемый символ вставляется в соответствующий ему отрезок одинаковых символов в первом столбце таким образом, чтобы он имел только что посчитанный порядковый номер; - в соответствующую позицию в последнем столбце вставляется ; б) предыдущая из следующей: - находим символ в первом столбце, которому соответствует в последнем столбце; - считаем порядковый номер N этого символа в цепочке таких символов в первом столбце; - удаляем этот символ из первого столбца и из последнего; - находим в последнем столбце N-ый такой символ и заменяем его на ; Теперь, все же немного по поводу того, как же это так получается. :) Для определения позиции новой "исходной" строки с добавляемым символом необходимо (казалось бы :) сравнить эту строку со всеми остальными и определить, где же ей место. Но, как сразу понятно, место ей среди строк (точнее, сдвигов) с таким же первым символом, как добавляемый. Но все же с этими сдвигами новую строку сравнивать таки придется? Опять же, нет. К счастью, все уже сравнивалось раньше. Поскольку мы работаем со сдвигами одной и той же строки, и поскольку встречается только в одной позиции и, следовательно, дальше него сравнение не идет, а новый символ вставляется всегда после (по модулю длины строки :), то получается, что сдвиги на 1 влево строк, начинающихся с добавляемого символа уже отсортированы, причем этот самый добавляемый символ является последним символов этих сдвигов (по определению). Вот таким, собственно, образом и получается, что порядок добавляемой строки среди сдвигов, начинающихся на добавляемый символ, определяется номером этого символа в последнем столбце таблицы. А поскольку алгоритм получения следующей колонки из предыдущей получен обращением обратного :) алгоритма, то, следовательно, "теорема", наконец, доказана. Причем, на удивление, в процессе получен новый алгоритм вычисления BWT, не требующий лексикографической сортировки. И вообще, собственно, cортировки не требующий :) 1.3. И еще. А обещанные "некоторые еще мысли" заключались, как выяснилось, в новой бредовой (согласно "терминологии":) идее (типа кодирования вторым столбцом :) для которой во-первых, потребуется-таки и на самом деле сортировать сдвиги, а во-вторых, чтобы ее изложить, нужно сначала объяснить, что, собственно (IMHO :) из себя представляет BWT и почему работает (то есть, с его помощью можно даже что-то сжимать :). 1.4. Некоторые вопросы реализации. С распаковкой BWT и до меня все было достаточно нормально - во всяком случае, сортировка не требовалась. А вот с упаковкой дело обстоит несколько сложнее. Конечно, мой алгоритм упаковки, похоже, должен иметь большую производительность, чем любая сортировка даже если его запрограммировать именно в том виде, как он был записан (IMHO :). Но, по-моему, все же не стоит _настолько_ лениться. Лучше уж все-таки рассмотреть, на что же будет тратиться время при его использовании: - поиск и замена символа в последнем столбце ( на добавляемый); - вставка символа в определенную позицию последнего столца (, опять же); - поиск номера символа среди других таких же по его позиции в последнем столбце; - поиск позиции символа в первом столбце по его порядковому номеру; - вставка символа в первый столбец. а) Поскольку вставка и поиск/замена в последнем столбце имеют дело только с , то можно все-таки не хранить его в строке в виде одинокого :) символа, а просто присвоить некоей переменной значение его позиции. В этом случае его искать не придется, и вставлять тоже. б) Преобразованием первого столбца можно вообще не заниматься, так как его можно получить из последнего посимвольной сортировкой. Но если так и сделать, то вставку символа в последний, он же единственный, столбец все же необходимо будет осуществлять. 2. Сортировка, контексты и бредовые идеи. Теперь немного по поводу того, за счет чего же достигается упаковка при применении MTF к последнему столбцу отсортированной таблицы сдвигов. IMHO, MTF был придуман для соверешенно независимого применения и некоторые типы данных (например, тексты) все же будут им упаковываться (слегка :) даже и без предварительного применения дополнительных преобразований. Но, все же, результат BWT упаковывается MTF иногда несколько :) лучше, чем первоначальные данные. По какой же причине так происходит? А вот возьмем в качестве примера некоторую :) лексикографическую таблицу сдвигов (с ) и, в начале каждого из них, отметим подстроку максимальной длины, совпадающую либо с предыдущим сдвигом, либо со следующим. абра¬ кадабра¦ а¬ дакарба¦арб абра- ¦абракад а- карба¦арбад а¬ дабра¦абрак арба¬ дакарба¦ а¦ кадабра¦абр арба- ¦арбадак а- ¦абракадабр а- ¦арбадакарб бра¬ кадабра¦а ба¬ дакарба¦ар бра- ¦абракада ба- ¦арбадакар д¬ абра¦абрака д¬ акарба¦арба к- адабра¦абра к- арба¦арбада ра¬ кадабра¦аб рба¬ дакарба¦а ра- ¦абракадаб рба- ¦арбадака ¦- абракадабра ¦- арбадакарба Получаем интересную вещь: если некоторая подстрока встречается в тексте несколько раз, то сдвиги, начинающиеся со всех ее экземпляров будут сгруппированы сортировкой. При этом, последний символ каждого сдвига будет представлять собой символ, находившийся в тексте _перед_ данный экземпляром подстроки. Таким образом, BWT напоминает что-то типа извращенного :) контекстного моделирования - вместе рассматриваются не следующие за контекстом символы, а символы, за которыми следует данный контекст. К тому же, ничего не стоит с этим разобраться - если обработать BWT текст, записанный от последнего символа к первому, то мы получим как раз то, что нужно, только контексты будут перевернутыми. Это, собственно, и есть одна из новых бредовых идей - не может ли быть, что, например, текстовые данные будут упаковываться лучше, если BWT строить по перевернутым блокам? IMHO, в обычном тексте, контекстом точнее определяется все же именно следующий символ, а не предшествующий контексту (если язык, на котором написан текст - не Forth :). Хотя, при попытке это проверить, на куске _этого_ текста получился проигрыш (~10 байт), а на другом тексте (английском) - все же выигрыш (в ~3 байта :), но я склонен скорее отнести это к влиянию моей реализации MTF (как оно должно быть :), с один раз посчитанной и прописанной в программе таблицей частот для хаффмана). Ладно, по крайней мере, теперь есть возможность выбирать из двух вариантов :). Да, так вот, еще по поводу последнего столбца: а что если после лексикографической сортировки сдвигов отсортировать их по последним символам по отдельности для каждого контекста? 3. Вставка в сбалансированое дерево (на самом деле это дерево не сбалансированое, а фиксированое - изменяются только символы в узлах, а конструкция дерева остается неизменной.) Характеристики: - требуемая память: массив для записи N символов; - требуемое время: O(log(N!)) (то, что обычно называют N*log(N) :) Пример (полученный случайным образом): ---------------T--------T---------¬ ¦ Cтрока после ¦ Символ ¦ Позиция ¦ ¦ вставки ¦ ¦ символа ¦ ¦ символа ¦ ¦ ¦ +--------------+--------+---------+ ¦ р ¦ р ¦ 0 ¦ ¦ ар ¦ а ¦ 0 ¦ ¦ аар ¦ а ¦ 1 ¦ ¦ аадр ¦ д ¦ 2 ¦ ¦ ааадр ¦ а ¦ 2 ¦ ¦ абаадр ¦ б ¦ 1 ¦ ¦ абраадр ¦ р ¦ 2 ¦ ¦ абраадра ¦ а ¦ 7 ¦ ¦ абраадбра ¦ б ¦ 6 ¦ ¦ абраадабра ¦ а ¦ 6 ¦ ¦ абракадабра ¦ к ¦ 4 ¦ L--------------+--------+---------- 3.1. Вставка в инфиксное сбалансированое дерево Способ обхода дерева: левая ветвь - корень - правая ветвь Изменение дерева при последовательной вставке символов: -------------T----------------T------------------¬ ¦Количество ¦ Дерево ¦ Результат ¦ ¦перемещений ¦ ¦ обхода ¦ ¦символов ¦ ¦ дерева ¦ +------------+----------------+------------------+ ¦ ¦ ¦ ¦ ¦ 0 ¦ --р-¬ ¦ <р> ¦ ¦ ¦ ¦ ¦ ¦ ¦ ----а---¬ ¦ <а>р ¦ ¦ 0 ¦ --р-¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 1 ¦ ----а---¬ ¦ а<а>р ¦ ¦ ¦ --а-¬ --р-¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 1 ¦ ----а---¬ ¦ аа<д>р ¦ ¦ ¦ --а-¬ --д-¬ ¦ ¦ ¦ ¦ р¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 1 ¦ ----а---¬ ¦ аа<а>др ¦ ¦ ¦ --а-¬ --д-¬ ¦ ¦ ¦ ¦ a¬ р¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 2 ¦ ----а---¬ ¦ а<б>аадр ¦ ¦ ¦ --а-¬ --д-¬ ¦ ¦ ¦ ¦ б¬ а¬ р¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 2 ¦ ----а---¬ ¦ аб<р>аадр ¦ ¦ ¦ --б-¬ --д-¬ ¦ ¦ ¦ ¦ а¬ р¬ а¬ р¬ ¦ ¦ ¦ ¦ ¦ ¦ ¦ 0 ¦ ----а---¬ ¦ абраадр<а> ¦ ¦ ¦ --б-¬ --д-¬ ¦ ¦ ¦ ¦ а¬ р¬ а¬ р¬ ¦ ¦ ¦ ¦ а ¦ ¦ ¦ ¦ ¦ ¦ ¦ 3 ¦ ----а---¬ ¦ абраад<б>ра ¦ ¦ ¦ --б-¬ --б-¬ ¦ ¦ ¦ ¦ а¬ р¬ д¬ р¬ ¦ ¦ ¦ ¦ а а ¦ ¦ ¦ ¦ ¦ ¦ ¦ 0 ¦ ----а---¬ ¦ абраад<а>бра ¦ ¦ ¦ --б-¬ --б-¬ ¦ ¦ ¦ ¦ а¬ р¬ д¬ р¬ ¦ ¦ ¦ ¦ а а а ¦ ¦ ¦ ¦ ¦ ¦ ¦ 3 ¦ ----а---¬ ¦ абра<к>адабра ¦ ¦ ¦ --р-¬ --б-¬ ¦ ¦ ¦ ¦ а¬ а¬ д¬ р¬ ¦ ¦ ¦ ¦ б к а а ¦ ¦ ¦ ¦ ¦ ¦ L------------+----------------+------------------- Теперь, на основе опыта, полученного при построении дерева из предыдущей таблицы, запишем алгоритм вставки символа в дерево. Пусть k - позиция, в которой должен находиться вставляемый символ, а n - количество символов в дереве. Тогда, так как один символ записан в узле, то количества символов в ветвях: l = ((n-1) shr 1); r = l + (n-1) and 1; <Вставить символ в дерево> - Если дерево пустое, то записываем символ в его корень - Считаем l и r для корня дерева - Определяем, в какую из ветвей должен быть вставлен символ - Если символ вставляется в левую ветвь: - Если l=r, то: - вставляем корень дерева в правое поддерево - заменяем корень дерева на символ с максимальной позицией из левого поддерева - удаляем символ с максимальной позицией из левого поддерева - вставляем символ в левое поддерево - Если символ вставляется в правую ветвь: - Если l - Если удаляемый символ является корнем дерева, то не делаем ничего - Считаем l и r для корня дерева - Определяем, в какой из ветвей находится удаляемый символ - Если удаляемый символ в левой ветви - Если l