Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Програмний комплекс для аналізу ефективності роботи основних методів пошуку нечітких співпадінь, у порівнянні з запропонованим алгоритмом «найдовших речень»

Скачати 73.88 Kb.

Програмний комплекс для аналізу ефективності роботи основних методів пошуку нечітких співпадінь, у порівнянні з запропонованим алгоритмом «найдовших речень»




Скачати 73.88 Kb.
Дата конвертації30.03.2019
Розмір73.88 Kb.
ТипПрограмний комплекс
РЕФЕРАТ Актуальність теми. У наш час існує багато різноманітних способів знаходження нечітких співпадінь в електронних документах. Переважна більшість із них використовує за основу метод шинглів.
Більшість - велика частина чого-небудь, або кількісне переважання прихильників якоїсь ідеї чи рішення над їхніми противниками. Вважається найпершою засадою демократичного способу прийняття спільних рішень, головною й необхідною умовою обрання кандидата на виборну посаду.
Цей метод демонструє високу швидкість роботи та прийнятні точність та повноту результатів. Недоліком класичної реалізації методу є те, що після перестановки порядку слів у реченні обчислена хеш-сума, буде відмінною від хеш-суми немодифікованого речення. Тобто фактично речення є схожими, однак їхні хеш-суми відрізняються. Окрім того, метод шинглів базується на порівнянні 84 найменших хеш-сум речень, однак модифіковане речення може взагалі не потрапити до їх списку. В результаті, модифікований порядок слів може призвести до того, що два дуже подібні електронні документи будуть мати близький до нуля результат порівняння.
Результат, пі́дсумок, (заст. ску́ток, вислід) - кінцевий наслідок послідовності дій. Можливі результати містять перевагу, незручність, вигоду, збитки, цінність і перемогу. Результат є етапом діяльності, коли визначено наявність переходу якості в кількість і кількості в якість.
Електро́нний докуме́нт - документ, інформація в якому зафіксована у вигляді електронних даних, включаючи обов'язкові реквізити документа. Електронний документ може бути створений, переданий, збережений і перетворений електронними засобами у візуальну форму.
Для вирішення цієї проблеми пропонується використання підходу, який полягає на основі відбору речень з найбільшою сумарною довжиною слів та випадкових перестановок слів у реченнях. Передбачається, що відбір речень із найбільшою сумарною довжиною слів допоможе підвищити точність і повноту результатів. Це дозволить у певних випадках підвищити ефективність нечіткого порівняння в цілому. Також пропонується модифікувати підхід до канонізації текстів.
Модифікування (рос. модифицирование, англ. modification, нім. Abänderung f, Impfen n, Modifizierung f) - дія, напрямлена зміна властивостей об'єктів.
Каноніза́ція (від грец. κανονίζω - регулювати, визначати, узаконювати) - багатозначний термін.
Зокрема – відмовитися від словників службових слів, взявши за правило, що будь-яке слово, довжиною менше за 4 літери не несе інформаційного змісту для порівняння.
Словни́к - упорядкований в алфавітному чи тематичному порядку список заголовних слів, лексикографічно опрацьованих.
Це допоможе зменшити час роботи алгоритму на етапі канонізації, а отже і загалом час роботи порівняння. Об’єктом дослідження є нечітке порівняння електронних документів. Предметом дослідження є оцінка тривалості роботи, точності і повноти результатів різних модифікацій алгоритмів нечіткого порівняння та алгоритму «найдовших речень» зі спрощеною канонізацією та випадковими перестановками. Мета роботи: розробити модифікацію методу нечіткого порівняння та запропонувати програмний комплекс для аналізу ефективності роботи основних методів пошуку нечітких співпадінь, у порівнянні з запропонованим алгоритмом «найдовших речень» зі спрощеною канонізацією та випадковими перестановками.
Алгори́тм (латинізов. Algorithmi за араб. ім'ям узб. математика аль-Хорезмі) - набір інструкцій, які описують порядок дій виконавця, щоб досягти результату розв'язання задачі за скінченну кількість дій; система правил виконання дискретного процесу, яка досягає поставленої мети за скінченний час.
Мод (скор. від «модифікація», моддинґ ігор) - доповнення до відеогри, написане, як правило, сторонніми розробниками або любителями за допомогою SDK, який додається до гри або спеціальних, розроблених для модифікації любительських програм.
Докуме́нт - базова теоретична конструкція, яка відноситься до всього, що може бути збережене або представлене, щоб служити як доказ для певної мети.
Програма (фр. programme письмове оголошення, порядок денний, від грец. prógramma вказівка) - заздалегідь затверджена (визначена) дія.
Наукова новизна полягає в наступному: 1. Запропоновано модифікацію методу нечіткого порівняння на основі алгоритму «найдовших речень» зі спрощеною канонізацією та випадковими перестановками. Практична цінність отриманих в роботі результатів полягає в тому, що запропонований метод переважає в параметрах точності, повноти та швидкості базовий метод шинглів і його модифікації при нечіткому порівнянні електронних документів. Апробація роботи. Результати проміжних досліджень були представлені на: V науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг» ПМК-2013 (Київ, 17-19 квітня 2013р.
Mathematica - система комп'ютерної алгебри компанії Wolfram Research. Містить багато функцій як для аналітичних перетворень, так і для чисельних розрахунків. Крім того, програма підтримує роботу з графікою і звуком, включаючи побудову дво- і тривимірних графіків функцій, малювання довільних геометричних фігур, імпорт та експорт зображень і звуку.
Аспірáнт - основна форма підготовки наукових кадрів при вищих навчальних закладах і науково-дослідницьких установ. Час навчання в стаціонарній аспірантурі входить до наукового стажу і зараховується при призначенні пенсії за Законом України «Про наукову та науково-технічну діяльність».
Магі́стр - освітній ступінь, що здобувається на другому рівні вищої освіти та присуджується вищим навчальним закладом у результаті успішного виконання здобувачем вищої освіти відповідної освітньої програми.
Дослі́дження, до́сліди - (широко розуміючи) пошук нових знань або систематичне розслідування з метою встановлення фактів; (вузько розуміючи) науковий метод (процес) вивчення чого-небудь.
), міжнародній науково-технічній конференції «Інтелектуальні технології лінгвістичного аналізу» (Київ, 22-23 жовтня 2013р.) та VІІ науковій конференції магістрантів та аспірантів «Прикладна математика та комп’ютинг» ПМК-2015 (Київ, 15-17 квітня 2015р.). Впровадження роботи. Розробку було впроваджено, як систему для моніторингу унікальності статей на сайтах компанії «Сінево Україна». Структура та обсяг роботи. Магістерська дисертація складається з вступу, чотирьох розділів та висновків.
Те́хніка (від грец. techne - мистецтво, майстерність) - сукупність засобів, створених людством для обслуговування своїх потреб виробничого і невиробничого характеру. У техніці матеріалізовані знання і виробничий досвід, накопичені людством у процесі розвитку суспільного виробництва.
Моніторинг (англ. monitoring, нім. Monitoring n) - комплекс наукових, технічних, технологічних, організаційних та інших засобів, які забезпечують систематичний контроль (стеження) за станом та тенденціями розвитку природних, техногенних та суспільних процесів.
Мовозна́вство, також лінгві́стика - наука, що вивчає мову в усій складності її прояву; наука про мову взагалі й окремі мови світу як індивідуальних її представників. Це гуманітарна наука, яка є розділом культурології (нарівні з мистецтвознавством і літературознавством) і філології (нарівні з літературознавством), а також галуззю семіотики.
Дисерта́ція (лат. dissertatio - твір, обговорення, розсуд, доповідь) - спеціально підготовлена наукова праця на правах рукопису, яку виконують для прилюдного захисту на здобуття наукового ступеня. В Україні розрізняють дисертацію для здобуття наукового ступеня кандидата наук (кандидатська дисертація) та доктора наук (докторська дисертація).
У вступі подано загальну характеристику роботи, зроблено оцінку сучасного стану проблеми, обґрунтовано актуальність напрямку досліджень, сформульовано мету і задачі досліджень, показано наукову новизну отриманих результатів і практичну цінність роботи.
Актуа́льність (від лат. actualis - справжній, теперішній, сучасний, важливий у даний момент, злободенний, назрілий) - абстрактний іменник до прикметника «актуальний». Актуальність - важливість, значимість чого-небудь на сьогодні, сучасність, злободенність.
У першому розділі розглянуто класичні варіанти реалізації алгоритмів нечіткого порівняння, а також проведений аналіз, який дає змогу визначити основні переваги та недоліки існуючих алгоритмів. У другому розділі приведений опис запропонованої модифікації методу нечіткого порівняння на основі алгоритму «найдовших речень» зі спрощеною канонізацією та випадковими перестановками. У третьому розділі приведено опис програмного комплексу для порівняльної оцінки якісних і кількісних показників роботи методів нечіткого пошуку. У четвертому розділі приведено результати експериментальних досліджень та порівняльну характеристику існуючих і запропонованого методів нечіткого порівняння.
Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
Експериме́нт (англ. experiment) - сукупність дослідів, об’єднаних однією системою їх постановки, взаємозв’язком результатів і способом їх обробки. В результаті експерименту отримують сукупність результатів, які допускають їхню сумісну обробку і зіставлення.
У висновках підбитий підсумок по результатам проведеної роботи. Робота виконана на 82 аркуші, містить посилання на список використаних літературних джерел з 21 найменування. У роботі наведено 16 рисунків та 14 таблиць. Ключові слова: речення, релевантність, нечітке співпадіння, нечітке порівняння, шингл, канонізація, хеш-сума.
Релева́нтність (англ. relevance) - міра відповідності отримуваного результату бажаному.
ABSTRACT Theme urgency. Nowadays there are many different ways to find fuzzy matches in documents. The majority of them use the shingles method. This method shows high performance and acceptable accuracy and completeness of results. The disadvantage is that after the order of words changing in a sentence resulting hash sum will be differ from the checksum proposal without changes in the order. That is actually the same proposal will have different hash. In addition, the method is based on a comparison of shingles least 86 hash-sums of proposals and modified the proposal may not get there on their list. As a result, the modified sentence can lead to the fact that two similar documents will be unequal. To solve this problem, we propose to use an approach that is based on the selection of proposals with the greatest total length of words and random permutations of words in sentences. It is expected that the selection of the proposals with the greatest total length of words to help increase the accuracy and completeness of the results. This allows, in certain cases improve overall fuzzy comparison. It is also proposed to modify the approach to the canonization of texts. Object of research is a comparison of fuzzy electronic documents. Subject of research is to assess the duration of the work, the accuracy and completeness of the results of various modifications of the algorithms and fuzzy comparison algorithm long sentences with a random permutations. Research objective: to design the software package for the analysis of the effectiveness of the main methods of searching for fuzzy matches, compared with the proposed algorithm long sentences with a random permutations. Scientific novelty consists in the following: 1. A method of fuzzy comparison algorithm based on long sentences with a random permutations. Practical value of the obtained results is that the proposed method can change the basic modern fuzzy-search methods in future. Approbation. The intermediate results of the studies were presented at the V Scientific Conference of PhD students and undergraduates «Applied mathematics and computing» AMC-2013 (Kyiv, 17-19 April 2013), the international scientific conference «Intelligent technology of linguistic analysis»(Kyiv, 22-23 October 2013), VII Scientific Conference of PhD students and undergraduates «Applied mathematics and computing» AMC-2015 (Kyiv, 15-17 April 2015). Implementation. Library based on algorithm was implemented as a system for monitoring uniqueness articles online directory of Synevo Ukraine. Structure and content of the thesis. Masters thesis consists of an introduction, four chapters and conclusions. The introduction presents the General characteristics of the work, the estimation of modern condition of the problem, the actuality of research directions, formulated goal and tasks of research, shows scientific novelty of the results and practical value of the work. The first section deals with classical ways of realization of operations amounts for the module using technologies FPGA, as well as the analysis, which allows to determine the main advantages and disadvantages of selected structures.. The second section describes the software for the comparative evaluation of qualitative and quantitative indicators of fuzzy search methods. The third section describes the proposed modification of the method of comparison based on fuzzy algorithm long sentences with a random permutations. The fourth section presents the results of experimental studies and comparative characteristics of the existing and proposed methods of fuzzy comparison. In Conclusion, summed up the results of work. Work carried out on 82 sheets, contains links to the list of the used literature with 21 items. The work contains 16 drawings and 14 tables. Keywords: fuzzy matching, fuzzy comparison, shingle, canonization, hash. РЕФЕРАТ Актуальность темы. В наше время существует много различных способов нахождения нечетких совпадений в электронных документах. Подавляющее большинство из них использует за основу метод шинглов. Этот метод демонстрирует высокую скорость работы и приемлемые точность и полноту результатов. Недостатком классической реализации метода является то, что после смены порядка слов в предложении полученая хэш-сумма, будет отличаться от хэш-суммы предложения без изменений в порядке слов. То есть фактически одинаковый предложения будут иметь разные хэш-суммы. Кроме того, метод шинглов базируется на сравнении 84 наименьших хэш-сумм предложений и модифицированное предложение может вообще не попасть в их список. В результате, модифицированный порядок слов может привести к тому, что два очень похожие электронные документы будут иметь близкий к нулю показатель схожести. Для решения этой проблемы предлагается использование подхода, который заключается на основе отбора предложений с наибольшей суммарной длиной слов и случайных перестановок слов в предложениях. Предполагается, что отбор предложений с наибольшей суммарной длиной слов поможет повысить точность и полноту результатов. Это позволит в определенных случаях повысить эффективность нечеткого сравнения в целом. Также предлагается модифицировать подход к канонизации текстов. В частности - отказаться от словарей служебных слов, взяв за правило, что любое слово, длиной меньше 4 - не несет информационного содержания для сравнения. Это поможет уменьшить время работы алгоритма в целом и на этапе канонизации в частности. Объектом исследования является нечеткое сравнение электронных документов. Предметом исследования является оценка продолжительности работы, точности и полноты результатов различных модификаций алгоритмов нечеткого сравнения и алгоритма «длинных предложений» с упрощенной канонизацией и случайными перестановками. Цель работы: предложить программный комплекс для анализа эффективности работы основных методов поиска нечетких совпадений, по сравнению с предложенным алгоритмом «длинных предложений» с упрощенной канонизацией и случайными перестановками. Научная новизна заключается в следующем: 1. Предложено модификацию метода нечеткого сравнения на основе алгоритма «длинных предложений» с упрощенной канонизацией и случайными перестановками. Практическая ценность полученных в работе результатов заключается в том, что предложенный метод преобладает по параметрам точности, полноты и скорости выполнения над базовым методом шинглов и его модификациями при нечетком сравнении электронных документов. Апробация работы. Результаты промежуточных исследований были представлены на: V научной конференции магистрантов и аспирантов «Прикладная математика и компьютинг» ПМК-2013 (Киев, 17-19 апреля 2013), международной научно-технической конференции «Интеллектуальные технологии лингвистического анализа» (Киев, 22-23 октября 2013) и VII научной конференции магистрантов и аспирантов «Прикладная математика и компьютинг» ПМК-2015 (Киев, 15-17 апреля 2015). Внедрение работы. Разработка была внедрена, как система для мониторинга уникальности статей на сайтах компании «Синэво Украина». Структура и объем работы. Магистерская диссертация состоит из введения, четырех глав и выводов. Во введении представлена ​​общая характеристика работы, произведена оценка современного состояния проблемы, обоснована актуальность направления исследований, сформулированы цели и задачи исследований, показано научную новизну полученных результатов и практическую ценность работы. В первом разделе рассмотрены классические варианты реализации алгоритмов нечеткого сравнения, а также проведен анализ, который позволяет определить основные преимущества и недостатки существующих алгоритмов. Во втором разделе приведено описание предложенных модификации метода нечеткого сравнения на основе алгоритма «длинных предложений» с упрощенной канонизацией и случайными перестановками. В третьем разделе приведены описание программного комплекса для сравнительной оценки качественных и количественных показателей работы методов нечеткого поиска. В четвертом разделе приведены результаты экспериментальных исследований и сравнительная характеристика существующих и предложенного методов нечеткого сравнения. В выводах подведен итог по результатам проведенной работы. Работа выполнена на 82 листах, содержит ссылки на список использованных литературных источников из 21 наименование. В работе приведены 16 рисунков и 14 таблиц. Ключевые слова предложение, релевантность, нечеткое совпадение, нечеткое сравнение, шингл, канонизация, хеш-сумма.


Скачати 73.88 Kb.