|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
25.11.2012, 13:51 | #1 |
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
алгоритм BWT. List<string>.qSort / Array(char).BubbleSort
Доброго времени суток!
Реализовываю алгоритм 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) Из-за другой моей ошибки Код:
Последний раз редактировалось Lime; 25.11.2012 в 13:59. |
25.11.2012, 13:57 | #2 | ||||
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
в 1 сообщение не поместилось.
Для примера, исходный текст: Цитата:
Цитата:
Цитата:
p.s. http://msdn.microsoft.com/ru-ru/libr...=vs.90%29.aspx Цитата:
p.p.s. Если применить вандальный способ сравнения противоречащий всей идее алгоритма Код:
Код:
Как такое возможно? Последний раз редактировалось Lime; 25.11.2012 в 16:53. |
||||
26.11.2012, 11:52 | #3 |
Форумчанин
Регистрация: 01.10.2008
Сообщений: 248
|
а почему ты не используешь обычное сравнение?
iChar > jChar
Контакты
skype, почта: bm@kwax.ru |
26.11.2012, 13:27 | #4 |
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
Спасибо, надо будет попробовать, но я предположил что в таком варианте они будут сравниватся согласно их байтовому значению, либо по номеру в таблице.
Так-же такой вариант предполагает тройную проверку (>,==,<) при каждой итерации upd: использование "прямого"(>,==,<) сравнения не решило проблему. Некоторые знаки по прежнему сравниваются по разному. Кажется стоит найти способ лексикографического сравнения символов. Кто может подсказать направление поиска, а может и решение?) Последний раз редактировалось Lime; 26.11.2012 в 13:40. |
26.11.2012, 13:35 | #5 |
Форумчанин
Регистрация: 01.10.2008
Сообщений: 248
|
только двойную
сначала == // кстати выполняется быстрее чем больше/меньше потом > else не проверяет
Контакты
skype, почта: bm@kwax.ru |
26.11.2012, 14:01 | #6 | |
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
Цитата:
Код:
Текст прописными, с некоторыми знаками, трансформирует верно (идентично с методом BWT). Текст с заглавными буквами и более редкими знаками трансформирует по прежнему неправильно в результате сортировки по другим правилам. В описании алгоритма предполагается лексикографический порядок сортировки. На MSDN в описании метода сравнения знаков (char.CompareTo()) пишется обратное. А именно что сравнение проходит не по лексикографическому правилу. Видимо в этом и есть вся проблема... |
|
26.11.2012, 14:06 | #7 |
Форумчанин
Регистрация: 01.10.2008
Сообщений: 248
|
лексикографический порядок это который для тебя?
сравнение осуществляется согласно таблице кодировки это правило можно переопределить для этого и есть интерфейс IComparable
Контакты
skype, почта: bm@kwax.ru |
26.11.2012, 14:24 | #8 | |
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
Лексикографический порядок
BWT wiki(eng) Цитата:
Но кроме BWT(byte[]), где в сравнении двух байтов не должно быть проблем и разногласий, нужен так-же BWT(string). Последний раз редактировалось Lime; 26.11.2012 в 14:34. |
|
26.11.2012, 14:27 | #9 |
Форумчанин
Регистрация: 01.10.2008
Сообщений: 248
|
что больше
'a' 'B' ? ознакомься с таблицами кодировки Windows-1251(по умолчанию для русского языка): http://upload.wikimedia.org/wikipedi.../41/Ascii1.gif http://upload.wikimedia.org/wikipedi.../d7/Ascii2.gif
Контакты
skype, почта: bm@kwax.ru Последний раз редактировалось masax; 26.11.2012 в 14:34. |
26.11.2012, 14:41 | #10 | |
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
Цитата:
полное сравнение строка1 строка2 в качестве string дает один результат посимвольное сравнение строка1[i] строка2[i] дает другой результат. Всё это в рамках C# (код я приводил выше, в качестве вандальных модификаций). http://sheepsystems.com/bookdog/Help...icalOrder.html Вот тут например можно увидеть что < и > находятся внутри алфавита по порядку, а в ASCII по вашей ссылке их номера предшествуют символам алфавита в в нижнем и верхнем регистре. То-же самое я увидел и на примере программы. Добавляя в текст БОЛЬШИЕ буквы результат трансформации начинает отличатся. так-же и со знаками. В приведенной ссылке видно почему (2рой столбец) |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
String в array of Char и обратно. | _PROGRAMM_ | Общие вопросы Delphi | 4 | 22.11.2011 22:10 |
Алгоритм BWT | Farrel | Общие вопросы C/C++ | 1 | 26.02.2011 16:32 |
builder string to char array | 6AZblJlb | C++ Builder | 4 | 05.11.2010 20:10 |
array of char -> string | Valkiria | Общие вопросы Delphi | 5 | 04.10.2007 10:40 |
Преобразовать из string в array of char | vitalik007 | Общие вопросы Delphi | 6 | 07.09.2007 01:15 |