Построение_кодов

1. ФУНКЦИИ MS EXCEL ДЛЯ РАБОТЫ С ТЕКСТОМ

2. Мастер функций (новые версии)

Вызов мастера функций осуществляется при помощи кнопки на ленте
(в новых версиях) или панели (в старых версиях) инструментов.
2

3. Мастер функций (новые версии)

Для каждой функции показывается краткое описание назначения.
Для каждого аргумента функции также приведено краткое описание.
При указании адреса ячейки для того или иного аргумента мастер
функций показывает как значение аргумента в указанной ячейке,
так и значений функции, которое будет получено при использовании
данного аргумента.
3

4. Мастер функций (старые версии)

Внешний вид окон диалога Мастера функций весьма консервативен и
соответствует внешнему виду предыдущих версий электронных
таблиц MS Excel (в версиях до 2003 года включительно вместо ленты
инструментов использовались панели инструментов).
4

5. Мастер функций (лента инструментов)

Различные функции как на ленте инструментов, так и в мастере
функций сгруппированы по нескольким категориям.
5

6. Мастер функций (строка ввода формул)

Мастер функций может быть вызван также непосредственно в
процессе ввода формул в ячейку либо из строки ввода формул.
В приведенном примере в ячейке B2 показана функция ДЛСТР,
определяющая длину строки, которая имеет один аргумент – адрес
ячейки со строкой текста (в данном примере – ячейка B1).
Возвращаемое значение зависит от вида функции и может быть
числом, текстовой строкой или сообщением об ошибке.
6

7. Краткое описание текстовых функций

ДЛСТР(текст)
Категория – текстовые функции
Возвращает длину строки текста, заданного первым и
единственным аргументом.
ПСТР(текст;начальный_номер;количество_символов)
Категория – текстовые
Извлекает из строки текста, заданной первым аргументом,
начиная с позиции, заданной вторым аргументом,
столько символов, сколько указано в третьем аргументе.
7

8. Краткое описание текстовых функций

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

9. Краткое описание текстовых функций

СЦЕПИТЬ(текст1;текст2;…)
Категория – текстовые
Объединяет несколько (от одного до тридцати)
текстовых аргументов в один текст.
НАЙТИ(найти_текст;внутри_текста;начальный_номер)
Категория – текстовые
Ищет первый текстовый аргумент внутри второго текстового
аргумента, начиная с позиции, указанной в третьем
аргументе. Если текст найден, возвращается номер позиции,
с которой начинается найденный текст, иначе возвращается
сообщение об ошибке #ЗНАЧ!.
9

10. Краткое описание текстовых функций

Если одна из объединяемых ячеек является пустой, т.е. не содержит
никаких символов, то она рассматривается как пустая строка нулевой
длины (функция ДЛСТР() даст для такой ячейки значение 0).
При слиянии строк пробелы между строками не добавляются
автоматически. При необходимости пробелы должны добавляться
вручную либо в самих строках (как изображено на рисунке выше),
либо непосредственно в списке аргументов в функции, например,
так: =СЦЕПИТЬ(B3; " ";C3).
10

11. Краткое описание текстовых функций

ЕОШИБКА(проверяемое_значение)
Категория – проверка свойств и значений
Возвращает значение ИСТИНА, если проверяемое значение
является любым сообщением об ошибке, например #Н/Д,
#ССЫЛКА, #ИМЯ?, #ЗНАЧ! и т.д.
Если проверяемое значение не является ошибкой
(т.е. является числом или текстом), то возвращается значение ЛОЖЬ.
Сообщение об ошибке не всегда является признаком неправильного
результата. В некоторых случаях (в том числе – при выполнении
данной работы), сообщение об ошибке текстовой функции,
полученное в одних ячейках, используется для выполнения
определенных действий с другими ячейками, т.е. является
ожидаемым событием.
11

12. Краткое описание текстовых функций

ЕСЛИ(проверяемое_условие;
значение_если_истина;
значение_если_ложь)
Категория – логические функции
Проверяет условие или логическое значение,
заданное первым аргументом, и возвращает второй
либо третий аргумент в зависимости от результата проверки.
Функции НАЙТИ(), ЕОШИБКА() и ЕСЛИ() могут эффективно
применяться совместно. В зависимости от того, был ли в одной
ячейке найден искомый текст функцией НАЙТИ(), в другой ячейке
появится либо число (номер позиции, в которой найден текст),
либо сообщение об ошибке, которое может быть интерпретировано
как признак отсутствия дальнейших повторных появлений искомого
текста.
12

