Работа со строками слов (стр. 4 )

(15 баллов)

Задание 8. Модифицируйте проект RemoveExtraBlanks (для получения процедуры RemoveAllWords) так, чтобы действие программы было реверсированным: программа должна записывать только все пробелы и пропускать слова.

(15 баллов)

Задание 9. Обозначив входную строку буквой S, выходную строку программы RemoveExtraBlanks обозначив W, а выходную строку программы RemoveAllWords буквой B, объясните, почему:

Длина (S) ≠ длина(W) + длина (B)

(15 баллов)

Задание 10. Докажите, что реализацией для {вставить пробел, если это не последнее слово} также может являться:

IF Ch <> ‘ ‘

THEN

  WRITE(FileOut, ‘ ‘)

(15 баллов)

Задание 11. Текстовый файл содержит трехзначные числа, разделенные пробелами (одним или несколькими). Числам могут предшествовать нулевые символы (несколько, либо ни одного). Цель: переформатировать файл в файл с разделителями в один пробел, с убиранием ведущих нулей (за исключением числа ноль, который должен выглядеть так: 0).

a) Опишите проблемы с использованием BNF

b) разделите множество входных строк на группы и создайте наборы тестовых данных для каждой группы.

c) Напишите проект программы, решающей данную задачу.

(50 баллов)

Задание 12. Даны 2 строки. Первая строка состоит из пробелов. Вторая – из слов и пробелов. Предположив, что длина первой строки определяет ее ширину, выведите каждое слово из второй строки в отцентрированном (относительно ширины первого слова) виде.

(20 баллов)

10.2 Сортировка строк по словам.

Сортировка слов является более  полезной, нежели по символам. Однако типичные задачи требуют более быстрой методики сортировки, нежели описанные в главе 4. Здесь будет описываться

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

Рассмотрим 400-страничную книгу с 500 словами на странице – книгу из 200 000 слов. Предположим, что в ней есть 3 000 уникальных слов. Каким образом они могут быть найдены? Самым простым способом было бы отсортировать всю книгу целиком, а затем пройтись по отсортированным строкам, выкинуть дубликаты, которые будут собраны вместе после сортировки. На самом деле, это не такая уж элементарная задача.

SelectSort требует n2 операций чтения-записи файла длиной n символов. Предположим, что длина слова, в среднем, 5 символов, а также пробел между каждой парой слов. SelectSort потребует 200000* 200000=4*1010 операций чтения-записи слов и 24*1010 операций чтения-записи символов. Поскольку в году всего лишь 313 360 секунд в году, даже при миллионе операций чтения / записи в секунду эта задача потребует 9 месяцев выполнения, что на практике вовсе не подходит.

Другим способом создания списка слов, могло бы быть сортировка слов на первой странице, удаление дубликатов, затем на второй и т. д. На первой странице будет меньше 500 слов, но большинство из 3000 уникальных слов могут появиться на нескольких первых страницах. Как только это произойдет, на каждой странице необходимо будет отсортировать 3500 слов. В самом худшем случае нам придется сортировать 400 раз по 3500 слов. Количество операций чтения / записи на каждой странице будет равно 3500 * 3500 = 1.225 * 107 , а для всей книги – 3500 * 3500 * 400 = 4.9 * 109 или 2.94 * 1010 операций чтения-записи символов. Что ж, раз в 8 лучше, однако все равно потребует больше месяца выполнения.

Стратегия сортировки, которую мы разработаем в дальнейшем, требует только n * k операций чтения для сортировки файла длиной n символов, где k – наименьшее целое, такое, что

2k >= n

Для n = 200 000, количества слов в книге, количество операций чтения требуемое при такой сортировке будет:

n * k = 200000 * 18 = 3 600 000 (поскольку 218  = 262144 > 200000)/

Опять таки, предположив, что слова у нас в среднем имеют длину 5 символов и должны быть разделены пробелом, сортировка слов потребует 21 600 000 операций считывания символов (немногим больше 21 секунды). Для простоты и сравнения с SelectSort эта новая стратегия сортировки будет разработана для сортировки символов.

