Використання функції В. Левенштейна при тематичному пошуку інформації за алгоритмом Метафон

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Вінницький національний технічний університет

Використання функції В. Левенштейна при тематичному пошуку інформації за алгоритмом Метафон

Т. О. Савчук

Вступ

Зростання потужності мережі Інтернет привело до підвищення складності пошуку інформації у множині Web-сторінок і файлів. Нині для цього використовуються спеціальні пошукові системи, які містять постійно оновлювану інформацію у Web-сторінках і файлах на серверах Інтернету. Пошукові системи містять тематично організовану інформацію про інформаційні ресурси Всесвітньої павутини в базах даних. Спеціальні програми-роботи періодично «обходять» Web-сервери, зчитують інформацію, що зустрічається, виділяють в ній ключові слова і заносять в базу даних мережі Інтернет.

Принцип дії таких каталогів не відрізняється від тематичних каталогів бібліотек. Звернувшись на адресу пошукового каталогу, користувач знаходить на його основній сторінці перелік тематичних категорій, наприклад, таких, як Освіта, (Education), Наука (Science), Бізнес (Business), Мистецтво (Art) тощо. Як правило, такі каталоги є ієрархічними гіпертекстовими меню з визначеною тематикою сайтів, адреси яких містяться в цьому каталозі, з послідовним уточненням теми. Працювати з пошуковими каталогами просто - пошук інформації відбувається на інтуїтивному рівні і у більшості випадків закінчується успіхом. Однак, після цієї простої процедури слідує більш складна по створенню і ведення каталогу. При цьому, пошукові каталоги створюються вручну. Висококваліфіковані редактори переглядають інформаційний Web-простір, відбираючи те, що на їхню думку більше цікавить користувача, і заносять відповідні адреси до каталогу [2]. Але, при розробці інтелектуальних систем, знання про конкретну предметну область, для якої створюється система, рідко бувають повними й абсолютно достовірними (навіть кількісні дані, отримані шляхом досить точних експериментів, мають невисокі статистичні оцінки вірогідності, надійності). Цей факт значно ускладнює тематичний пошук інформації, оскільки не враховується відмінність двох послідовних символів (рядків). Обчислення відстані В.Левенштейна, як мінімальної кількості операцій вставки, видалення і заміни, необхідних для перетворення одної послідовності в іншу [3] при проведенні такого пошуку інформації, може значно вплинути на його ефективність.

Отже, актуальним, при вирішенні задачі пошуку інформації за визначеною тематикою, є використання функції В.Левенштейна, що сприятиме підвищенню результативності пошуку у потужних множинах файлів, документів та на Web-сторінках.

Порівняльний аналіз алгоритмів тематичного пошуку інформації

Серед основних алгоритмів що використовуються при тематичному пошуку інформації слід відзначити такі.

Поки найбільш поширеним є саме пошук за текстовими документами. Такими документами можуть бути Web-сторінки, документи в форматі doc, rtf, txt і інші. Останнім часом з'явився новий тип пошукових движків серед XML-даних різного типу, а також заснованих на технології RSS. При цьому, методи та алгоритми, що використовуються, базуються на різних підходах до вирішення проблеми - одні з них орієнтуються на точний пошук, інші аналізують властивості метрики для побудови різних просторових структур тощо [2].

1. Метафон є одним з найбільш поширених фонетичних алгоритмів перетворення вихідного слова з урахуванням правил англійської мови, використовуючи складні правила. В процесі перетворення втрачається значно менше інформації, так як букви не розбиваються на групи. На першому кроці алгоритму по вихідному тексту будується словник, що містить слова і їх позиції в тексті. Також, можна підраховувати частоти використання слів і словосполучень для поліпшення якості результатів пошуку. Залежність розміру словника від обсягу тексту не є строго лінійною - до деякого обсягу формується базовий каркас слів, що становить від 15% на 500 тисячах слів до 5% на 5 мільйонів, і потім залежність наближається до лінійної, повільно прагнучи до 0,5% на 680 мільйонів слів. Подальше збереження зростання забезпечується здебільшого за рахунок рідкісних слів. На рисунку 1 зображена залежність розміру словника від обсягу тексту. Але при використанні алгоритму «Метафон» у результуючому наборі можуть містяться слова які не відповідають тематичному пошуку. І при цьому залишається багато зайвих слів, в основному завдяки тому, що голосні не ігноруються, а перетворюються і використовуються в підсумковому коді