13. ПОИСК АЛФАВИТА СООБЩЕНИЯ

14. Исходное сообщение

Введем в отдельную ячейку исходное сообщение.
В качестве примера используется сообщение МАМА_МЫЛА_РАМУ.
Для наглядности рекомендуется использовать заглавные буквы,
а пробелы заменить символом подчеркивания.
В следующей строке находим длину сообщения |T|, которая
потребуется для определения количества ячеек в расчетах.
В ячейке B2 виден результат вычислений, а расчетная формула
показана выше в строке формул (рядом с ней находится кнопка
вызова мастера функций fx). Адрес ячейки, в которую введена
формула, можно увидеть в левой части строки формул.
14

15. Извлечение отдельных символов

Далее заполняем первый столбец
числами от 1 до найденной длины
сообщения с использованием
простейшей формулы (A8=A7+1).
В следующем столбце при помощи
функции ПСТР( ) извлекаем по
одному символу из исходного
сообщения (номер позиции символа
берется из первого столбца).
Перед копированием формулы по
строкам вниз следует убедиться, что в
формуле использована абсолютная
ссылка на ячейку с исходным
сообщением ($B$1).
15

16. Поиск повторений символов

В следующем столбце (начиная
с ячейки C7) при помощи
функции НАЙТИ будем искать
в сообщении ($B$1) поочередно
отдельные символы
со следующей позиции
по отношению к известной
(в столбце A).
Если символ будет найден,
в ячейке появится позиция
повторного появления данного
символа в сообщении.
Если символ в сообщении
больше не встречается, будет
получено сообщение об ошибке.
16

17. Получение строки алфавита

В алфавит следует включать только те символы, для которых в
столбце «Повтор» имеется сообщение об ошибке (т.е. они больше
не повторяются).
Для составления строки алфавита используется сложная формула,
включающая в себя три функции из трех разных категорий
(логическая, проверка, текстовая).
Для правильной работы этой формулы в ячейку D6 необходимо
ввести пустую строку ="" (две кавычки без пробела), которая
будет являться заготовкой для получения алфавита сообщения,
иначе пустая ячейка интерпретируется как число 0.
17

18. Получение строки алфавита

Если в текущей строке в столбце C есть сообщение об ошибке,
значит, в столбце B есть символ, который больше не повторяется в
сообщении, поэтому его следует дописать в столбце D к строке
алфавита из предыдущей строки.
Если в столбце C ошибки нет, предыдущая строка алфавита
остается без изменений.
После копирования формулы в последней строке будет получен
алфавит сообщения.
18

19. Определение размера алфавита

Ссылку на ячейку с полученной строкой алфавита можно
разместить в ячейку B3, а в следующей строке при помощи
функции =ДЛСТР() определить размер алфавита |A|
(при использовании относительных ссылок эту формулу можно
скопировать из ячейки B2).
19

20. ПОИСК ЧАСТОТ ПОВТОРЕНИЙ СИМВОЛОВ

21. Извлечение символов алфавита

Создадим заготовку расчетной таблицы. По вертикали (столбец G)
извлечем отдельные символы из сообщения, а по горизонтали
(строка 5) – символы алфавита.
Формула извлечения отдельных символов из строки алфавита в
строку аналогична формуле извлечения символов из текста
сообщения, но поскольку размеры сообщения и алфавита разные,
то и количество строк и столбцов, в которые копируются
формулы, будут разными.
21

22. Проверка совпадений символов

Далее в полученной матрице проверим, какой из символов алфавита
совпадает с текущим символом сообщения. При составлении
формулы необходимо использовать абсолютные ссылки на столбец
символов сообщения и строку символов алфавита. В таком случает
формулу из ячейки H3 можно скопировать на все ячейки матрицы
Логическая функция ЕСЛИ проверяет совпадение символов.
В пределах каждой из строк должна быть только одна единица (все
символы алфавита разные, поэтому в строке совпадение только
одно). Количество единиц в столбце дает частоту повторения
символов алфавита во всем сообщении.
22

