fuzz · y ( adjectiv e) - трудно воспринимать ясно или понимать и точно объяснять; нечеткое или расплывчатое.
Начиная как разработчик, можно подумать, что термин «нечеткий» применим ко всему, что они делают. На самом деле, вы можете вообще не вспомнить этот термин (я не подумал. За исключением тех случаев, когда я просматривал гифки с кошками в блогах других людей).
Однако мы используем слово «нечеткое» для описания жизни регулярно, потому что жизнь может быть чрезвычайно расплывчатой и общей. Как объектно-ориентированный программист, мы стремимся минимизировать разрыв между нашим кодом и реальным миром с помощью точных моделей этого мира. Так почему бы не применить нечеткое? Конечно, уже есть.
Нечеткая логика?
Концепция нечеткой логики была разработана в 20 веке, развивая предложение Яна Лукасевича о многозначной логике в 1920 году. Ян особенно был пионером отрицания и импликации; вы можете знать значение как оператор if. Многозначная логика необходима, потому что она позволяет проводить математические вычисления в отношении неоднозначной природы жизни.
«Нечеткая логика… обеспечивает эффективную концептуальную основу для решения проблемы представления знаний в среде неопределенности и неточности».
Важность нечеткой логики становится все более очевидной по мере того, как наука копается в компьютерах, а программирование идет дальше. Это стало особенно полезно в контексте искусственного интеллекта. Вы можете подумать: «Но подождите! Логические значения присутствуют в программировании повсюду. Разве это не противоречит логике многих ценностей? »И да, и нет.
Мы регулярно используем многозначную логику (также известную как бесконечная), когда уже кодируем. Каждый раз, когда вы используете оператор if, добавляя несколько предложений elsif, вы используете форму бесконечной логики. Вы учитываете несколько возможных сценариев, кроме true или false, вплоть до потенциально бесконечного количества раз. Однако есть много других ситуаций, в которых нечеткая логика может сразу помочь.
Редактировать расстояние и соответствие нечеткой строки
«Нечеткое сопоставление строк - это, по сути, перефразирование ДА / НЕТ« Строка A и строка B одинаковы? » на« Насколько похожи строка A и строка B? »
Нечеткая логика пришла мне на помощь, когда я работал над базовым интерфейсом командной строки в школе Flatiron. Если кто-то наберет команду или что-то неправильно, это может сломать вашу программу. Первый шаг - реализовать правильную обработку ошибок, например. сообщение, чтобы пользователь узнал об ошибке и разрешил еще одну попытку. Однако это непростительно, когда ты запачканный типаж. Вы можете сделать так, чтобы ваша программа соответствовала первым трем символам, но здесь все же есть место для ошибок. Человеческая ошибка всегда непоследовательна. Как мы учитываем неправильные или лишние буквы, которые могут появиться в любом месте строки? Введите изменить расстояние.
По сути, расстояние редактирования вычисляет, насколько похожи (или нет) две строки. Это вычисляется через количество операций, необходимых для преобразования одной строки в другую - например, с моим именем «Жюльен» и обычным написанием «Джулиан» требуется только одна операция, замена «а» на «е».
Авторский алгоритм принадлежит Владимиру Левенштейну, скончавшемуся в сентябре прошлого года. Это расстояние известно как расстояние Левенштейна. Это рекурсивная функция, которая вычисляет расстояние редактирования для каждого префикса и суффикса. Алгоритм дает матрицу всех возможностей.
Расстояние редактирования нашло широкое применение при картировании и сравнении геномов. Это также стало чрезвычайно полезным в названии этой статьи - сопоставлении нечетких строк.
Нечеткое сопоставление строк, также известное как приблизительное сопоставление строк, может быть различным; Регулярные выражения являются его формой, как и символы подстановки в контексте SQL. Это любая форма попытки сопоставить одну строку с другой.
Нечеткое сопоставление строк в отношении расстояния редактирования - это применение расстояния редактирования в качестве метрики и нахождение минимального расстояния редактирования, необходимого для сопоставления двух разных строк вместе. Мы сталкиваемся с этим ежедневно при взаимодействии с компьютерами - красная линия под словом с ошибкой звонит в колокол? Или, может быть, вот этот:
Все они реализуют некоторую форму сопоставления нечетких строк. Расстояние Левенштейна - наиболее распространенная метрика, но есть и другие варианты алгоритма - Селлерса, Дамерау-Левенштейна, Хэмминга и другие. У всех есть разные способы вычисления одного и того же.
Хорошо, как мне использовать это в своих интересах?
Большая часть тяжелой работы уже была сделана за нас, поскольку эти алгоритмы уже были выражены в коде на всех мыслимых языках Интернета. Я разместил версию Ruby выше, но для всех остальных: Найдите здесь расстояние Левенштейна, выраженное на других языках.
На самом деле, причиной того, что я оказался в этой червоточине редактирования, стала Рубиновая жемчужина Amatch Флориана Франка. Проверьте это! Он предлагает вам выбор алгоритмов на выбор в зависимости от вводимых вами данных. Некоторые больше подходят для больших объемов текста, а другие нет.
Мир нечеткого сопоставления строк прошел долгий путь. Есть гораздо более продвинутые способы включения этих концепций в поиск нечетких строк, и есть больше возможностей для повышения эффективности (через MIT утверждает, что алгоритм настолько же эффективен, насколько и будет). Копайся!
Источники
- Ягер, Рональд Р. и Лотфи А. Заде. Введение в приложения нечеткой логики в интеллектуальных системах. Клювер, 1998 г.
- Https://en.wikipedia.org/wiki/Many-valued_logic
- Http://www.levenshtein.net/
- Https://www.r-bloggers.com/fuzzy-string-matching-a-survival-skill-to-tackle-unstructured-information/
- Https://en.wikipedia.org/wiki/Approximate_string_matching
- Https://en.wikipedia.org/wiki/%C5%81ukasiewicz_logic
- Https://www.youtube.com/watch?v=ocZMDMZwhCY
- Http://rosettacode.org/wiki/Levenshtein_distance#Ruby
- Http://www.occasionalenthusiast.com/wp-content/uploads/2016/04/levenshtein-formula.png
