Алгоритм Лампеля-Зива

[Оль4ик]

Здравствуйте!
Вот есть такое задание: Написать программу на Delphi, реализующую алгоритм Лемпеля-Зива. Программа должна кодировать исходный текст и определять объем памяти, занимаемый исходным и зашифрованным текстом в байтах.
В качестве пояснения к алгоритму краткая теория: "если в прошедшем ранее выходном потоке уже встречалась подобная последовательность байт, причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина), а не сама последовательность". Например фраза: "КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ" закодируется так: "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ". Я поняла этот алгоритм, но никак не соображу, как это можно реализовать в программе. Не знаю с чего начать. Если кто-нибудь сталкивался с методами шифрования, подскажите идею.

[Smitt&Wesson]

Сталкивался, но боюсь на вашу задачку, сейчас, такой холивар накатит, аж страшно подумать...

[Serge_Bliznykov]

Программа должна кодировать исходный текст и определять объем памяти, занимаемый исходным и зашифрованным текстом в байтах.
....
Если кто-нибудь сталкивался с методами шифрования, подскажите идею.

Вы путаете понятия "кодирования" и "шифрования".
В данном случае ни о каком шифровании речь, разумеется, не идёт, тут чистое кодирование.

Кроме того, не понятно

причем запись о ее длине и смещении от текущей позиции короче чем сама эта последовательность, то в выходной файл записывается ссылка (смещение, длина)

КОЛОКОЛ - семь символов
КОЛО(-4,3) - десять символов.
Вы уверены, что запись о длине и смещении у Вас короче, чем сама последовательность?

[Smitt&Wesson]

Олечка.
Язык. Наработки. Предполагаемое решение. Собственные расуждения.
Скинуть задачку в тексте, много ума не нужно.

[Оль4ик]

Здравствуйте.
Сперва отвечу Сергею Близнякову. Да, я видимо что-то напутала с понятиями "кодирования" и "шифрования".
Вот как я понимаю данный алгоритм.
Берем фразу: КОЛОКОЛ_ОКОЛО_КОЛОКОЛЬНИ.
Читаем по буквам слева направо - в слове КОЛОКОЛ есть повторяющийся слог КОЛ, и он есть точная копия первых 3-х букв данной фразы, и путь к этим буквам лежит в левую сторону (поэтому знак "-"), который составляет четыре знака. Получаем (-4,3).

Читаем фразу дальше, в слове ОКОЛО опять видим повторяющуюся последовательность букв которая встречалась ранее - это слог ОКОЛ (мы его встречали в слове КОЛОКОЛ). Значит смещение составит пять знаков влево "-5", а количеств букв в слоге ОКОЛ четыре. Получаем (-5,4).

Читаем фразу дальше, в слове КОЛОКОЛЬНИ опять видим повторяющуюся последовательность букв которая встречалась ранее - это слог КОЛОКОЛ (да это же первые 7 букв нашей фразы!). Значит смещение составит четырнадцать знаков влево "-14", а количеств букв в слоге КОЛОКОЛ семь. Получаем (-14,7).

Тот материал для объяснения, который давал нам преподаватель я нашла тут http://naukoved.ru/content/view/842/35/

[Serge_Bliznykov]

Сперва отвечу Сергею Близнякову

я - Близнюков.

Да, я видимо что-то напутала с понятиями "кодирования" и "шифрования".

есть маленько. Но это не страшно, если Вы поняли разницу. В следущий раз уже не спутаете.

Вот как я понимаю данный алгоритм.

угу. согласен. в принципе правильно понимаете.

Вы зря расшифровываете. Из первого поста было всё понятно.
Единственное, что у меня вызвало сомнение, так это то, что у Вас не соблюдается условие минимизации длины - текст после такой замены, как приведено в вашем примере не сжимается, а наоборот, становится длинее.
Впрочем, на самом деле, конечно, смещение и длина хранятся не в виде строковых величин, что и даёт выигрыш. Но тогда возникает вопрос, как Вы собираетесь определить объём памяти, занимаемый кодированным текстом.
Вот, например, "КОЛО(-4,3)_(-5,4)О_(-14,7)ЬНИ" сколько занимает?

[Stilet]

как Вы собираетесь определить объём памяти, занимаемый кодированным текстом.

А какая разница? Определить фиксированный словарь, а потом уж разбираться хватит его или нет для текста.

[Serge_Bliznykov]

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

А какая разница? Определить фиксированный словарь, а потом уж разбираться хватит его или нет для текста.

чтобы решить поставленную задачу..

Программа должна кодировать исходный текст и определять объем памяти, занимаемый исходным и зашифрованным текстом в байтах.

[Stilet]

Ну так как я понимаю объем определять потом?
В любом случае это все теория. Я на практике реализации алгоритма еще не видел.

[Serge_Bliznykov]

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

Ну так как я понимаю объем определять потом?
В любом случае это все теория. Я на практике реализации алгоритма еще не видел.

Дык это же 100% УЧЕБНАЯ задача.
Задача состоит в том, чтобы студент понял АЛГОРИТМ сжатия на конкрентном примере.