Рубрика «расстояние Левенштейна»
Распознавание символов методом наименьшего расстояния Левенштейна
2020-02-17 в 10:52, admin, рубрики: java, Программирование, распознавание символов, расстояние ЛевенштейнаВ последнее время задача распознавания символов в прикладных программах не представляет особой сложности — можно использовать множество готовых OCR-библиотек, многие из которых доведены почти до совершенства. Но все же иногда может возникнуть задача разработать свой алгоритм распознавания без использования сторонних «навороченных» OCR-библиотек.
Именно такая задача возникла у меня по ходу работы, а причин, почему лучше не использовать готовые библиотеки, несколько: закрытость проекта, с его дальнейшей сертификацией, определенное ограничение на количество строчек кода и размер подключаемых библиотек, тем более что по предметной области распознавать приходится достаточно определенный набор символов.
Расстояние Левенштейна и поиск контролёров
2019-12-03 в 8:15, admin, рубрики: data mining, natural language processing, python, боты для социальных сетей, Вконтакте API, машинное обучение, общественный транспорт, паблик вконтакте, расстояние Левенштейна, социальные сетиНаверное, в каждом городе Беларуси, где есть троллейбусы, существуют группы ВК или чаты в Telegram, в которых люди отслеживают местоположение контролёров. В основном это делается для того, чтобы не оплатить проезд и проехать бесплатно, хотя в описании групп почти всегда есть постскриптум “Платите за проезд”.
Читать полностью »
Расстояние Левенштейна в MySQL и алгоритмы нечёткого поиска средствами PHP
2017-11-15 в 8:41, admin, рубрики: levenshtein, metaphone, mysql, php, similar_text, алгоритм Оливера, Алгоритмы, метафон, нечеткий поиск, поисковые технологии, расстояние дамерау-левенштейна, расстояние ЛевенштейнаЗнаменитый советский и российский математик Владимир Иосифович Левенштейн (кстати, ушедший из жизни два с небольшим месяца назад) в начале второй половины прошлого века ввёл понятие дистанции редактирования, которым мы пользуемся по сей день в различных сферах — от поисковых систем до биоинформатики. В этой статье мы применим его принцип для нечёткого поиска в MySQL (поскольку MySQL на данный момент пока не предлагает встроенного решения), вычислив самый эффективный (т.е. быстрый) способ из нескольких найденных в интернете, построим алгоритм такого поиска и реализуем его на PHP.
Полнотекстовый нечеткий поиск с использованием алгоритма Вагнера-Фишера
2016-03-18 в 8:28, admin, рубрики: алгоритм Вагнера-Фишера, Алгоритмы, нечеткий поиск, полнотекстовый поиск, Программирование, расстояние Левенштейна, метки: алгоритм Вагнера-Фишера, алгоритм Дамерау-ЛевенштейнаСтатья написана об использовании алгоритма вычисления расстояния Левенштейна для нечеткого поиска в тексте, без использования вспомогательного словаря.
Расстояние Левенштейна используется для сравнения двух слов или двух строк, чтобы определить их схожесть. Некоторое время назад передо мной встала схожая задача — в заданной строке искать вхождение слов, словосочетаний и формул, похожих на образец.
Читать полностью »
Автоматическая проверка орфографии, модель Noisy Channel
2013-11-20 в 15:27, admin, рубрики: data mining, алгоритм, Алгоритмы, вероятность, искусственный интеллект, орфография, расстояние дамерау-левенштейна, расстояние Левенштейна, метки: алгоритм, вероятность, орфография, расстояние дамерау-левенштейна, расстояние Левенштейна 
Доброго времени суток. На днях у меня возникла задача по реализации алгоритма пост-обработки результатов оптического распознавания текста. Для решения этой проблемы не плохо подошла одна из моделей для проверки орфографии в тексте, хотя конечно слегка модифицированная под контекст задачи. Этот пост будет посвящен модели Noisy Channel, которая позволяет осуществлять автоматическую проверку орфографии, мы изучим математическую модель, напишем на c# немного кода, обучим модель на базе Питера Норвига, и под конец протестируем то что у нас получится.
О подходах к сравнению версий файлов
2012-04-24 в 4:45, admin, рубрики: алгоритм, Алгоритмы, контроль версий, оптимизация, Программирование, разработка, расстояние Левенштейна, сравнение, сравнение файлов, хэширование, метки: алгоритм, Алгоритмы, контроль версий, оптимизация, расстояние Левенштейна, сравнение, сравнение файлов, хэширование Люди, использующие системы контроля версий исходного кода (SVN, Mercurial, Git и т.п.), наверняка часто пользуются возможностью сравнения версий файлов для просмотра внесенных пользователями изменений. Существует множество независимых программ сравнения версий (WinMerge, BeyondCompare и др.). При сравнении версий, как правило, две версии файла показываются рядом друг с другом таким образом, чтобы одинаковые (неизменившиеся) части документов были расположены напротив друг друга, а изменившиеся (добавленные и удаленные) выделяются соответствующим цветом.
Уверен, многим было бы интересно узнать, какие алгоритмы могут использоваться для реализации такого сравнения.
Читать полностью »