Программирование (python) для лингвистов дз — различия между версиями
Denaas (обсуждение | вклад) (→Задание 2.) |
Denaas (обсуждение | вклад) |
||
Строка 100: | Строка 100: | ||
!! обратите внимение, что теперь частоты - это действительные числа. | !! обратите внимение, что теперь частоты - это действительные числа. | ||
+ | |||
+ | |||
+ | == Задание 4. == | ||
+ | |||
+ | По материалам 4 семинара: | ||
+ | # Модифицировать алгоритм Рабина-Карпа, чтобы он выполнял поиск нескольких паттернов в строке одновременно. | ||
+ | # Дать асимптотическую верхнюю оценку сложности O() реализованного алгоритма в зависимости от параметров T (длина текста), P_1, P_2, ..., P_n (длины паттернов) | ||
+ | # Написать юнит тесты к разработанному алгоритму | ||
+ | # работу оформить в виде скрипта *.py | ||
+ | |||
+ | Интерфейс: | ||
+ | |||
+ | def search_rabin_multi(text, patterns): | ||
+ | """ | ||
+ | text - строка, в которой выполняется поиск | ||
+ | patterns = [pattern_1, pattern_2, ..., pattern_n] - массив паттернов, которые нужно найти в строке text | ||
+ | По аналогии с оригинальным алгоритмом, функция возвращает массив [indices_1, indices_2, ... indices_n] | ||
+ | При этом indices_i - массив индексов [pos_1, pos_2, ... pos_n], с которых начинаетй pattern_i в строке text. | ||
+ | Если pattern_i ни разу не встречается в строке text, ему соотвествует пустой массив, т.е. indices_i = [] | ||
+ | """ | ||
+ | pass |
Версия 02:39, 5 октября 2017
Содержание
Задание 1.
1. Реализовать функцию fibonacci(n) вычисления n-ого числа Фибоначчи со сложностью не хуже O(n) по вренени
2. Реализуйте иерархию наследования с нетривиальной структурой (т.е. иерархия должна образовывать дерево / лес), не менее 6 классов. Например: группы языков, систематика животного мира и т.д. Продемонстрируйте на примере применение полиморфизма к решению какой то задачи. (Например, обслуживание зоопарка в случае животных). P.S. укажите в комментариях к коду (например, в реализации класса зоопарка), в каком месте вы применяете полиформизм
3. Реализуйте средствами ООП паттерн поведения Singleton: класс UniqObject реализует метод класса create_object, который возращает объект UniqObject. Объект UniqObject должен всегда существовать в единственном экземпляре.
Сделанная домашняя работа выкладывается в репозиторий в папку homework_1, решение каждого задания - в отдельный файл task_<номер задания>.py
Задание 2.
Цель задания - научится самостоятельно ориентроваться в документации к библиотекам.
virtualbox image with preinstalled libraries user: hse, password: hsepass
Вам необходимо написать программу, которая парсит статьи википедии (language=en) и считает по ним некоторые статистики.
1. Реализовать класс WikiParser с конструктором без аргументов и методом get_articles, который принимает название исходной статьи start, обходит все статьи википедии, на которые она ссылается, и возвращает список содержимого статей (с выполнением парсинга).
- При парсинге каждой статьи для того, чтобы убрать html теги, используется функция pattern.web.plaintext.
- В результате парсинга между соседними словами должно быть 1 пробел.
- В результате парсинга весь текст переводится в lowercase, знаки пунктуации выкидываются
Интерфейс:
class WikiParser: def __init__(self): pass def get_articles(self, start, depth, max_count): return list_of_strings
2. Реализовать класс TextStatistics с конструктором, который принимает в качестве аргумента список содержимого статей:
- get_top_3grams - возвращает tuple, первым элемент которого - список 3-грамм в порядке убывания их частот, второй элемент - соотвественно список сколько раз встретилась каждая 3грамма. Подсчет идет по всему корпусу articles. При подсчете 3-грамм исключить из рассмотрения все числа и пунктуацию.
- get_top_words - возвращает tuple, первым элемент которого - список слов в порядке убывания их частот, второй элемент - соотвественно список сколько раз встретилась каждое слово. Подсчет идет по всему корпусу articles. При подсчете слов исключить из рассмотрения все числа, предлоги, артикли и пунктуацию.
Интерфейс:
class TextStatistics: def __init___(self, articles): pass
def get_top_3grams(self, n): return (list_of_3grams_in_descending_order_by_freq, list_of_their_corresponding_freq)
def get_top_words(self, n): return (list_of_words_in_descending_order_by_freq, list_of_their_corresponding_freq)
3. Реализовать класс Experiment с методом show_results, который используя WikiParser и TextStatistics:
- Выполняет парсинг статей википедии для "Natural language processing"
- По полученному корпусу текстов считает топ-20 3-грамм и топ-20 слов.
- По статье "Natural language processing" (только по ней) считает топ-5 3-грамм и топ-5 слов.
- Печатает результаты эксперимента в структурированной форме
4. В комментариях после класса Experiment привести результаты выполнения метода show_results.
5. Результатом выполнения задания является код указанных классов и корректные результаты эксперимента
Задание 3.
Интерфейс
class WikiParser: def __init__(self): pass def get_articles(self, start): return list_of_strings
class TextStatistics: def __init___(self, articles): pass def get_top_3grams(self, n, use_idf=False): return (list_of_3grams_in_descending_order_by_freq, list_of_their_corresponding_freq) def get_top_words(self, n, use_idf=False): return (list_of_words_in_descending_order_by_freq, list_of_their_corresponding_freq)
Используя код из задания 2:
- Изменить логику работы WikiParser.get_articles - оставить знаки пунктуации, которые разделяют предложения.
- Изменить логику get_top_3grams - теперь под 3-граммами понимаются буквенные триграммы. Триграммы могут состоять из букв, цифр и не более 1 пробела подряд.
- Добавить в метод get_top_words параметр use_idf, при выставлении которого частоты умножаются на коэффициент IDF и соотвественно сортируются. IDF = log(<общее кол-во статей в корпусе> / <кол-во статей, в которых встретилось данное слово>)
- Добавить в метод get_top_3grams параметр use_idf, при выставлении которого частоты умножаются на коэффициент IDF и соотвественно сортируются. IDF = log (<общее кол-во предложений в корпусе> / <кол-во предложений, в которых встретилась данная триграмма>)
- написать unit тесты к классу TextStatistics, которые проверяют соблюдение описанных условий и корректность подсчета частот. Тесты должны покрывать граничные условия и разные варианты (в разумных пределах) аргументов, передаваемые в методы.
- выполнить эксперимент:
1 Выполнить парсинг статей википедии для "Natural language processing" 2 По полученному корпусу текстов посчитать топ-20 3-грамм и топ-20 слов с use_idf=True. 3 Печатает результаты эксперимента в структурированной форме 4 В комментариях после класса Experiment привести результаты выполнения метода show_results. 5 Результатом выполнения задания является код указанных классов в 1 файле *.py и корректные результаты эксперимента
!! обратите внимание, что вы кладете 3 дз в новый каталог homework_3, не внося изменения в каталог homework_2
!! обратите внимение, что теперь частоты - это действительные числа.
Задание 4.
По материалам 4 семинара:
- Модифицировать алгоритм Рабина-Карпа, чтобы он выполнял поиск нескольких паттернов в строке одновременно.
- Дать асимптотическую верхнюю оценку сложности O() реализованного алгоритма в зависимости от параметров T (длина текста), P_1, P_2, ..., P_n (длины паттернов)
- Написать юнит тесты к разработанному алгоритму
- работу оформить в виде скрипта *.py
Интерфейс:
def search_rabin_multi(text, patterns): """ text - строка, в которой выполняется поиск patterns = [pattern_1, pattern_2, ..., pattern_n] - массив паттернов, которые нужно найти в строке text По аналогии с оригинальным алгоритмом, функция возвращает массив [indices_1, indices_2, ... indices_n] При этом indices_i - массив индексов [pos_1, pos_2, ... pos_n], с которых начинаетй pattern_i в строке text. Если pattern_i ни разу не встречается в строке text, ему соотвествует пустой массив, т.е. indices_i = [] """ pass