2. Лінійний пошук - алгоритм послідовного пошуку знаходження заданого значення довільної функції на деякому її відрізку. Цей алгоритм є найпростішим алгоритмом пошуку і на відміну, наприклад, від двійкового пошуку, не накладає жодних обмежень на функцію і має просту реалізацію. Пошук значення функції здійснюється простим порівнянням чергового розглянутого значення (як правило пошук відбувається зліва направо, тобто від менших значень аргументу до більших) і, якщо значення збігаються (з тією або іншою точністю), то пошук вважається завершеним. Недоліком лінійного пошуку є те що, його зазвичай використовують лише тоді, коли відрізок пошукової системи містить дуже мало елементів, і при тому що його не можна застосувати при почному пошуку інформації він вимагає додаткової пам'яті або обробки/аналізу функції.

3. Пошук за критерієм вартості - враховується не кількість етапів, що вже наявні в шляху, а тільки їх сумарна вартість. Тому процедура цього пошуку може увійти в нескінченний цикл, якщо виявиться, що в ній розгорнутий вузол, що має дію з нульовою вартістю, які знову вказують на той же стан. Можна гарантувати повноту пошуку за умови, що вартість кожного етапу більше або дорівнює деякій невеликій додатній константі е. Ця умова є також і достатньою для забезпечення оптимальності. Вона означає, що вартість шляху завжди зростає по мірі проходження по цьому шляху.Із заданої властивості легко визначити, що такий алгоритм розгортає шляхи в порядку зростання вартості шляху. Тому перший цільовий вузол, обраний для розгортання, представляє собою оптимальний розв'язок. (Нагадаємо, що в процедурі пошуку в дереві перевірка цілі застосовується лише до тих вузлів, які обрані для розгортання.) Проте використання цього алгоритму при тематичному пошуку інформації не є доцільним, тому що, чим більше інформації потрібно буде обробляти тим більше часу і ресурсів потребуватиме даний алгоритм. А в деяких випадках він може зациклитись, що призведе до небажаних результатів при роботі пошукової системи.

Результати порівняльного аналізу алгоритмів тематичного пошуку інформації.

Таблиця 1 - Результати порівняльного аналізу алгоритмів тематичного пошуку інформації

Покращити наведені у таблиці 1 характеристики можна, якщо врахувати тематичність чи направленість шуканої інформації. Цього можна досягти введенням додаткової функції аналізу відстаней шуканих довжин порівнювальних рядків, в якості якої може бути використаною функція В. Левенштейна [2].

Таким чином, актуальною задачею є підвищення ефективності тематичного пошуку інформації.

Постановка задачі тематичного пошуку інформації

Нехай i і j - довжини порівнюваних рядків або слів, а l - кількість порівнювальних рядків або слів.

При цьому, di,j є відстанню між префіксами рядків x і y, довжини яких дорівнюють, відповідно, i та j, тобто:

di,j=d(x(l, i), y(l, j)). (1)

позначимо через w(a, b).

Введемо такі позначення:

w(a, b) - це ціна заміни одного символу на інший коли a!= b (ціну перетворення символу a на символ b),

w(a, ?) - ціна видалення з cимволу a,

w(D, b) - ціна вставки в cимвол b.

Тоді, якщо

w(a, е)=1 , (2)

w(е, b)=1, (3)

w(a, b)=1, a!=b , (4)

w(a, b)=0, a=b, (5)

то di,j* є відстанню Левенштейна.

Результати обчислень відстані di,j за допомогою рекурентного співвідношення:

di,j=min{di-1, j+w(xi, е), di, j-1+w(е, yj), di-1, j-1+w(xi, yi)}. (6)

формують масив розмрністю (m +1) * (n +1),

Слід знайти мінімальну ціну перетворення x(1, j) в y(1, j), з урахуванням відстані В.Левенштейна di,j,* що визначаюєься тематикою пошуку інформації.

Використання функції В. Левенштейна при тематичному пошуку інформації

Особливістю всіх алгоритмів нечіткого пошуку з індексацією є те, що індекс будується за словником, складеним за вихідним тексому або списком записів у будь-якій базі даних.

Якщо припустити, що відома ціна перетворення 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 (7)

(8)

(9)

Означений підхід реалізовано у модифікованому алгоритмі, що базується на алгоритмі Метафон з урахуванням функції В.Левенштейна», який, в свою чергу, покладено в основу функціонування запропонованого емулятора нечіткого пошуку з використанням засобами мови програмування PHP. Означений емулятор має функцію «Мабуть, ви мали на увазі...», яка реалізована у таких пошукових системах як Google, Yandex та ін.

Розглянемо приклад виконання тематичного пошуку інформації з використанням запропонованого підходу аби виконати поставлену задачу дослідження. левенштейн метафон пошук інформація

