lab_work_2.md

Лабораторная работа №2

Дано

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

Пример: пусть есть два слова: заданное слово length и желаемое слово kitchen.

Веса значимости операций:

• добавление - 1
• удаление - 1
• замена - 2

Вопрос: какие операции и в каком порядке надо проделать над словом length, чтобы получить слово kitchen, если в списке доступных операций только добавление, удаление и замена символов?

Что надо сделать

В рамках лабораторной работы №2 требуется разработать механизм, позволяющий определить минимальное количество операций (минимальное расстояние) за которые можно из заданного слова получить желаемое слово.

Шаг 1. Генерация матрицы решений

Функция должна возвращать объект типа list - список, состоящий из списков заданного размера. Все элементы списков - нули.

Подсказка №1: математически этот двумерный список соответствует матрице.

Подсказка №2: внимательно ознакомьтесь с Шагом 4, чтобы оценить требуемый размер матрицы.

Например матрица из 3 строк и 4 столбцов:

[
  [0, 0, 0, 0],
  [0, 0, 0, 0],
  [0, 0, 0, 0]
]

Интерфейс:

def generate_edit_matrix(num_rows: int, num_cols: int) -> list:
  pass

Шаг 2. Инициализация матрицы решений

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

Функция принимает матрицу в качестве единственного аргумента и возвращает измененную версию этой матрицы.

Правила инициализации матрицы:

• заполнение первого столбца матрицы

* заполнение первой строки матрицы

Интерфейс:

def initialize_edit_matrix(edit_matrix: tuple, add_weight: int, remove_weight: int) -> list:
  pass

Шаг 3. Найти наименьшее значение из набора заданных чисел

Функция принимает на вход кортеж из чисел и возвращает наименьшее из них.

Интерфейс:

def minimum_value(numbers: tuple) -> int:
  pass

Шаг 4. Заполнить матрицу решений

Функция принимает на вход инициализированную матрицу решений и веса значимости операций.

Правило заполнения каждой ячейки матрицы:

Подсказка №3: при итерировании по матрице обратите внимание на диапазоны счётчиков (переменные цикла) - какое они могут принимать минимальное и макимальное значения

Интерфейс:

def fill_edit_matrix(edit_matrix: tuple,
                    add_weight: int,
                    remove_weight: int,
                    substitute_weight: int) -> list:
  pass

Матрица решений из разбора примера в Разделе "Дано":

	#	k	i	t	c	h	e	n
#	0	1	2	3	4	5	6	7
l	1	2	3	4	5	6	7	8
e	2	3	4	5	6	7	6	7
n	3	4	5	6	7	8	7	6
g	4	5	6	7	8	9	8	7
t	5	6	7	6	7	8	9	8
h	6	7	8	7	8	7	8	9

Символ # обозначает пустую строку

Минимальным расстоянием является значение в матрице по индексу (6,7) и для данного примера равняется 9.

Шаг 5. Расчёт минимального расстояния (выполнение Шагов 1-5 соответствует 6 баллам)

Функция принимает на вход изначальное слово, желаемое слово и веса значимости операций. Возвращаемым значением является число - найденное минимальное расстоянние.

def find_distance(original_word: str,
                  target_word: str,
                  add_weight: int,
                  remove_weight: int,
                  substitute_weight: int) -> int:
  pass

Шаг 6. Сохранение и восстановление матрицы решений с помощью файлов (выполнение Шагов 1-5 + 6 соответствует 8 баллам)

Функция сохранения в файл принимает на вход матрицу решений и путь до .csv файла. Функция чтения из файла принимает на путь до .csv файла и возвращает матрицу решений, построенную на основе значений из заданного файла.

Подсказка: файлы с расширением .csv представляют собой текстовые документы, содержащие строки. Каждая строка содержит значения, перечисленные через запятую.

Например, матрица из Шага №1 может быть записана в файл matrix.csv:

0,0,0,0
0,0,0,0
0,0,0,0

Интерфейс:

def save_to_csv(edit_matrix: tuple, path_to_file: str) -> None:
  pass

def load_from_csv(path_to_file: str) -> list:
  pass

Шаг 7. Интеллектуальная интерпретация матрицы решений (выполнение Шагов 1-5 + 6 + 7 соответствует 10 баллам)

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

Возвращаемым значением является набор строк, содержащих текстовое описание требуемых операций. Разбирая пример из Шага 4:

[
  'remove l',
  'substitute e with k',
  'substitute n with i',
  'remove g',
  'insert c',
  'insert e',
  'insert n'
]

Важно: список инструкций должен начинаться по ходу разбора заданного слова, т.е. с его начала

Подсказка №4: алгоритм разбора матрицы решения M(nxm) лучше начинать с M[n][m]

Интерфейс:

def describe_edits(edit_matrix: tuple,
                  original_word: str,
                  target_word: str,
                  add_weight: int,
                  remove_weight: int,
                  substitute_weight: int) -> list:
  pass

Литература для пытливых умов

1. Ссылка на бессмертную Википедию
2. Глава в книге Журавского