Программа частотного словаря сочетаний слов
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
Курсовая работа
Программа частотного словаря сочетаний слов
Техническое задание
Требуется разработать программу дляформирования частотного словаря сочетаний пар словдля некоторого текста. Программа должна обеспечивать следующие функции:
-обработка текстов, полученных методом копирования-вставки или расположенных в текстовом файле (разрешена работа с файлами, имеющими расширения.txt и.rtf);
-возможность пользователю самостоятельно определять символы, являющиеся разделителями слов;
-составление словаря словосочетаний по заданному тексту (под словосочетанием подразумеваются два слова, расположенные рядом в одном предложении);
-сохранение созданного в результате работы программы словаря в файл одного из текстовых форматов (.txtили.rtf);
-возможность сортировки словосочетаний словаря по алфавиту и по частоте их употребления в тексте;
-поиск словосочетания и частоты его употребления в словаре;
-отсутствие различий между символами верхнего и нижнего регистра в ходе обработки текста и словаря.
Введение
Задача создания программы, обладающей функционалом, определяемым заданием, предполагает решение более простых подзадач:
-возможность обработки текста из файла;
-формирование из заданного текста списка словосочетаний, в котором каждый элемент соответствует некоторому слову из текста;
-возможность перемещения словаря в файл текстового формата;
-поиск словосочетания в словаре;
-сортировка словосочетаний в словаре по заданному признаку;
-нечувствительность к регистру.
1.Теоретическая часть
приложение тестирование интерфейс пользователь
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). [1] Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:
количество шагов алгоритма, необходимых для упорядочения;
количество сравнений элементов;
количество перестановок, выполняемых при сортировке. [1]
Самым простым методом сортировки является так называемый метод пузырька. Чтобы уяснить его идею, представьте, что массив (таблица) расположен вертикально. Элементы с большим значением всплывают вверх наподобие больших пузырьков. При первом проходе вдоль массива, начиная проход снизу, берется первый элемент и поочередно сравнивается с последующими. При этом:
если встречается более легкий (с меньшим значением) элемент, то они меняются местами;
при встрече с более тяжелым элементом, последний становится эталоном для сравнения, и все следующие сравниваются с ним.
В результате наибольший элемент оказывается в самом верху массива.
Во время второго прохода вдоль массива находится второй по величине элемент, который помещается под элементом, найденным при первом проходе, т.е. на вторую сверху позицию, и т.д.
Заметим, что при втором и последующих проходах, нет необходимости рассматривать ранее всплывшие элементы, т.к. они заведомо больше оставшихся. Другими словами, во время j-го прохода не проверяются элементы, стоящие на позициях выше j.
Алгоритм данной сортировки считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка и пирамидальная сортировка. [1]
Шейкерная сортировка (сортировка перестановками) - разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.
Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения. [1]
Во-вторых, при движении от конца массива к началу минимальный элемент всплывает на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо. [1]
Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (т.е. части массива, где происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно справа налево и слева направо.
Лучший случай для этой сортировки - отсортированный массив (О(n)), худший - отсортированный в обратном порядке (O (n)). [1]
Пирамидальная - алгоритм сортировки, работающий в худшем, в среднем и в лучшем случае (то есть гарантированно) за? (n log n) операций при сортировке n элементов. Количество применяемой служебной памяти не зависит от размера массива (то есть, O(1)). [1]
Может рассматриваться как усовершенствованная сортировка пузырьком, в которой элемент всплывает (min-heap) / тонет (max-heap) по многим путям.
Сортировка пирамидой использует сортирующее дерево. Сортирующее дерево - это такое двоичное дерево, у которого выполнены условия:
1.Каждый лист имеет глубину либо , либо , - максимальная глубина дерева.
2.Значение в любой вершине больше, чем значения её потомков.
Удобная структура данных для сортирующего дерева - такой массив A