Щоб перетворити слово «небо» на слово «треба» необхідно зробити дві заміни та одну вставку, відповідно відстань В.Левенштейна становить 3:

небо > неба (замінюємо «о» на «а»)

неба > реба (замінюємо «н» на «р»)

реба > треба (вставляємо «т»)

Для розрахунку відстані В.Левенштейна найчастіше використовується простий алгоритм, в якому формується матриця розміром (n + 1) * (m + 1), де n і m - довжини порівнювальних рядків. При цьому, вартість операції вилучення, заміни та вставка вважається однаковою. Для конструювання матриці використовується таке рекурентне відношення:

(10)

Результат роботи запропонованого алгоритму визначення відстані В.Левенштейна між словами «корабель» і «бал» такий:

нехай е - пусте слово (слово без літер). Тоді маємо

е К О Р А Б Е Л Ь

е 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]. Як видно із прикладу, запропонований алгоритм не тільки пропонує рішення за обрахованою мінімальною відстанню, але й знаходить всі еквівалентні шляхи тематичного пошуку, використовуючи у кожному наступному кроці інформацію, здобуту у попередніх кроках (принцип динамічного програмування).

Основні етапи функціонування запропонованого емулятора представлено схемою відповідного алгоритму рисунку 2.

Перший крок - це виконання функції транслітерації російських слів на літери латинського алфавіту з метою коректного визначення відстані В. Левенштейна для слів. Вхідний вектор - рядок, який потрібно транслітерувати. В результаті функція буде повернута транслітеровано.

Другий крок - отримання всього словника з бази даних і його запис в масив, ключем якого буде російське слово, а значенням - транслітерація російського слова завдяки наведеній вище функції транслітерації. Цей етап забезпечує підвищення швидкодії процесу пошуку у словнику за рахунок зміни процедури пошуку, коли спочатку виконується пошук слова у базі даних, а потім його транслітерування.

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Рисунок 1 - Схема алгоритму виконання тематичного пошуку емулятором

Третій крок - перевірка введеного слова на наявність його у складеному словнику з транслітераціями. Якщо даного слова не було знайдено у словнику, то проводиться транслітерація отриманого слова. Після цього запускається цикл, який буде вибирати з масиву ті слова, відстань В.Левенштейна між Метафонами яких не буде перевищувати половину Метафона введеного слова (іншими словами, допускається до половини неправильнонаписаних приголосних букв). Серед обраних варіантів, знову обчислюється відстань В.Левенштейна, але не по всьому слову, а з його Метафону. В результаті, слова, які знайдено за умовами тематичного пошуку, записуємо в масив.

Четвертий крок - визначення змінних, де відстань В.Левенштейна буде рівноюа завідомо великому числу, а схоже слово - завідомо малому числу. Це потрібно для визначення максимального значення «подібності» між шуканим словом і словами в масиві, а також забезпечення мінімальної відстані В.Левенштейна. Після визначення мінімальної відстані В.Левенштейна, виконується пошук максимального значення «подібності» для тих слів, в яких відстань В.Левенштейна буде мінімальною.

П'ятий крок - запуск циклу, який підбере всі слова з найменшою відстанню В.Левенштейна і найбільшим значенням «подібності» одночасно.

Шостий крок - визначення максимального значення «подібності» між «метафонами» шуканого слова і слів у масиві, а також мінімальної відстані В.Левенштейна.

В результаті опрацювання інформації за запропонованим алгоритмом формується масив, який міститиме одне слово, після чого функція В.Левенштейна поверне «правильне» слово, яке зберігається як ключ у масиві словника.

Таким чином, не зважаючи на потужність слоника, відмінок, рід та час, результат тематичного пошуку буде достатньо точним.

Тематичний пошук, проведений з використанням сучасних засобів, які базуються на класичних алгоритмах, та з використанням запропонованого засобу, який базується на алгоритмі, що враховує відстань В.Левенштейна, має характеристики, подані в таблиці 1.

Таблиця 1 - Порівняльні характеристики підходів щодо тематичного пошуку інформації

Як видно з таблиці 1, врахування відстані В.Левенштейна в алгоритмах тематичного пошуку значно підвищить швидкодію розв'язування задачі, підвищить результативність пошуку у потужних множинах файлів, документах та на Web-сторінках, а, отже, підвищить ефективність тематичного пошуку інформації.

Висновки

Таким чином, застосування функції В.Левенштейна при тематичному пошуку інформаціїі сприятиме підвищенню ефективності такого процесу, а саме, спростить реалізацію такого пошуку, підвищить його швидкодію і точність визначення шуканого слова за визначеною тематикою.

Размещено на Allbest.ru