Алгоритм зіставлення шаблонів пошуку з вхідними рядками для визначення можливостей браузера
| dc.contributor.advisor | Ковалюк, Тетяна Володимирівна | |
| dc.contributor.author | Блажко, Ігнат Олегович | |
| dc.date.accessioned | 2019-06-04T13:44:06Z | |
| dc.date.available | 2019-06-04T13:44:06Z | |
| dc.date.issued | 2019-05 | |
| dc.description.abstracten | Nowadays, many companies and businesses that operate on the Internet, need to have all possible information about users. One of the most effective ways to get this information is to analyze user-agent request header, because this header contains information about the user's browser, the platform that this browser uses, the list of browser capabilities, and more. Using the information received, the business can customize the processing of customer requests depending on the type of traffic, whether mobile phone or computer, you can decide what content will be sent to the requesting device, or even adapt the content on the fly. But analysis of the user-agent header is not a trivial task. There are many libraries that solve this task by balancing between the accuracy of the results and the time to get that result. There are even services that help analyze user-agent headers, such as deviceatlas.com. The desired accuracy can be obtained by using databases of user-agent patterns from browscap.org, which are always up-to-date. But, currently, there are more than two hundred thousand patterns, and their number keeps growing. Existing solutions are not able to process them quickly, while the time of the response to the customer is another vital indicator for the business. Therefore, there is a need for fast and accurate methods of analyzing user-agents patterns, that is, the methods of fast multi-pattern matching with wildcards to detect browser capabilities. The work communication with academic programs, plans, themes. The work was carried out at the Department of Computer-Aided Management And Data Processing Systems of the National Technical University of Ukraine ”Igor Sikorsky Kyiv Polytechnic Institute” within the initiative theme "Intelligent text processing systesms". The purpose of the research is to develop an algorithm for multi-pattern matching with wildcards to be able to detect browser capabilities based on browscap.org data. The library should work faster than its alternatives - the speed should be comparable to libraries that use simplified (inaccurate) methods to detect browser capabilities. To achieve the goal, we need to do the following: figure out browscap.org data structure and similarities between different user agents of the same family; review and analyze existing studies that solve the problem of multi-pattern matching with wildcards; select applicable algorithms and methods for solving the problem and conduct a series of tests; based on obtained results, either adjust the existing algorithm to the task or develop a new one; implement the prototype of the algorithm; analyze results. Object of the research – text processing system. Subject of research – methods and algorithms of multi-pattern matching with wildcards. The scientific novelty of the results obtained is a new algorithm for multi-pattern matching with the best known lower bound time complexity. The practical value of the results obtained is a creation of a software package (library) that can analyze user-agent request HTTP header in a fast and accurate way which allows detecting capabilities of client browser. Additionally to that, the library database can be updated without the need of library version update. Comparing with other libraries that scan the full list of patterns from browscan.org – produced software package allows to make the same analysis, but much faster than ever, thus allowing users of this library not to compromise between the speed of the results and their accuracy. Publications. The results of the research were published during of the All-Ukrainian Scientific and Practical Conference of Young Scientists and Students "Information Systems and Technologies of Management" (ISTU-2019) and the V International Scientific and Practical Conference "Computing Intellect". | uk |
| dc.description.abstractuk | На сьогоднішній день для багатьох компаній та бізнесів які здійснюють свою діяльність в мережі інтернет необхідність у визначенні усієї можливої інформації про користувача стоїть дуже гостро. Один з найбільш дієвих шляхів отримання такої інформації – це аналіз user-agent заголовку запиту користувача, тому що використовуючи цей заголовок можна отримати інформацію про браузер користувача, платформу яку цей браузер використовує, перелік можливостей браузера та інше. Використовуючи отриману інформацію бізнес може налаштувати обробку запитів клієнтів в залежності від типу трафіку, чи то мобільний телефон чи то комп’ютер, можна вирішити який вміст буде відправлено до запитуючого пристрою, або навіть адаптувати вміст на льоту. Але аналіз user-agent заголовку не є тривіальним завданням. Існує багато бібліотек які вирішують цю задачу балансуючи між точністю та швидкістю отримання результатів. Існують навіть сервіси, що надають послуги по визначенню та аналізу user-agent заголовку, такі як deviceatlas.com. Проблема точності може бути вирішена використовуючи відкриті списки user-agent шаблонів з browscap.org, які постійно оновлюються. Наразі таких шаблонів більше ніж двісті тисяч та вони постійно поповнюються – наявні рішення не в змозі швидко їх обробляти, в той час як швидкість повернення відповіді до клієнта є іншим життєво важливим показником для бізнеса. Тому виникає необхідність в швидких методах аналізу цих шаблонів, а саме методах швидкого зіставлення великої кількості шаблонів пошуку з user-agent екземплярами. Зв'язок роботи з науковими програмами, планами, темами. Робота виконувалась на кафедрі автоматизованих систем обробки інформації та управління Національного технічного університету України «Київський політехнічний інститут ім. Ігоря Сікорського» в рамках ініціативної теми «Інтелектуальні системи обробки тексту». Мета дослідження – розробити алгоритм зіставлення шаблонів пошуку з вхідними рядками та програмне застосування (бібліотеку) для вирішення задачі визначення можливостей браузера на основі даних з browscap.org. Бібліотека повинна працювати швидше за своїх аналогів – швидкість роботи повинна бути порівнянною з бібліотеками для визначення можливостей браузера які використовують спрощенні (неточні) схеми визначення можливостей браузера. Для досягнення поставленої мети необхідно виконати наступні завдання: дослідити дані про агенти користувача з browscap.org, їх структуру та залежності між різними агентами користувача одного сімейства; виконати огляд досліджень та отриманих результатів з розв’язання задачі зіставлення шаблонів пошуку з вхідними рядками; обрати ряд алгоритмів та методів розв’язання задачі зіставлення шаблонів пошуку з вхідними рядками та провести ряд випробувань; на основі проведеного аналізу здійснити прискорення існуючого алгоритму або розробити новий; розробити програмну реалізацію алгоритму; провести порівняння швидкості роботи запропонованого алгоритму з бібліотеками-аналогами, такими що засновані на даних з browscap.org так і іншими, що дають приблизні результати; провести аналіз отриманих результатів. Об’єкт дослідження – система обробки тексту. Предмет дослідження – методи зіставлення шаблонів пошуку з екземплярами текстів. Наукова новизна отриманих результатів полягає у отриманні алгоритму зіставлення довільної кількості шаблонів пошуку з екземпляром тексту з найкращою часовою оцінкою складності з низу серед існуючих та її практичним підтвердженням. Практичне значення одержаних результатів полягає у створенні програмного застосування, яке здатне аналізувати заголовок запитів user-agent та точно та повно визначати усі характеристики та можливості браузера клієнта. Бібліотека дозволяє динамічне додавання нових екземплярів до бази агентів користувачів, без необхідності оновлення версії бібліотеки. Порівнюючи з аналогами які роблять повну перевірку за списком даних з browscap.org – отриманий програмний продукт робить той самий аналіз в рази швидше, тим самим дозволяючи користувачам цієї бібліотеки не обирати між швидкістю отримання результатів та їх повнотою та точністю. Публікації. Результати проведених досліджень були опубліковані у в рамках всеукраїнської науково-практична конференція молодих вчених та студентів «Інформаційні системи та технології управління» (ІСТУ-2019) та на V Міжнародна науково-практична конференція «Обчислювальний інтелект». | uk |
| dc.format.page | 58 с. | uk |
| dc.identifier.citation | Блажко, І. О. Алгоритм зіставлення шаблонів пошуку з вхідними рядками для визначення можливостей браузера : магістерська дис. : 126 Інформаційні системи та технології / Блажко Ігнат Олегович. - Київ, 2019. - 58 с. | uk |
| dc.identifier.uri | https://ela.kpi.ua/handle/123456789/27812 | |
| dc.language.iso | uk | uk |
| dc.publisher.place | Київ | uk |
| dc.subject | зіставлення шаблонів пошуку | uk |
| dc.subject | символи підстановки | uk |
| dc.subject | агент користувача | uk |
| dc.subject | можливості браузера | uk |
| dc.subject | browsecap | uk |
| dc.subject | multi-pattern mathcing | uk |
| dc.subject | wildcards | uk |
| dc.subject | variable length don’t care | uk |
| dc.subject | browser capabilities | uk |
| dc.subject | user agent | uk |
| dc.subject | browsecap | uk |
| dc.subject.udc | 681.3.01 | uk |
| dc.title | Алгоритм зіставлення шаблонів пошуку з вхідними рядками для визначення можливостей браузера | uk |
| dc.type | Master Thesis | uk |
Файли
Контейнер файлів
1 - 1 з 1
Ескіз недоступний
- Назва:
- Blazhko_magistr.docx
- Розмір:
- 2.29 MB
- Формат:
- Microsoft Word XML
- Опис:
Ліцензійна угода
1 - 1 з 1
Ескіз недоступний
- Назва:
- license.txt
- Розмір:
- 1.86 KB
- Формат:
- Item-specific license agreed upon to submission
- Опис: