нужен код на делфи

← →
Veniamin (2005-11-21 20:22) [0]

Здравствуйте уважаемые форумчане!!! Помогите пожалуйста написать код на делфи для курсовой (скоро сдавать :( ) или напишите похожий код хотя бы для создания словаря. Или у кого есть исходники по алгоритмам сжатия текстов - выложите пожалуйста ссылки.

Вот исходное задание курсовой:

Меньше copy – меньше и вздору.

или…
ИЗБЫТОЧНОСТЬ ТЕКСТА
И СЖАТИЕ ФАЙЛА

Все знают, что большинству людей свойственно излишнее многословие. Гораздо менее широко известно, что даже самые лаконичные высказывания можно было бы значительно сократить. Вообще, естественные языки отличаются чрезвычайной избыточностью. Даж есл нсклко бкв вбрсть, эт прдлжн ещ мжн прчть. Языки, используемые для вычислений, обладают той же особенностью. Для экономии памяти компьютера, объем которой ограничен, имеет смысл ликвидировать избыточность текста.

Существует несколько способов уплотнения текста. Самый очевидный из них – поиск различных по длине цепочек из одной повторяющейся литеры. Такая группа может быть заменена тройкой литер mcn, где m обозначает признак повторения, специальную литеру, не используемую нигде в тексте для других целей, c – сама повторяющаяся литера и n – длина цепочки. Один такой триграф экономит n – 3 литер, причем значение n не может превышать максимального числа, представимого в поле одной литеры. Описанный способ обработки весьма неплохо оправдывает себя для текстов, содержащих длинные цепочки повторяющихся литер, например длинные цепочки пробелов, характерных для большинства программ. К сожалению, этот прием не столь хорош для других текстов, поскольку большинство данных не отличается такой же строгой формой записи, как программы.

Второй способ основан на том, что в различных системах кодировки литер, применяемых на ЭВМ, большинство литер практически не используется (из 256 литер обычного 8-разрядного кода, как правило, употребляется лишь около 100). Сначала в тексте разыскиваются наиболее распространенные диграфы, и каждому из них ставится в соответствие одна из не используемых в тексте одиночных литер. Уплотнение текста производится при просмотре его слева направо путем последовательной замены выявленных диграфов их однолитерными эквивалентами. При этом может быть достигнута значительная экономия, поскольку, например, 150 наиболее часто встречающихся диграфов уже составляют большую долю текста на естественном языке. И если не ставить целью слишком высокую степень уплотнения текст, можно написать довольно эффективные программы кодирования и декодирования, работающие с машинным представлением литер.

← →
Veniamin (2005-11-21 20:23) [1]

(продолжение...)
Однако существуют все же определенные трудности. Кто сказал, что наиболее часто встречающиеся диграфы в английском тексте должны быть теми же, что и во французском, или в наборе файлов, содержащих почтовые адреса, или в тексте на Алголе? А если даже это и так, то как насчет триграфов, квадриграфов или более длинных групп? Ведь более длинные группы, даже если они и реже встречаются, дают большую экономию, а бывает, что определенный фрагмент появляется в большом куске текста намного чаще, чем можно было бы ожидать. И, возвращаясь назад, как подсчитать частоты появления диаграфов?

Ответ на все эти вопросы содержится в третьем подходе к решению исходной задачи. Вместо того чтобы употреблять некоторый, заранее заданный набор кодировок, можно на ходу генерировать кодовый словарь, используя непосредственно текст, подлежащий сжатию, или выборку из него. Поскольку при этом каждый элемент текста будет участвовать в создании своего собственного словаря, исчезнут трудности, вызванные неудачными аббревиатурами. Теперь нам надо найти способ построения такого словаря.

Опишем наш план действий в общих чертах. Начинаем с пустого словаря. Текст просматриваем слева направо. Ищем в словаре гнездо возможно большей длины, совпадающее с головной частью текста, и увеличиваем счетчик частоты соответствующего гнезда словаря. Если совпадений цепочек нет, образуем новое гнездо словаря и помещаем туда первую букву текста. Вычеркиваем обработанную цепочку из начала текста и начинаем просмотр заново. При обстоятельствах, поясняемых ниже, иногда два гнезда словаря соединяются в одно, образуя цепочку большей длины – процесс укрупнения гнезд. Когда словарь переполняется, производим его чистку, удаляя наиболее редко встречающиеся гнезда, и продолжаем просмотр. После того как частоты гнезд встречаемости словаря стабилизируются, вводим таблицу кодировок и, взяв исходный текст, полностью его кодируем.

В предложенной схеме есть два невыясненных момента: каким образом происходит укрупнение гнезд словаря и как осуществляется его чистка? Укрупнение двух гнезд словаря производится в случае, когда одно из них следует в тексте непосредственно за другим и частоты обоих гнезд превышают некоторое пороговое значение. При этом, чтобы новое гнездо словаря не подвергалось ближайшей чистке, ему может быть приписана начальная частота несколько выше обычной. Таким образом, если в словаре уже имеются, например, цепочки КОН т ТАКТ, то при условии, что содержимое их счетчиков достаточно велико, может образоваться новое гнездо словаря, содержащее цепочку КОНТАКТ. Что же касается чистки словаря, то существует простой способ – удалять все те гнезда, значения счетчиков которых меньше среднего. Можно действовать и иначе – выбрасывать все гнезда, частота которых ниже медианы частот. Годятся и другие, подобные этому способы.

Алгоритм построения словаря
В приводимом алгоритме предполагается, что построение словаря производится с помощью некоторой выборки из текста, подлежащего сжатию. Для алгоритма существенны все литеры текста, и если табуляция, концы строк и другие аналогичные элементы имеют значение, то в тексте должны присутствовать соответствующие управляющие литеры. Предполагается, что в начале работы словарь пуст. В начальный момент переменная last match содержит пустую цепочку, а переменная last count имеет значение, равное нулю.
1. Ищем в головной части входного текста возможно более длинную цепочку match, совпадающую с каким-нибудь гнездом словаря. Если переменная match пустая, засылаем в нее первую литеру входного текста, помещаем в свободное гнездо словаря и устанавливаем начальное значение счетчика этого нового гнезда равным единице. Если цепочка match не пустая, увеличиваем на единицу счетчик соответствующего гнезда словаря. Содержимое счетчика этого гнезда записываем в count.

2. Если либо count, либо last count меньше значения порога укрупнения гнезд, то переходим к шагу 4. Порог укрупнения определяется как отношение максимально допустимого объема словаря к числу оставшихся на данный момент свободных гнезд.

3. Образуем новое гнездо словаря путем объединения цепочек last match и match. Поскольку данное гнездо словаря возникло впервые, засылаем в его счетчик единицу. Можно применить и другие стратегии.

4. Если в словаре остались свободными менее двух гнезд, производим чистку, удаляя все гнезда с частотами меньше медианы частот. При этом, если окажется, что исключилось гнездо, содержащее match, устанавливаем count равным нулю.

5. Вычеркиваем match из начала входного текста. Если текст исчерпан, то алгоритм работу заканчивает – выход. В противном случае помещаем last match в match, пересылаем last count в count и возвращаемся к шагу 1.

← →
Veniamin (2005-11-21 20:25) [2]

(продолжение2...)
Кодирование и декодирование
Как только построение словаря завершилось, необходимо составить таблицы дл кодирования и декодирования. Образуем все возможные диграфы, начинающиеся с литеры, которая нигде в тексте не используется. Исключим из словаря все гнезда, состоящие из одной или двух литер (их уплотнение экономии дать не может). Упорядочим встречающиеся цепочки по частоте встречаемости. Поставим в соответствие гнездам словаря полученные выше кодирующие диграфы, начиная с гнезд, имеющих наибольшую частоту. Формирование таблицы кодировок завершается по исчерпании гнезд словаря или набора диграфов.

Процесс кодирования текста подобен процедуре построения словаря. На каждом этапе головная часть входного текста проверяется на совпадение в возможно большем числе позиций с гнездами словаря. Совпавшая цепочка заменяется в тексте соответствующим кодирующим диграфом, и начало просмотра входного текста сдвигается на длину выделенной цепочки. Если же в словаре не найдено нужного гнезда, в выходной текст просто переносится первая литера из головной части входного текста и начало просмотра перемещается вправо на одну позицию. Декодирование осуществляется путем простой замены кодирующих диграфов их эквивалентами из словаря.

Тема. Напишите программу, реализующую описанные выше алгоритмы построения словаря, кодирования и декодирования. Проверьте программу на достаточно больших фрагментах текста на естественном языке и языке программирования. Коэффициент сжатия данного куска текста определяется как частное отделение суммы длин сжатого текста и словаря на длину исходного текста. Проведите небольшое исследование зависимости коэффициента сжатия от какого-нибудь из следующих параметров: языка уплотняемого текста; объема используемой для упражнения выборки из текста; длины словаря при его построении; имеющегося количества кодирующих диграфов или применимости словаря, полученного на основании одного текста, для другого текста на том же языке.

Указания исполнителю. Данная задача интересна тем, что для ее эффективного решения требуется употребить некоторые весьма развитые алгоритмы и структуры данных. Однако пусть не столь эффективную, но правильно работающую программу можно написать, используя простые алгоритмы и структуры, которые можно, когда программа заработает, постепенно заменять более изящными конструкциями. Одним из примеров служит вычисление медианы для чистки словаря. В качестве первого варианта можно просто выбрасывать гнезда словаря с частотами, меньшими средней. При этом среднюю частоту легко вычислить за один полный просмотр всех частот словаря. А после того как такая программа в целом заработает, можно уже для нахождения порога исключения строк подключить более сложную программу расчета медианы.

Другим примером является выбор структуры словаря на этапах его создания и кодирования. Если гнезда словаря расположить в случайном порядке, то при проверках на совпадение необходимо проходить весь словарь. Однако при такой структуре появляющиеся новые гнезда добавляются просто в конец словаря. Небольшое усложнение могло бы заключаться в группировке гнезд словаря по их длинам. Тогда поиск мог бы осуществляться в направлении от самых длинных групп к коротким и прекращаться при первом же удачном сравнении. Если каждую группу и лексикографически упорядочить, то можно было бы воспользоваться вместо линейного поиска внутри группы двоичным поиском, экономя таким образом время. Но зато добавление в словарь новых гнезд становится в этом случае более сложным, так как для любого нового гнезда потребуется место, скорее всего, где-то в середине группы. Не исключено, что самой выгодной структурой для организации поиска окажется какая-либо разновидность дерева. Разыскиваемую цепочку словаря могла бы тогда составить последовательность букв по пути от корня дерева к его листьям, или, иначе говоря, в узлах некоего подобия двоичного дерева поиска могли бы располагаться соответствующие строки словаря. В то же время при составлении словаря деревья потребуют намного большей обработки, нежели описанные выше более простые структуры.

← →
Virgo_Style © (2005-11-21 20:37) [3]

http://www.torry.net/quicksearchd.php?String=compression&Title=Yes

Если принимать будет автор этого текста - быстрее будет написать и сдать, чем содрать и сдать.
Ну и лучше, конечно.

← →
Veniamin (2005-11-22 13:22) [4]

Virgo_Style © нет, я не из Москвы. а много написал, чтобы подробно. само задание курсовой так выглядит, не в одну строчку.

← →
SDA (2005-11-22 13:33) [5]

ДДДаа...., попал ты, я помню такую херню сдавал на 3-м курсе, предмет, кажется, назывался ТСВПС (теория сложности вычислительных процессов и структур), только писать надо было на ТР7+Turbo Vision... :) Время тогда другое было... самый головняк, на сколько я помню, это реализация алгоритма быстрого поиска по тексту... (КМП и ВМ помоему были...) ... бля, даже вспоминать боюсь... Veniamin а ты откуда???

