Використання функції В. Левенштейна при тематичному пошуку інформації
Обґрунтування доцільності використання функції В. Левенштейна при тематичному пошуку інформації. Етапи процесу виконання пошуку створеним емулятором. Виконання перевірки введеного слова на наявність його у складеному словнику с транслітераціями.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | украинский |
| Дата добавления | 23.12.2018 |
| Размер файла | 33,7 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru//
Размещено на http://www.allbest.ru//
Використання функції В. Левенштейна при тематичному пошуку інформації
Савчук Т.О
Зростання потужності мережі Інтернет привело до підвищення складності пошуку інформації у множині Web-сторінок і файлів. Нині для цього використовуються спеціальні пошукові системи, які містять постійно оновлювану інформацію у Web-сторінках і файлах на серверах Інтернету. Пошукові системи містять тематично організовану інформацію про інформаційні ресурси Всесвітньої павутини в базах даних. Спеціальні програми-роботи періодично «обходять» Web-сервери, зчитують інформацію, що зустрічається, виділяють в ній ключові слова і заносять в базу даних мережі Інтернет.
Отже, актуальним, при вирішенні задачі пошуку інформації за визначеною тематикою, є використання функції Левенштейна, що сприятиме підвищенню результативності пошуку у потужних множинах файлів, документів та на Web-сторінках.
Якщо припустити, що відома ціна перетворення x(1, i-1) в y(1, j), то ціну перетворення x(1, i) в y(1, j) ми отримаємо, додавши до неї ціну видалення xi. Аналогічно, ціну перетворення x(1, i) в y(1, j) можна отримати, додавши ціну вставки yj до ціни перетворення x(1, i) в y(1, j-1). Нарешті, знаючи ціну перетворення x(1, i-1) в y(1, j-1), ціну перетворення x(1, i) в y(1, j) ми отримаємо, додавши до неї ціну заміни xi на yj
Перед тим, як почати обчислювати di,j, треба встановити граничні значення масиву. Що стосується першого стовпця масиву, то значення di,0 дорівнює сумі цін видалення перших символів x. Аналогічно, значення d0,j першого рядка задаються сумою цін вставки перших j символів y. Отже, маємо наступне:
d0,0=0 (1)
(2)
(3)
Особливістю всіх алгоритмів нечіткого пошуку з індексацією є те, що індекс будується за словником, складеним по вихідному тексту або списку записів у будь-якій базі даних.
Як видно за результатами проведеного аналізу кожен з алгоритмів пошуку має як недоліки так і переваги. За результатами досліджень було реалізовано емулятор нечіткого пошуку, який засновано на методах «Відстань Левенштейна» та метафон.
В результаті виконання даних досліджень був реалізований емулятор нечіткого пошуку засобами мови програмування PHP, з функцією подібній до «Мабуть, ви мали на увазі...», яка має реалізацію у всіх пошукових системах, зокрема Google i Yandex.
Для виправлення помилок в словах було вирішено застосувати такі алгоритми, як «Відстань Левенштейна», «Метафон». Приклад:
Щоб перетворити слово «небо» на слово «треба» необхідно зробити дві заміни та одну вставку, відповідно відстань Левенштейна становить 3:
небо > неба (замінюємо «о» на «а»)
неба > реба (замінюємо «н» на «р»)
реба > треба (вставляємо «т»)
Для розрахунку відстані Левешнтейна найчастіше використовується простий алгоритм, в якому використовується матриця розміром (n + 1) * (m + 1), де n і m - довжини порівнювальних рядків. Окрім цього вартість операції вилучення, заміни та вставка вважається однаковим. Для конструювання матриці використовується таке рекурентне рівняння:
(4)
Цей алгоритм легко реалізується в ручну заповнивши таблицю. Наприклад, для визначення відстані між словами «корабель» і «бал» таблиця матиме такий вигляд:
е - т. зв. пусте слово, без літер
е К О Р А Б Е Л Ь
е 0 1 2 3 4 5 6 7 8 /*тобто відстань між пустим словом і словом К О Р А Б Е Л Ь = 8 (довжина слова корабель)*/
Б 1 1 2 3 4 4 5 6 7 /*між Б і КОРАБЕЛЬ відстань = 7 (літера Б в обох словах і може бути використана) */
А 2 2 2 3 3 4 5 6 7 /* між БА і КОРАБЕЛЬ відстань = 7 (лише одну з літер Б або А можна використати) */
Л 3 3 3 3 4 4 5 5 6 /* між БАЛ і КОРАБЕЛЬ відстань = 6 (можна використати дві літери (Б або А) +Л) */
Для визначення послідовності операцій необхідних для переходу від одного слова до іншого потрібно знайти найдешевший шлях від першої [0,0] клітки матриці до останньої [i, j]. Як видно із прикладу існує декілька еквівалентних шляхів і алгоритм не тільки вираховує мінімальну відстань але й усі шляхи, використовуючи у кожному наступному кроці інформацію здобуту у попередніх кроках (принцип динамічного програмування)
Процес виконання пошуку створеним емулятором складається з деяких етапів. Перший етап - це виконання функції транслітерації російських слів на літери латинського алфавіту. Вона потрібна для того, щоб можна було правильно визначити відстань Левенштейна для слів. Реалізація цього методу досить проста. Вхідним параметром методу є строка, яку потрібно транслітерувати. В результаті виконання функціє буде повернута транслітеровано. левенштейн пошук слово тематичний
Далі ми будемо виконувати перевірку введеного слова на наявність його у складеному словнику с транслітераціями. Якщо даного слова не було знайдено у словнику, то ми проводимо транслітерацію отриманого слова. Після цього запускається цикл, який буде вибирати з масиву ті слова, відстань Левенштейна між «метафонами» яких не буде перевищувати половину «метафона» введеного слова (грубо кажучи, допускається до половини неправильно написаних приголосних букв), потім, серед вибраних варіантів, знову перевіряємо відстань, але не по всьому слову, а з його «метафону» і слова, які підійшли записуємо в масив.
Далі задамо змінні, де відстань Левенштейна буде рівна завідомо великому числу, а схоже слово - завідомо мале число. Це потрібно для визначення максимального значення «подібності» між нашим словом і словами в масиві, а також мінімальної відстані Левенштейна. Для початку знайдемо мінімальну відстань Левенштейна. Далі будемо шукати максимальне значення «подібності» для тих слів, в яких відстань Левенштейна буде мінімальною. Наступним кроком виконання алгоритму буде запуск циклу, який підбере всі слова з найменшою відстанню Левенштейна і найбільшим значенням «подібності» одночасно. Після цього визначаємо максимальне значення «подібності» між «метафонами» нашого слова і слів у масиві, і мінімальну відстань Левенштейна.
В результаті опрацювання інформації за запропонованим алгоритмом формується масив, який міститиме одне слово. Після чого функція Левенштейна поверне «правильне» слово, яке зберігається як ключ у масиві словника. Отже, не зважаючи на потужність слоника відмінок, рід та час (мови) результат тематичного пошуку буде достатньо точним.
Размещено на Allbest.ru
...Подобные документы
Технологія пошуку інформації в мережі Інтернет. Можливості спеціальних служб, індексів. Інформаційні ресурси у каталогах. Системи мета-пошуку, пошуку в конференціях Usenet, пошуку людей. Знаходження інформації із застосуванням серверів глобального пошуку.
реферат [38,8 K], добавлен 20.05.2011Історія розвитку і створення Інтернет. Протоколи передачі даних. Способи організації пошуку інформації Інтернет. Пошукові системи та сервіси: Яндекс, Google, шукалка. Послідовність виконання пошуку необхідної інормації за допомогою браузера Mozilla.
дипломная работа [4,9 M], добавлен 22.07.2015Особливості та методика пошуку інформації та об’єктів у зовнішній пам’яті комп’ютера, в мережі або операційній системі Windows. Специфіка використання автономної й онлайнової довідки операційної системи. Параметри пошуку в прихованих або системних папках.
конспект урока [885,7 K], добавлен 03.01.2010Дослідження можливостей пошуку в Google за тематикою. Використання можливості розширеного тематичного пошуку для підвищення релевантності пошуку за встановленим завданням. Розширений пошук зображень. Особливості пошуку щодо країн та наукових знань.
контрольная работа [4,6 M], добавлен 03.02.2014Галузі застосування та принцип роботи мови програмування "Пролог". Керування процесом пошуку рішень, типи даних та використання списків. Рекурсивні процедури та цикли за допомогою пошуку з поверненням. Виконання арифметичних та логічних операцій.
курс лекций [99,7 K], добавлен 06.07.2011Використання автоматичних систем інформаційного пошуку для зменшення "інформаційного перевантаження". Методи організації пошуку: атрибутивний, повнотекстовий і вибірка видань. Тематичні каталоги та пошукові машини. Системи Yandex, Rambler та Google.
реферат [333,0 K], добавлен 18.05.2011Обробка масивів формалізованих записів, їх застосування у базах даних підприємств для пошуку інформації про об’єкт. Вимоги до програмного продукту і документації; його структура і функціональна схема. Посібник користувача, умови виконання програми.
курсовая работа [391,0 K], добавлен 13.10.2012Принципові рішення, що покладені в основу концепції створення єдиних реєстрів. Критерії для відбору стратегії пошуку правової інформації в Інтернеті. Модель ділового процесу, її використання у Workflow-системах. Організаційне забезпечення ІС ОВС України.
контрольная работа [23,3 K], добавлен 20.07.2011Архітектура Web-баз даних. Загальні відомості про мову SQL. Створення таблиць баз даних. Використання бібліотеки для пошуку інформації. Аутентифікація за допомогою РНР й MySQL. Зберігання паролів в окремому файлі на сервері, використання бази даних.
курсовая работа [913,8 K], добавлен 12.01.2010Опис організаційної структури автоматизації пошуку кур'єра для виконання замовлення в фірмі "Екіпаж-Сервіс". Побудова умовно замкненої моделі. Побудова дерева цілей і дерева функцій автоматизації. Створення DFD-діаграми та опис форм документів (шаблонів).
курсовая работа [1,1 M], добавлен 12.04.2014Характеристика особливостей реалізації пошуку по масиву методами лінійним, бінарним, по "дереву Фібоначе" та екстраполярним на мові програмування Turbo Pascal. Використання алгоритма Рабіна-Карпа та Кнута-Морріса-Пратта для знаходження підрядка в рядку.
курсовая работа [51,0 K], добавлен 16.09.2010Проблема порушення авторських прав в Інтернеті. Системи та сервіси пошуку плагіату. Захист електронних видань від плагіату в Інтернеті. Алгоритми аналізу, подання і порівняння текстової інформації. Вибір методу пошуку текстових документів з запозиченнями.
магистерская работа [1,0 M], добавлен 14.06.2013Функції систем захисту інформації, основні терміни та визначення. Введення в криптологію, нормативно-правова база захисту інформації. Впровадження новітніх інформаційних телекомунікаційних системи. Використання та здійснення електронного документообігу.
реферат [24,0 K], добавлен 03.10.2010Перетворення вхідних даних великого розміру в дані фіксованого розміру. Алгоритми хешування з різними характеристиками. Криптографічні хеш-функції та їх використання. Застосування хешування для прискорення пошуку даних, перевірка парольної фрази.
презентация [80,7 K], добавлен 14.08.2013Неекспортовані символи ядра. Оптимальний підхід до реалізації пошуку символів у ядрі. Виконання, підміна, додавання та приховання системних викликів. Завантаження модуля ядра із програмного коду та з коду іншого модуля. Робота з UNIX-сигналами.
курсовая работа [84,0 K], добавлен 23.05.2013Методи результативного пошуку інформації в Інтернеті. Уявлення про пошукові служби, їх призначення та структура. Основні типи пошукових служб: пошукові каталоги, рейтингові системи, індексні бази даних. Спрямованість тематики і широта охоплення ресурсів.
реферат [33,5 K], добавлен 23.04.2010Основні математичні функції табличного процесора Excel, особливості та правила їх використання. Основи мови макросів, порядок їх запису та виконання. Поняття та характерні риси макрофункцій, їх призначення та правила використання в програмі Excel.
контрольная работа [19,6 K], добавлен 16.10.2009Процеси пошуку інформацій та розробка структури даних для ефективного зберігання та обробки інформації. Як приклад розглянуто бінарне дерево. Бінарні структури широко використовуються у житті,широко використовуються в багатьох комп'ютерних завданнях.
курсовая работа [67,7 K], добавлен 24.06.2008Дослідження проблеми пошуку автомобілів та постановка задачі створення автокаталогу з використанням мови програмування PHP і JаvаScrіpt. Дослідження моделей прецедентів системи та їх класової архітектури. Моделювання розподіленої конфігурації систем.
курсовая работа [3,7 M], добавлен 11.10.2010Аналіз властивостей безкоштовних пошукових та поштових серверів Інтернету. Огляд методики ранжирування результатів пошуку в інформаційно-пошукових системах бібліотек. Вивчення можливостей пошукової системи "Мета", пошуку по реєстру українських сайтів.
курсовая работа [142,9 K], добавлен 17.11.2011
