алгоритм BWT. List<string>.qSort / Array(char).BubbleSort

[Lime]

Доброго времени суток!

Реализовываю алгоритм BWT. Прямая реализация "В ЛОБ" с составлением матрицы, сортировкой и возвращением последнего столбца работает.
НО при среднем/большом обьеме данных памяти на сортировку приходится выделять Pow(datasize,2), к томуже сортировка требует больше ресурсов и времени.
В следствии чего решил написать "быструю" реализацию алгоритма, использующую вместо целой "матрицы" лишь индексы.
Про BWT можно почитать на вики, тут и тут.

Суть "улучшенного" алгоритма такова:
Получить последний столбец предполагаемой матрицы.
Запомнить каждому char'y его изначальный номер столбца.
Отсортировать строки соответствующие последнему столбцу(и его втч) используя любой алгоритм сортировки, а в качестве сравнения использовать char.CompareTo(char value).
выдать отсортированный последний столбец.

Проблема заключается в том что в 1 варианте "в лоб" используется List<string>Sort();. При этом алгоритм сортировки - qsort, и сравниваются строки. string.CompareTo(string)
В моей версии алгоритм пузырьковой сортировки (да, знаю, неэффективный, но сейчас не о нем) и поочередное сравнение символов char.CompareTo(char).
В следствии чего результаты иногда немного отличаются (в основном при добавлении в исходный текст различных символов).
Внимание вопрос, почему результаты отличаются?
1) Из-за использования неустойчивого(qSort) и устойчивого(BubbleSort) алгоритмов сортировки
2) Из-за разных правил сравнения char-ов отдельно и в string
3) Из-за другой моей ошибки

//BWT "в лоб"
        public string BWT(string text, ref int opos)
        {
            List<string> MX = new List<string>();
            string res = "";
            for (int i = 0; i < text.Length; i++)
            {
                MX.Add(text.Substring(i) + text.Substring(0, i));
            }
            MX.Sort();
            opos = MX.IndexOf(text);
            for (int i = 0; i < text.Length; i++)
            {
                res += MX[i][text.Length-1];
            }
            return res;
        }

        struct xchar
        {
            public char C;
            public int N;
            public xchar(char c, int n)
            {
                this.C = c;
                this.N = n;
            }

        }

        private void SwapElements(List<xchar> list, int pos1, int pos2)
        {
            xchar temp = list[pos1]; list[pos1] = list[pos2]; list[pos2] = temp;
        }
        private char GetMXChar(string unEncoded,int row,int col,int un_Len)
        {
            return unEncoded[(/*-*/row + col + un_Len) % un_Len];
        }

        public string BWT_fast(string text, ref int strpos)
        {
            int txtlen = text.Length;
            string lastcol_unsorted = text[txtlen - 1] + text.Substring(0, txtlen - 1);
            
            List<xchar> RES = new List<xchar>(txtlen);
            for (int i = 0; i < txtlen; i++)
            {
                RES.Add(new xchar(lastcol_unsorted[i], i));
            }
            //bubblesort
            int rowpos = 0; bool rowsolution = false; char iChar, jChar;
            for (int i = txtlen - 1; i > 0; i--)
            {
                for (int j = i - 1; j >= 0; j--)
                {
                    rowpos = 0; rowsolution = false;
                    while ((rowsolution == false) && (rowpos < txtlen))
                    {
                        iChar = GetMXChar(text, RES[i].N, rowpos, txtlen);
                        jChar = GetMXChar(text, RES[j].N, rowpos, txtlen);
                        int csol = iChar.CompareTo(jChar);
                        if (csol < 0)// j > i
                        {
                            rowsolution = true;
                            SwapElements(RES, i, j);
                        }
                        if (csol == 0)//знаки под индексом rowpos строк i,j одинаковы.
                        {
                            rowpos++;
                        }
                        if (csol > 0)
                        {
                            rowsolution = true;
                        }
                    }
                }
            }

            string res = "";
            for (int i = 0; i < txtlen; i++)
            {
                res += RES[i].C;
            }
            return res;
        }

Спасибо за внимание и ответы!

[Lime]

в 1 сообщение не поместилось.
Для примера, исходный текст:

List<string> MX = new List<string>();

BWT

Xw>=>()tt ggnnnrrLL; iittii<<sssseM

BWT_fast

Xw>=>()tt gg; MnnnrrLL iittii<<sssse

p.s. http://msdn.microsoft.com/ru-ru/libr...=vs.90%29.aspx

Сравнение, выполненное с помощью данного метода, основывается на закодированных значениях данного экземпляра и value, а не на их лексикографических характеристиках.