← →
Плохиш © (2005-11-22 13:34) [6]

> Veniamin (21.11.05 20:22)

Ты предлагаешь нам этот текст весь прочитать? Нафик, нафик.

← →
alex_*** © (2005-11-22 13:34) [7]

ну ты бы своими словами сформулировал для начала. Хоть сам может поймешь. А то делать нечего как вчитываться в твои опусы

← →
Leonid Troyanovsky © (2005-11-22 13:42) [8]

> Плохиш © (22.11.05 13:34) [6]

> Ты предлагаешь нам этот текст весь прочитать? Нафик, нафик.

А чего - хороший текст.
Чарльз Уэзерел, Этюды для программистов.
Издана была где-то 70-х.

Кста, 2Veniamin - там и исходники были на PL/1 или фортране.

--
Regards, LVT.

← →
Плохиш © (2005-11-22 13:44) [9]

> Leonid Troyanovsky © (22.11.05 13:42) [8]
> А чего - хороший текст.
> Чарльз Уэзерел, Этюды для программистов.

Да? Хм, тогда почитаю :-)

← →
SDA (2005-11-22 13:44) [10]

> Кста, 2Veniamin - там и исходники были на PL/1 или фортране.

:) ага... ему это поможет... еще бы на лиспе были бы исходники... Car(Cdr...)

