Студопедия
МОТОСАФАРИ и МОТОТУРЫ АФРИКА !!!


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram

Вычисление дистанции Левенштейна. На рис. 11, 12 представлена функция levenshtein, реализующая алгоритм динамического программирования вычисления дистанции Левенштейна




На рис. 11, 12 представлена функция levenshtein, реализующая алгоритм динамического программирования вычисления дистанции Левенштейна.

Рис. 11. Прототип функции levenshtein

Рис. 12. Реализация функции levenshtein

Функция levenshteinимеет тот же набор параметров, что и функция levenshtein_r,описанная в пред. лекции. Более того, реализации этих двух функций практически одинаковы. Основное отличие – применение в функции levenshteinмассива d(для работы с ним используется макрос DD) для хранения результатов промежуточных вычислений.

Интерес представляет сравнительный анализ скорости вычисления дистанции Левенштейна функциями levenshtein_r(рекурсивный алгоритм) и levenshtein(алгоритм динамического программирования) сделанный для строк различной длины с помощью программы, представленной на рис. 13. В программе поочередно вызываются функции levenshtein_rиlevenshteinс одинаковыми значениями параметров и замеряется продолжительность выполнения этих функций.

Рис. 13. Программа для сравнительного анализа продолжительности выполнения функций levenshtein_rиlevenshtein

На рис. 14 представлен результат выполнения программы, приведенной на рис. 13. Продолжительность выполнения функций в распечатке приведена в миллисекундах.

Рис. 14. Результат выполнения программы, представленной на рис. 13

Рис. 14 демонстрирует подавляющее превосходство алгоритма, основанного на динамическом программировании. При последнем просчете, в котором вычислялась дистанция Левенштейна между строками длиной 12 и 14 символов, рекурсивный алгоритм затратил на вычислении более 2 мин, а алгоритм, основанный на динамическом программировании, – менее 0,001 с.





Дата добавления: 2014-02-18; просмотров: 777; Опубликованный материал нарушает авторские права? | Защита персональных данных | ЗАКАЗАТЬ РАБОТУ


Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент - человек, постоянно откладывающий неизбежность... 11021 - | 7451 - или читать все...

Читайте также:

 

34.204.191.0 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.


Генерация страницы за: 0.002 сек.