Возможно 4тый вариант ошибки?
p.p.s. Если применить вандальный способ сравнения противоречащий всей идее алгоритма

string iChar, jChar;
//-- вырезано --
iChar = GetMXrow(text, RES[i].N, txtlen);
jChar = GetMXrow(text, RES[j].N, txtlen);
int csol = string.Compare(iChar, jChar);

То результат сходится, но если же сравнивать отдельно символы этих строк под одинаковыми индексами, все тем-же методом, то результат снова отличается.

string iChar, jChar;
//-- вырезано --
iChar = GetMXrow(text, RES[i].N, txtlen)[rowpos].ToString();
jChar = GetMXrow(text, RES[j].N, txtlen)[rowpos].ToString();
int csol = string.Compare(iChar, jChar);

Но ведь строки всегда одинаковой длинны (что для лексикографического сравнения важно) и различаются только позицией элементов(знаков).
Как такое возможно?

[masax]

а почему ты не используешь обычное сравнение?
iChar > jChar

[Lime]

Сообщение от masax

а почему ты не используешь обычное сравнение?
iChar > jChar

Спасибо, надо будет попробовать, но я предположил что в таком варианте они будут сравниватся согласно их байтовому значению, либо по номеру в таблице.
Так-же такой вариант предполагает тройную проверку (>,==,<) при каждой итерации

upd: использование "прямого"(>,==,<) сравнения не решило проблему. Некоторые знаки по прежнему сравниваются по разному.
Кажется стоит найти способ лексикографического сравнения символов.
Кто может подсказать направление поиска, а может и решение?)

[masax]

только двойную
сначала == // кстати выполняется быстрее чем больше/меньше
потом >
else не проверяет

[Lime]

Сообщение от masax

только двойную
сначала == // кстати выполняется быстрее чем больше/меньше
потом >
else не проверяет

Ну подразумевалось сравнение (а в коде конечно же ==, я позже исправил сообщение).

if (jChar > iChar)// RES[j] > RES[i]
                        {
                            rowsolution = true;
                            SwapElements(RES, i, j);
                        }
                        if (jChar == iChar)//знаки под индексом rowpos строк i,j одинаковы.
                        {
                            rowpos++;
                        }
                        if (jChar < iChar)
                        {
                            rowsolution = true;
                        }

Однако результат всё тот-же.
Текст прописными, с некоторыми знаками, трансформирует верно (идентично с методом BWT).
Текст с заглавными буквами и более редкими знаками трансформирует по прежнему неправильно в результате сортировки по другим правилам.

В описании алгоритма предполагается лексикографический порядок сортировки. На MSDN в описании метода сравнения знаков (char.CompareTo()) пишется обратное. А именно что сравнение проходит не по лексикографическому правилу.
Видимо в этом и есть вся проблема...

[masax]

лексикографический порядок это который для тебя?
сравнение осуществляется согласно таблице кодировки
это правило можно переопределить
для этого и есть интерфейс IComparable

[Lime]

Лексикографический порядок
BWT wiki(eng)

The transform is done by sorting all rotations of the text in lexicographic order, then taking the last column. For example, the text "^BANANA|" is transformed into "BNN^AA|A"

Возможно это было использовано лишь для примера (а так-же в двух других источниках).
Но кроме BWT(byte[]), где в сравнении двух байтов не должно быть проблем и разногласий, нужен так-же BWT(string).

[masax]

что больше
'a' 'B' ?


ознакомься с таблицами кодировки Windows-1251(по умолчанию для русского языка):
http://upload.wikimedia.org/wikipedi.../41/Ascii1.gif
http://upload.wikimedia.org/wikipedi.../d7/Ascii2.gif

[Lime]

Сообщение от masax

что больше
'a' 'B' ?


ознакомься с таблицами кодировки Windows-1251(по умолчанию для русского языка):
http://upload.wikimedia.org/wikipedi.../41/Ascii1.gif
http://upload.wikimedia.org/wikipedi.../d7/Ascii2.gif

Выше я уже писал о некоем парадоксе
полное сравнение
строка1
строка2
в качестве string дает один результат
посимвольное сравнение строка1[i] строка2[i] дает другой результат.
Всё это в рамках C# (код я приводил выше, в качестве вандальных модификаций).

http://sheepsystems.com/bookdog/Help...icalOrder.html
Вот тут например можно увидеть что < и > находятся внутри алфавита по порядку, а в ASCII по вашей ссылке их номера предшествуют символам алфавита в в нижнем и верхнем регистре.
То-же самое я увидел и на примере программы. Добавляя в текст БОЛЬШИЕ буквы результат трансформации начинает отличатся. так-же и со знаками. В приведенной ссылке видно почему (2рой столбец)