← →
Игорь Шевченко © (2005-11-22 14:16) [11]

Leonid Troyanovsky © (22.11.05 13:42) [8]

Опередил :)

> Кста, 2Veniamin - там и исходники были на PL/1 или фортране.

на XPL

← →
Veniamin (2005-11-23 13:44) [12]

SDA из ХМАО, Сургут. помогите решить задачу. я понимаю ее так: необходимо убрать некотрые буквы или сочетания букв в тексте, при этом чтобы текст еще оставался читабельным. и потом смочь это все восставновить в исходный текст. если у кого есть исходный текст чего то подобного или такой на Паскале или на Делфи буду благодарен. если необходимо, отблагодарю материально. у меня есть идея - посчитать кол-во вхождений каждой буквы в текст, найти максимум, удалить несколько таких букв , максимально часто встречающихся в тексте, при этом он останется читабельным, но опять же проблема - запоминать позицию кажой буквы в тексте для воостановления исходного текста, а если текст на мегабайт - вообще караул!!!

← →
Venaiamin (2005-11-23 23:34) [13]

SDAсам сейчас на 3-м курсе. необходимо сделать до января. выше постом написал идею алгоритма, чувствую что идею которую сам написал - не самый лучший вариант, но по-другому не знаю как. если есть возможность, посоветуйте что-нибудь. или есть исходник, или алгоритм из книжки Ч. Уэзерелла можно перевести хотя бы на Паскаль.