23. Проверка совпадений символов

Далее в отдельной строке может быть подсчитано количество
повторений символов алфавита k(i) в сообщении при помощи
математической функции СУММ( ).
Использование относительных ссылок на номер столбца позволит
скопировать эту формулу на все столбцы.
В отдельной ячейке можно получить сумму всех повторений
всех символов, которая, очевидно, должна быть равна
длине сообщения |T|.
23

24. РАСЧЕТ КОЛИЧЕСТВА ИНФОРМАЦИИ В СООБЩЕНИИ

25. Расчет вероятности появления символов

Для расчета вероятности появления символов p(i)=k(i)/|T|
необходимо использовать абсолютную ссылку на суммарное
количество символов в сообщении.
В отдельной ячейке можно получить сумму всех вероятностей
повторений всех символов, которая, очевидно, должна быть равна 1.
25

26. Расчет количества информации

Для расчета количества информации в сообщении
H= – S p(i) * log2p(i)
можно использовать математическую функцию расчета суммы
произведений ячеек в двух непрерывных диапазонах ячеек.
26

27. Пример оформления рабочего листа

27

28. ПОСТРОЕНИЕ КОДА ПОСТОЯННОЙ ДЛИНЫ

29. Подготовка нового рабочего листа

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

30. Ввод двоичных кодовых слов

Для каждого символа из столбца B в следующем столбце
разместим двоичные слова постоянной длины, соответствующие
двоичным кодам символов. Двоичные слова составляются
в порядке возрастания, это не является обязательным требованием,
но является простым способом обеспечения уникальности кодов.
Длина двоичных слов определяется как наименьшее натуральное
число, удовлетворяющее условию L ≥ log2|A|.
Чтобы сохранить отображение ведущих нулей, первым символом
в ячейке (перед вводом цифр двоичных кодов) следует
использовать апостроф, чтобы содержимое ячейки было
интерпретировано как текстовой поле, а не число.
30

31. Извлечение отдельных символов текста

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

32. Подстановка двоичных кодовых слов

Двоичные слова кодов
символов в столбце С
заполняются при помощи
функции =ВПР().
Эта функция ищет
значение первого аргумента
в первом столбце диапазоне
ячеек второго аргумента
и подставляет вместо него
значение из столбца, номер
которого указан в третьем
аргументе.
Значение последнего аргумента "ЛОЖЬ" задает поиск символа
в столбце по строгому совпадению, при поиске числовых значений
можно проверять попадание в заданный интервал.
32

33. Получение строки двоичного кода

Далее объединяем полученные двоичные слова кодов
отдельных символов сообщения в единую строку
при помощи функции =СЦЕПИТЬ() аналогично
составлению строки символов алфавита.
33

34. Получение строки двоичного кода

Поместим ссылку на последнюю ячейку со строкой двоичного кода
постоянной длины в ячейку B3 и найдем длину полученного кода.
Далее рассчитаем эффективность полученного кода постоянной
длины при Lср=const=3.
Для расчета эффективности полученного кода постоянной дины
в ячейке B6 следует использовать ссылку на рассчитанное ранее
значение количества информации на предыдущем рабочем листе.
34

35. Пример оформления рабочего листа

35

36. ПОСТРОЕНИЕ КОДА ПЕРЕМЕННОЙ ДЛИНЫ

37. Таблица частот появления символов

Для построения двоичного дерева
префиксного кода переменной длины
нам потребуется таблица частот появления
отдельных символов алфавита в сообщении,
отсортированная по уменьшению частоты.
Построение двоичного дерева начинается с
нижней части таблицы. Складываются
наименьшие частоты появления символов,
начиная с нижней части дерева.
На шаге 1 для букв Ы и У, имеющих частоту 1, составляется
суммарная частота 2.
Продолжаем складывать наименьшие частоты, с самых нижних
узлов, имеющих самые маленькие частоты, а именно – с пар букв
Л и Р. Их суммарная накопленная частота тоже равна 2.
37

38. Первые три шага построения дерева

На шаге 2 из трех частот, равных 2, складываем наименьшие
частоты нижних узлов, а именно – для двух пар букв УЫ и ЛР.
На шаге 3 минимальными накопленными частотами являются 2 (у
пробела) и 4 (у четырех букв ЛРУЫ вместе).
38

