Бакнелл Джулиан М.
Шрифт:
Код реализации простой технологии обхода, которая может быть приведена в соответствие с нашими потребностями, показан в листинге 12.26. Подпрограмма содержит два метода: первый вызывается пользователем с указанием имени файла, а второй представляет собой рекурсивную подпрограмму, которая записывает данные в файл. Весь основной объем работы выполняется во второй подпрограмме. Поскольку в матрице путь LCS кодируется в обратном направлении (т.е. для определения пути необходимо начать с конца и продвигаться к началу матрицы), мы создаем метод, который вначале вызывает сам себя, а затем записывает данные, соответствующие текущей позиции. Необходимо обеспечить прерывание выполнения рекурсивной подпрограммы. Это соответствует случаю, когда подпрограмма вызывается для ячейки (0,0). В этом случае никакие данные не записываются в файл. Если индекс строки То равен нулю, мы выполняем рекурсивный вызов, перемещаясь вверх по матрице (индекс строки From уменьшается), и предпринимаемым действием должно быть удаление символа из строки From. Если индекс строки From равен нулю, мы выполняем рекурсивный вызов, перемещаясь по матрице влево, и тогда действием является ставка текущего символа в строку То. И, наконец, если оба индекса не равны нулю, мы находим соответствующую ячейку в матрице, выполняем рекурсивный вызов и записываем действие в файл. Перемещению вниз соответствует удаление, перемещению вправо - вставка, перемещению по диагонали - ни одно из упомянутых действий (символ "переносится" из одной строки в другую). Для обозначения удаления мы будем использовать стрелку, указывающую вправо (-> ), а для обозначения вставки - стрелку, указывающую влево (<-). Перенос символа не обозначается.
Листинг 12.26. Вывод последовательности редактирования
procedure TtdStringLCS.slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
var
Cell : PtdLCSData;
begin
{если оба индекса равны нулю, данная ячейка является первой ячейкой матрицы LCS, поэтому подпрограмма просто выполняет выход}
if (aFromInx = 0) and (aToInx = 0) then
Exit;
{если индекс строки From равен нулю, ячейка расположена в левом столбце матрицы, поэтому необходимо переместиться вверх; этому будет соответствовать удаление}
if (aFromInx = 0) then begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '->', FToStr[aToInx]);
end
{если индекс строки To равен нулю, ячейка расположена в верхней строке матрицы, поэтому необходимо переместиться влево; этому будет соответствовать вставка}
else
if (aToInx = 0) then begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, '< - FFromStr[aFromInx]);
end
{в противном случае необходимо выполнить действия, указанные ячейкой}
else begin
Cell := FMatrix[aFromInx, aToInx];
case Cell^.ldPrev of
ldNorth : begin
slWriteChange(F, aFromInx-1, aToInx);
writeln(F, ' <- ', FFromStr[aFromInx]);
end;
ldNorthWest : begin
slWriteChange(F, aFromInx-1, aToInx-1);
writeln(F, ' ', FFromStr[aFromInx]);
end;
ldWest : begin
slWriteChange(F, aFromInx, aToInx-1);
writeln(F, '-> FToStr[aToInx]);
end;
end;
end;
end;
procedure TtdStringLCS.WriteChanges(const aFileName : string);
var
F : System.Text;
begin
System.Assign(F, aFileName);
System.Rewrite(F);
try
slWriteChange(F, length(FFromStr), length(FToStr));
finally
System.Close(F);
end;
end;
Ниже показан текстовый файл, который был сгенерирован для преобразования слова "illiteracy" в слово "innumeracy".
< - i
<- l
<- l
i
<- t
– > n
– > n
– > u
– > m
e
r
a
с
y
Это представление действий по редактированию легко доступно для понимания, но при необходимости его можно развернуть. Как видите, наиболее длинная общая подпоследовательностью является (i, e, r, a, c, y), а определение удалений и вставок не представляет сложности.
Памятуя о том, что примененный метод является рекурсивным, следует подумать о требуемой для его реализации глубине стека. Если бы строки вообще не имели общих символов, последовательность редактирования сводилась бы к удалению всех символов первой строки и вставке всех символов второй строки. Если первая строка содержит n символов, а вторая m, глубина стека должна быть пропорциональной сумме n + m.
Вычисление LCS двух файлов
После того, как мы ознакомились с решением для двух строк, его можно модифицировать для вычисления LCS и генерации команд редактирования для двух текстовых файлов. Дабы упростить себе задачу, выполним считывание обоих файлов в объект TStringsLists. Понятно, что теперь одновременно выполняется сравнение целых текстовых строк, а не символов, тем не менее, в основном, реализация остается практически той же самой. Код интерфейса и вспомогательных методов приведен в листинге 12.27.
Листинг 12.27. Класс TtdFileLCS
type
TtdFileLCS = class private
FFromFile : TStringList;
FMatrix : TtdLCSMatrix;
FToFile : TStringList;
protected
function slGetCell(aFromInx, aToInx : integer): integer;
procedure slWriteChange(var F : System.Text;
aFromInx, aToInx : integer);
public
constructor Create(const aFromFile, aToFile : string);
destructor Destroy; override;
Жанры
- Романы
- Приключения
- Детективы
- Техно триллер
- Дамский детективный роман
- Исторические детективы
- Классические детективы
- Шпионские детективы
- Триллеры
- Юридический триллер
- Крутой детектив
- Полицейские детективы
- Медицинский триллер
- Иронические детективы
- Боевики
- Криминальные детективы
- Политические детективы
- Маньяки
- Зарубежные детективы
- Прочие Детективы
- Спецслужбы
- Драматургия
- Фантастика
- Хентай
- Ранобэ
- Сянься
- Дорама
- Уся
- Аниме
- Космоопера
- Юмористическая фантастика
- Боевая фантастика
- Героическая фантастика
- Технофэнтези
- Готический роман
- Социально-философская фантастика
- Попаданцы
- Историческая фантастика
- Ироническая фантастика
- Зарубежная фантастика
- Историческое фэнтези
- Юмористическое фэнтези
- Детективная фантастика
- Эпическая фантастика
- Мистика
- Космическая фантастика
- Фантастика: прочее
- Постапокалипсис
- Научная фантастика
- Киберпанк
- Альтернативная история
- Ненаучная фантастика
- РПГ
- Стимпанк
- Ироническое фэнтези
- Ужасы и мистика
- Сказочная фантастика
- Фэнтези
- Городское фэнтези
- Эзотерика
- Проза
- Военная проза
- Легкая проза
- Сентиментальная проза
- Советская классическая проза
- Антисоветская литература
- Афоризмы
- Эпистолярная проза
- Новелла
- Семейный роман
- Рассказ
- Классическая проза
- Эпопея
- Эссе
- Проза прочее
- Повесть
- Магический реализм
- Современная проза
- Контркультура
- Роман
- Историческая проза
- Русская классическая проза
- Феерия
- Стихи и поэзия
- Юмор
- Дом и досуг
- Рыбалка
- Охота
- Здоровье детей
- Домашние животные
- Воспитание детей
- Отдых / туризм
- Зарубежная прикладная литература
- Прочее домоводство
- Прикладная литература
- Домашнее хозяйство
- Кулинария
- Медицина и здоровье
- Сделай сам
- Спорт
- Хобби и ремесла
- Образовательная литература
- Сад и Огород
- Здоровье и красота
- Развлечения
- Коллекционирование
- Секс / секс-руководства
- Образование и наука
- Боевые искусства
- Органическая химия
- Обществознание
- Военная история
- Ветеринария
- Ораторское искусство / риторика
- Физика
- Химия
- Семейная психология
- Военная техника и вооружение
- Иностранные языки
- Прочая научная литература
- Психотерапия и консультирование
- Биохимия
- Cпецслужбы
- Астрономия и Космос
- Школьные учебники
- Учебная и научная литература
- Учебники
- Государство и право
- Психология
- Литературоведение
- История
- Научно-популярная литература
- Политика
- Детская психология
- Юриспруденция
- Шпаргалки
- Педагогика
- Физическая химия
- Медицина
- Биофизика
- Языкознание
- Зарубежная образовательная литература
- Зоология
- Геология и география
- Краткое содержание
- Зарубежная психология
- Саморазвитие / личностный рост
- Технические науки
- Религиоведение
- Военное дело
- Личная эффективность
- Аналитическая химия
- Рефераты
- Экология
- Философия
- Альтернативная медицина
- Математика
- Культурология
- Военное дело: прочее
- Ботаника
- Биология
- Словари и Энциклопедии
- Финансы и бизнес
- Отраслевые издания
- Бухучет и аудит
- Недвижимость
- Деловая литература
- Ценные бумаги
- Внешнеэкономическая деятельность
- Торговля
- Зарубежная деловая литература
- О бизнесе популярно
- Стартапы и создание бизнеса
- Корпоративная культура
- Управление, подбор персонала
- Маркетинг, PR, реклама
- Личные финансы
- Работа с клиентами
- Менеджмент
- Интернет-бизнес
- Поиск работы, карьера
- Малый бизнес
- Делопроизводство
- Государственное и муниципальное управление
- Банковское дело
- Экономика
- Книги по IT
- Техника
- Древние книги
- Документальное
- Прочее
- Интерьеры
- Газеты и журналы
- Театр
- Музыка
- Комиксы / манга
- Зарубежная классика
- Современная зарубежная литература
- Изобразительное искусство, фотография
- Мода и стиль
- Искусство и Дизайн
- Зарубежная литература о культуре и искусстве
- Фанфик
- Подростковая литература
- Шахматы
- Кино
- Культура и искусство
- Недописанное
- Классическая литература
- Без Жанра
- Народные
- Книги Для Детей
- Детские остросюжетные
- Сказки
- Детские стихи
- Прочая детская литература
- Детская образовательная литература
- Книги для дошкольников
- Детская фантастика
- Детские детективы
- Книга-игра
- Детский фольклор
- Буквари
- Детская проза
- Детская познавательная и развивающая литература
- Внеклассное чтение
- Зарубежные детские книги
- Детские приключения