Если предположить, что процессор может выполнять 10000 миллионов операций в секунду, то процесс анализа будет соответствовать величине:
Безусловно, данное время не может считаться приемлемым для данной задачи, потому требуется выполнять ее оптимизацию.
В данной работе выделяются следующее методы повышения быстродействия алгоритма:
1. использование индексов глубины рекурсивного просмотра. Если индекс превышает максимально допустимый, то выполняется шаг назад;
2. Использование перебора с возвратом. Если на определенном этапе возможна на основе мультипликативного значения величин ребер установить, что в данном направлении просмотра установить факт изоморфности невозможно, то выполняется шаг назад;
3. Использование алгоритма выбора ключевых вершин, с которых будет выполняться просмотр;
4. Использование технологий внедрения нитей в граф.
Первый метод оптимизации позволить получить любое указанное разработчиком время работы алгоритма, однако качество результата прямопропорционально времени, которое выделяется для работы алгоритма. Под качеством работы алгоритма понимается соответствие полученных выводов о наличие заимствований истине. В данном методе индекс глубины просмотра определяется согласно вычислительным возможностям техники, на котором будет проводиться анализ.
Второй метод позволяет очень существенно оптимизировать время работы и память, необходимые для работы алгоритма: скорость работы может возрастать в десятки раз, а если исходный граф имеет слаборегулярную структуру, то может потребоваться объем времени, в сотни раз меньше, чем у оригинального алгоритма.
Данный подход может также использоваться при переходе к алгоритму, основанному на методах динамического программирования (с целью снятия проблем, возникающих при рекурсивных вызовах).
Очевидным недостатком данного метода является то, что невозможно предсказать реальное время работы алгоритма, то есть невозможно предугадать сколько раз будет выполнен шаг назад. Это не позволяет формально описать время работы алгоритма выражением, меньшим чем
O(n) = n!
Использование алгоритма выбора ключевых вершин позволяет (при комбинировании с алгоритмом поиска с возвратом) сократить сложность алгоритма в количество раз, соответствующему количеству ребер, исходящих из этой вершины.
Еще уменьшить время, требуемое на работу алгоритма возможно, если на каждом рекурсивном вызове формировать очередную ключевую вершину. В таком случае время работы будет уменьшаться по обратному экспоненциальному закону.
Технология внедрения нитей в граф может очень значительно оптимизировать алгоритм, приблизив его сложность к такой, какая является приемлемой для вычислительных способностей техники, на которой будет вестись анализ без существенной потери качества анализа текстов на наличие заимствований.
Оптимизация базируется на том, что некоторые вершины на определенном этапе анализа при просмотре графа игнорируются. Создается некоторое фиктивное ребро, вес которого рассчитывается согласно значениям весов между вершинами, которые предполагается извлечь из списка рассматриваемых.
Существенной проблемой при реализации алгоритма внедрения нитей в графы является сложность задачи построения списка вершин, которые возможно убрать из рассмотрения.
Предполагается, что данный алгоритм будет иметь реализацию элементов динамического программирования на динамической таблице, которая должна строиться на этапе формирования семантических моделей.
Значительного выигрыша в производительности возможно достичь, если использовать метод динамического комбинирования алгоритмов, т.е. выбор алгоритма, который на определенном этапе должен проводить просмотр графа исходя из анализа данных, полученных на предыдущих этапах.
Для обеспечения возможности динамического переключения между алгоритмами придется использовать дополнительные блоки памяти:
· Память для хранения данных по каждой вершине. Эти данные возможно сохранять в таблицах, описывающих графы. В качестве данных таблиц используются кубы, каждое измерение которых определяет тип данных. В качестве одного из измерений предлагается использовать данных, которые были получены при выполнении определенного алгоритма и каким-либо образом характеризуют вершину или связь с точки зрения этого алгоритма;
· Блок данных, являющихся результирующими для одного алгоритма и входными для другого
Ключевым алгоритмом анализа текстов, представленных на естественном языке, на наличие заимствований является алгоритм сравнения семантических моделей.
В данной работе этот алгоритм реализован на базе классического алгоритма установления изоморфности графов, но использовалась проблемно-ориентированная модификация алгоритма.
При рассмотрении алгоритма было предложено использовать несколько вариантов оптимизаций, применимых в контексте данной работы.
В качестве основного средства разработки проекта использовался язык программирования C# в среде разработки Microsoft Visual Studio 2005.
На выбор данного языка повлиял ряд факторов, среди которых:
· Поддержка Объектно-ориентированной парадигмы программирования. C# полноценно поддерживает данную парадигму и позволяет применять все характерные особенности данной технологии:
o Абстракция данных;
o Механизмы наследования;
o Средства обеспечения полиморфизма;
o Парадигма инкапсуляции
Механизмы объектно-ориентированных технологий позволяют создать логическую связь между разрабатываемыми объектами и обеспечить их взаимодействие между собой.
В данной работе присутствует множество логически-независимых и обособленных частей, при реализации которых потребуется организовать взаимодействие и организацию данных и инструкций согласно правилам объектно-ориентированного программирования.
· C# поддерживает ряд средств в рамках технологий объектно-ориентированного программирования, которые позволяют увеличить качество разрабатываемых продуктов и максимально эффективно использовать время, отведенное на разработку программного обеспечения. Среди них:
o Технология внешних псевдонимов (external aliases). Данная технология позволяет использовать различные сборки с одинаковыми пространствами имен как различные пространства имен. Это достигается за счет использования механизмов выделения глобальных пространств имен для сборок. Для этих целей объявляются внешние псевдонимы для каждой сборки. Далее эти псевдонимы возможно использовать как пространства имен высоко уровня;
o Возможность использования общих типов (Generics). Данный подход позволяет не указывать тип используемого параметра в процессе разработки, тем самым обеспечив возможность универсализировать процесс разработки. Данный механизм несколько схож с механизмом шаблонного программирования в C++;
o Возможность использования статических классов. Данные и инструкции статического класса загружаются один раз, а создать экземпляр данного класса невозможно;
o Разделение классов. Язык программирования C# позволяет разбить класс на несколько частей, используя идентификатор partial. Данный подход позволяет оптимальным образом структурировать исходный код приложения;
o Итераторы. Механизм итераторов позволяет удобно и эффективно выполнять обход элементов коллекций, что положительно сказывается на качестве исходного кода и производительности разрабатываемого приложения. Механизм итераторов позволяет максимально оптимизировать операции итеративного характера, что является весьма востребованным в данной работе, поскольку вычислительная сложность используемых алгоритмов очень высокая, а значит, следует искать пути максимально оптимизировать работу системы с точки зрения использования процессорного времени и системной памяти;
o Безымянные методы. Этот подход позволяет разработчику не указывать имена методов, а разрешить компилятору сгенерировать их автоматически. Такой подход позволяет сократить объем исходного кода приложения, тем самым повысив его читабельность и логическую упорядоченность;
o Документирование исходного кода в стандарте XML. C# позволяет каждый блок кода комментировать и документировать по правилам, принятым согласно стандарту оформления XML-кода. Такой подход позволяет разрабатывать структурную документацию по приложению прямо в процессе его разработки. Это позволит получать автоматически техническую документацию по коду в любом виде;
o В C# присутствует сборщик мусора (garbage collector), характерный для всех .NET – языков. C# также позволяет писать и неуправляемый код, в рамках блока небезопасного блока;
o В C# все объекты являются классами, что позволяет универсализировать и упростить процесс разработки;
o C# позволяет использовать очень удобный механизм – сериализацию классов, упаковывая и распаковывая классы в различных участках разрабатываемого приложения. На базе этой возможности возможно очень удобно строить распределенные вычисления, что также является актуальным для данной работы;
o В C# представлена концепция пространств имен, что позволяет иерархически структурировать исходный код приложения и избежать проблем с именованием;
· C# является полноценным .NET-языком, что позволяет использовать все достоинства данной технологии, среди которых:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42