← →
Venaiamin (2005-11-25 00:29) [14]

Leonid Troyanovsky У вас есть исходники из этой книги?

← →
Игорь Шевченко © (2005-11-25 00:54) [15]

Ты написал весь алгоритм, которого достаточно для того, чтобы заняться реализацией. Исходники есть в упомянутой книжке ("Этюды для программистов"). На XPL. Нет смысла их искать, на Delphi они все равно не странслируются без переделки.

Преподавателю - почет и уважение за интересную задачу.

← →
Venaiamin (2005-11-25 22:25) [16]

Игорь Шевченко алгоритм то написан, но деревья то я не то что бы не понимаю, но задачи по ним не решали. Нам просто на 2м курсе дали теорию и все, а как таковых задач на динамику не было. Стоп! Вы имеете ввиду алгоритм из курсовой или то как я понимаю задачу своими словами и написал свою идею решения? Если второе, то я уже пишу, а первое - не знаю как написать, опять же не имея навыка в задачах с деревьями.

Venaiamin (25.11.05 22:25) [16]

В описании полностью описан алгоритм решения задачи сжатия текста.
Деревья здесь не нужны, все решается массивами.

← →
Venaiamin (2005-11-25 23:43) [18]

Игорь ШевченкоДеревья здесь не нужны, все решается массивами. можно на этом месте пожалуйста поподробнее

← →
Venaiamin (2005-11-26 14:27) [19]

Игорь Шевченкозагнать в массив весь текст политерно и уже обрабатывать или создавать массив слов и уже с ними работать?

← →
упаковщик (2005-11-26 14:57) [20]

Метод Хаффмана:
http://algolist.manual.ru/compress/standard/huffman.php

Внизу смотри ссылку на реализацию на Паскале.

← →
Venaiamin (2005-11-27 13:57) [21]

упаковщик а попроще нету алгоритма? там же динамика, Игорь Шевченко говорит что можно решить массивами, но что, куда, мне вкратце бы рассказали, а реализацией сам займусь!

← →
упаковщик (2005-11-27 14:35) [22]

> Veniamin (23.11.05 13:44) [12]
> я понимаю
> ее так: необходимо убрать некотрые буквы или сочетания букв
> в тексте, при этом чтобы текст еще оставался читабельным.
>

Для востановления, таким образом сжатого текста, потребуется ИИ.

Есть ещё RLE (Групповое кодирование), но этот метод тексты практически не сжимает. Хотя этот метод и прост в реализации, но тебе не подходит.

А судя по заданию, где говорится о подсчёте частот вхождений символов для построения словаря, кстати, то же самое должно использоваться и при востановлении исходного текста - без древовидной структуры не обойтись.

Просто изучи готовые алгоритмы и создай нечто в упрощёном варианте.

← →
упаковщик (2005-11-27 14:43) [23]

Вот очень простой алгоритм по методу LZW: http://algoritms.ru/9.html
Перепиши на Паскале и всё:)

нужен код на делфи Найти похожие ветки