39. Итоговое двоичное дерево

Процесс продолжается до тех пор, пока в сумме не будет получено
полное количество символов в сообщении (шаги 4–5), причем
сначала складываются 4+4=8 (шаг 4), а не 4+6=10 (шаг 5).
В результате получим иерархический граф, называемый двоичным
(бинарным) деревом – из каждой вершины графи исходят строго
две дочерние ветви, а входит одна родительская ветвь
(кроме вершины дерева – узла с максимальной суммой).
39

40. Кодовые слова переменной длины

Для того, чтобы превратить полученное дерево в двоичный
префиксный код, необходимо расставить нули и единицы на
ветвях полученного дерева. Принято кодировать более частые
комбинации меньшими по абсолютной величине кодами.
Начиная с вершины дерева (в примере – узел с суммой 14),
для каждой восходящей ветви записываем 0,
а для каждой нисходящей ветви 1.
40

41. Подстановка двоичных кодовых слов

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

42. Пример оформления рабочего листа

42

43. ВАРИАНТЫ ЗАДАНИЙ

44. ВАРИАНТЫ ЗАДАНИЙ (##1-15)

1. ВЕСЕЛО_И_ЛАСКОВО_СЛОВО_СОКОЛА
2. АЛЕН_ДЕЛОН_НЕ_ПИЛ_ОДЕКОЛОН
3. НЕТУ_СИЛ_У_ЛИСЫ_ПЛЕСТИ_СЕТИ
4. ТУРОК_СТЕРЕГ_СУРКА_У_СТОГА
5. ТАРАКАН_ИСКАЛ_КАРАВАН_РИСА
6. КАРЛ_У_КЛАРЫ_НЕ_КРАЛ_КОРАЛЛЫ
7. РАНО_МОНАРХ_НАХАМИЛ_МОНАХУ
8. КЛАРА_У_КАРЛА_УКРАЛА_КЛАРНЕТ
9. РАД_КОНОКРАД_ДАРЕНОЙ_КОРОВЕ
10. КАЗАК_ЗАКАЗАЛ_ФАЗАНА_В_КАЗАНЕ
11. ТАРАКАН_УВОЛОК_ВОРОНУ_У_РАКА
12. СОКОЛ_ЛАСКЕ_РАССКАЗАЛ_СКАЗКУ
13. НАПОЛЕОН_ПОЛОЛ_НА_ПОЛЕ_ЛУК
14. НЕДАРОМ_МНОГО_МАРОДЕРОВ_В_МОРЕ
15. ПЛАКАЛА_ВОРОНА_НА_КАРНАВАЛЕ
44

45. ВАРИАНТЫ ЗАДАНИЙ (##16-30)

16. САВАННА_ПОЛНА_КАРАВАНОВ_КОРОВ
17. ЛОСОСЬ_НАСЫПАЛ_СОЛЬ_НА_САЛО
18. ПОСОЛ_ПОД_СТОЛ_ПОЛОЖИЛ_ТОПОР
19. В_МОРГЕ_ГАРЕМА_ГРОМКО_ГРЕМЕЛО
20. ВАРАН_НАПАЛ_НА_КАРАВАН_ВАНИЛИ
21. РЕВИЗОР_ВЕЗ_ТЕЛЕВИЗОР_ЗВЕРЮ
22. В_САЛАКЕ_МАЛО_САЛА_И_МАСЛА
23. КАБАН_И_БАРАН_КУРИЛИ_ТАБАК
24. УЛИТКА_ЗАПОЛЗЛА_ЗА_КАЛИТКУ
25. ВОБЛА_БЫЛА_В_КАБАЛЕ_У_ВОЛОВ
26. РИС_С_БАРБАРИСОМ_И_РЕДИСОМ
27. ЛОСЬ_И_ОСА_ЕЛИ_СОЛЬ_И_ФАСОЛЬ
28. МАЛ_КОЛОКОЛ_ИЗ_ВОЛОКОЛАМСКА
29. ОСА_ПОКУСАЛА_ОСЛИКУ_ЛОПАТКУ
30. ВАССАЛ_ПОСЛАЛ_ПИСЬМО_В_ЛАОС
45