Автоматизация и учет данных о научной работе в ВУЗе
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
-исследовательский сектор11НИРНаучно-исследовательская работа12Серверкомпьютер (или специальное компьютерное оборудование), выделенный и/или специализированный для выполнения определенных сервисных функций [7]13Сводный план НИРДокумент в который включены данные о научной деятельности в течении года14Сотрудник кафедрыСотрудник кафедры, который отвечает за научную деятельность на кафедре и подачу сведений в НИС 15РекторРуководитель высшего учебного заведения16.ПроректорЗаместитель ректора высшего учебного заведения по какому-либо направлению работы ВУЗа17Отчет о финансированииДокумент, содержащий сведения о финансировании научных проектов18Форма по публикациямДокумент, утвержденный в высшем учебном заведении, для подачи сведений о опубликованных работах19Заведующий аспирантурой Заведующий подразделением ВУЗа по подготовке преподавательских и научных кадров высокой квалификации20Бухгалтерия Штатно-структурное подразделение хозяйствующего субъекта, предназначенное для аккумулирования данных о его имуществе и обязательствах21Отчетный периодКвартал (четверть года)
1.2 Математическая модель ПМК для автоматизации учета данных о
научной работе в ВУЗе
При разработке ПМК, одним из важных требований был поиск дублирующихся или похожих записей в поданных сведениях. Рассмотрим алгоритмы, которые находят похожие записи Расстояние Левенштейна, алгоритм Вагнера-Фишера, метод N-грамм, поиска по сигнатуре, поиск с помощью БK-деревьев.
Расстояние Левенштейна между двумя строками в теории информации и компьютерной лингвистике - это минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
Пусть S1 и S2 - две строки (длиной и соответственно) над некоторым алфавитом, тогда расстояние Левенштейна d(S1,S2) рассчитывается по формуле (1.1)
d(S1,S2)=D(M,N) , (1.1)
где
(1.2)
где m(a,b) равна нулю, если a=b и единице в противном случае.
Здесь шаг по i символизирует удаление из первой строки, по j - вставку в первую строку, а шаг по обоим индексам символизирует замену символа или отсутствие изменений [8].
Расстояние Дамерау-Левенштейна.
Эта вариация вносит в определение расстояния Левенштейна еще одно правило - транспозиция (перестановка) двух соседних букв также учитывается как одна операция, наряду со вставками, удалениями и заменами.
Еще пару лет назад Фредерик Дамерау мог бы гарантировать, что большинство ошибок при наборе текста - как раз и есть транспозиции. Поэтому именно данная метрика дает наилучшие результаты на практике.
Рассмотрим алгоритм Вагнера-Фишера.
Для нахождения кратчайшего расстояния необходимо вычислить матрицу D, используя вышеприведённую формулу. Её можно вычислять как по строкам, так и по столбцам. Псевдокод алгоритма представлен на рисунке 1.1
Рисунок 1.1 - Псевдокод алгоритма вычисление матрицы D
Или в более развёрнутом виде, и при произвольных ценах замен, вставок и удалений, рисунок 1.2
Рисунок 1.2- Псевдокод алгоритма вычисление матрицы D учетом ценах замен, вставок и удалений
Для восстановления редакционного предписания требуется вычислить матрицу D, после чего идти из правого нижнего угла (M,N) в левый верхний, на каждом шаге ища минимальное из трёх значений:
если минимально (D(i-1, j) + цена удаления символа S1[i]), добавляем удаление символа S1[i] и идём в (i-1, j);
если минимально (D(i, j-1) + цена вставки символа S2[j]), добавляем вставку символа S1[i] и идём в (i, j-1);
если минимально (D(i-1, j-1) + цена замены символа S1[i] на символ S2[j]), добавляем замену S1[i] на S2[j] (если они не равны; иначе ничего не добавляем), после чего идём в (i-1, j-1).
Здесь (i, j) - клетка матрицы, в которой мы находимся на данном шаге. Если минимальны два из трёх значений (или равны все три), это означает, что есть 2 или 3 равноценных редакционных предписания.
Метод N-грамм.
Этот метод был придуман довольно давно, и является наиболее широко используемым, так как его реализация крайне проста, и он обеспечивает достаточно хорошую производительность. Алгоритм основывается на принципе: Если слово А совпадает со словом Б с учетом нескольких ошибок, то с большой долей вероятности у них будет хотя бы одна общая подстрока длины N.
Эти подстроки длины N и называются N-граммами.
Во время индексации слово разбивается на такие N-граммы, а затем это слово попадает в списки для каждой из этих N-грамм. Во время поиска запрос также разбивается на N-граммы, и для каждой из них производится последовательный перебор списка слов, содержащих такую подстроку. На рисунке 1.3 представлена визуализация поиска для слова крокодил.
Наиболее часто используемыми на практике являются триграммы - подстроки длины 3. Выбор большего значения N ведет к ограничению на минимальную длину слова, при которой уже возможно обнаружение ошибок.
К особенностям алгоритма относится то, что алгоритм N-грамм находит не все возможные слова с ошибками. Если взять, например, слово ВОТКА, и разложить его на триграммы: ВОТКА > ВОТ ОТК ТКА - то можно заметить, что они все содержат ошибку Т. Таким образом, слово ВОДКА найдено не будет, так как оно не содержит ни одной из этих триграмм, и не попадет в соответствующие им списки. Следовательно, чем меньше длина слова и чем больше в нем ошибок, тем выше шанс того, что оно не попадет в соответствующие N-граммам запроса списки, и не будет присутствовать в результ