10.2.1 Сортировка при помощи разделения и слияния.

Две отсортированные строки могут быть объединены в одну отсортированную строку при помощи циклического сравнивания их первых символов и перемещения символа, который должен быть первым в конец новой строки.

Например, рассмотрим две отсортированные строки:

cow

art

Сначала сравниваются a и c, и a выбирается в качестве начала новой строки, сравнивая c и r, мы добавляем символ c в конец строки. Выполнение пошагового слияния строк показано в следующей таблице:

После выполнения шага	Старые строки	Новая строка
0	cow	art
1	cow	rt	a
2	ow	rt	ac
3	w	rt	aco
4	w	t	acor
5	w	acort
6	acortw

Таким образом, если файл может быть разделен на отсортированные части, называемые сериями (runs), то он может быть отсортирован путем объединения этих серий. Произвольная строка не может быть просто разделена на две серии за один проход, но она может быть разделена  на две строки, каждая из которых содержит несколько серий. Путем повторяющихся операций разделения и слияния может быть получена отсортированная строка. Покажем это на примере. Рассмотрим строку

character,

которая содержит 4 серии: ch, ar, act, er. Разделив символы на 2 новые строки и переключаясь между строками после обработки каждой серии, будут созданы строки:

ch·act

ar·er

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

Объединяя эти строки символ за символом, получим в результате:

После выполнения шага	Старые строки	Новая строка
0	chact	arer
1	chact	rer	a
2	hact	rer	ac
3	act	rer	ach
4	ct	rer	acha
5	t	rer	achac
6	t	er	achacr
7	t	r	achacre
8	t	achacrer
9	achacrert

Склеенная строка теперь содержит 3 серии: ach, acr, ert. Снова разделяем ее на две строки по сериям:

ach·ert

acr

после объединения получим:

aacch·errt

Разделение строк дает:

aacch

errt

И третья операция слияния дает нам сортированную строку:

aaccehrrt

Другой способ слияния – слежение за границами серий и перемещение всех символов в паре серий до рассмотрения следующее пары серий. Для выше упомянутого примера, разделив строку на:

ch·act

ar·er

после слияния мы получим:

aacch·errt

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

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

Сортируемый файл может уже содержать длинные серии, но может и не содержать. В общем случае нам могут быть гарантированы только серии единичной длины – отдельные символы. Если файл будет разделен на чередующиеся символы, то каждый кусочек будет содержать серии единичной длины. Затем они могут быть объединены для получения серий длиной в 2 символа. Разделяя файл на чередующиеся серии длины 2 и, объединяя их, мы получим серии длиной 4 символа и т. д. При этом, случайно возможные серии большей длины игнорируются, однако эта процедура стабильно приближает нас к конечному результату. Мы сможем избежать подсчета длины серий, если обозначим символом # искусственные границы серий. Пример данного процесса показан ниже для строки wrcaot:

Шаг	Разделенные строки	Склеенная строка
w#r#c#a#o#t#
Разделение	w#c#o#	r#a#t#
Слияние	rw#ac#ot#
Разделение	rw#ot#	ac#
Слияние	acrw#ot
Разделение	acrw#	ot#
Слияние	acortw#

Этот процесс прекращается, когда текст содержит одну-единственную серию. Процедура MergeSort1 будет спроектирована с использованием этих идей.

Design part 2

ROCEDURE MergeSort1 (VAR Txt: TEXT);

VAR

  Temp1, Temp2: TEXT;

  Sorted, Ch: CHAR;

{включает в себя процедуру CopyOpen(VAR F1, F2: TEXT)

Копирует строку из F1 в F2 без выполнения RESET и REWRITE;

поэтому F1 должен быть открыт для чтения, а F2 для записи,

а строки прошлого в этих файлах могут не быть пустыми}

BEGIN {MergeSort1}

  {присвоить переменной Sorted значение ‘Y’ если Txt отсортирован, иначе - ‘N’};