Когда использовать какую функцию fuzz для сравнения 2 строк

Я изучаю fuzzywuzzy в Python, понимаю концепции fuzz.ratio, fuzz.partial_ratio, fuzz.token_sort_ratio и fuzz.token_set_ratio. У меня вопрос, когда использовать какую функцию? Должен ли я сначала проверить длину 2 строк, скажем, если они не похожи, то исключить fuzz.partial_ratio? ИЛИ если длина двух строк одинакова, я буду использовать fuzz.token_sort_ratio? ИЛИ Я всегда должен использовать fuzz.token_set_ratio?

Кто-нибудь знает, какие критерии использует SeatGeek?

Я пытаюсь создать сайт по недвижимости, думая использовать fuzzywuzzy для сравнения адресов.

Любое понимание очень ценится.

Р.

Источник

2 ответа

Решение

Отличный вопрос

Я инженер в SeatGeek, поэтому я думаю, что могу помочь здесь. У нас есть отличный пост в блоге, который довольно хорошо объясняет различия, но я могу подвести итог и дать некоторое представление о том, как мы используем различные типы.

обзор

Под капотом каждый из четырех методов вычисляет расстояние редактирования между некоторыми порядками токенов в обеих входных строках. Это делается с помощью difflib.ratio функция, которая будет:

Вернуть меру сходства последовательностей (с плавающей точкой в ​​[0,1]).

Где T - общее количество элементов в обеих последовательностях, а M - количество совпадений, это 2,0*M / T. Обратите внимание, что это 1, если последовательности идентичны, и 0, если они не имеют ничего общего.

Вызов четырех нечетких методов difflib.ratio на разных комбинациях входных строк.

fuzz.ratio

Просто. Просто звонки difflib.ratio на двух входных строках ( код).

fuzz.ratio("NEW YORK METS", "NEW YORK MEATS")
> 96

fuzz.partial_ratio

Попытки объяснить частичные совпадения строк лучше. Вызовы ratio использование самой короткой строки (длины n) для всех подстрок длины n большей строки и возвращает наивысший результат ( код).

Обратите внимание, что "YANKEES" является самой короткой строкой (длина 7), и мы используем соотношение "YANKEES" для всех подстрок длины 7 "NEW YORK YANKEES" (что включает проверку на "YANKEES", 100% совпадение):

fuzz.ratio("YANKEES", "NEW YORK YANKEES")
> 60
fuzz.partial_ratio("YANKEES", "NEW YORK YANKEES")
> 100

fuzz.token_sort_ratio

Попытки учесть похожие строки не по порядку. Вызовы ratio на обе строки после сортировки токенов в каждой строке ( код). Обратите внимание здесь fuzz.ratio а также fuzz.partial_ratio оба не удаются, но как только вы сортируете токены, это соответствует 100%:

fuzz.ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets")
> 45
fuzz.partial_ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets")
> 45
fuzz.token_sort_ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets")
> 100

fuzz.token_set_ratio

Попытки исключить различия в строках. Соотношение вызовов для трех конкретных наборов подстрок и возвращает максимум ( код):

  1. только пересечение и пересечение с остатком строки один
  2. только пересечение и пересечение с остатком строки два
  3. пересечение с остатком от одного и пересечение с остатком от двух

Обратите внимание, что, разделив пересечение и остатки двух строк, мы учитываем, насколько похожи и различны эти две строки:

fuzz.ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 36
fuzz.partial_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 61
fuzz.token_sort_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 51
fuzz.token_set_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 91

заявка

Вот где происходит волшебство. По сути, в SeatGeek мы создаем векторную оценку с каждым отношением для каждой точки данных (место проведения, название события и т. Д.) И используем ее для информирования программных решений о сходстве, характерных для нашей проблемной области.

При этом, по правде говоря, не похоже, что FuzzyWuzzy полезен для вашего случая использования. Будет очень плохо определять, похожи ли два адреса. Рассмотрим два возможных адреса для SeatGeek HQ: "235 Park Ave Floor 12" и "235 Park Ave S. Floor 12":

fuzz.ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 93
fuzz.partial_ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 85
fuzz.token_sort_ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 95
fuzz.token_set_ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 100

FuzzyWuzzy дает этим строкам высокую оценку соответствия, но один адрес - это наш фактический офис возле Юнион-сквер, а другой - по другую сторону Grand Central.

Для решения вашей проблемы лучше использовать Google Geocoding API.

Источник

По состоянию на июнь 2017 года fuzzywuzzy также включает в себя некоторые другие функции сравнения. Вот обзор тех, которые отсутствуют в принятом ответе (взяты из исходного кода):

fuzz.partial_token_sort_ratio

Тот же алгоритм, что и в token_sort_ratio, но вместо применения ratio после сортировки токенов, использует partial_ratio,

fuzz.token_sort_ratio("New York Mets vs Braves", "Atlanta Braves vs New York Mets")
> 85
fuzz.partial_token_sort_ratio("New York Mets vs Braves", "Atlanta Braves vs New York Mets")
> 100    
fuzz.token_sort_ratio("React.js framework", "React.js")
> 62
fuzz.partial_token_sort_ratio("React.js framework", "React.js")
> 100

fuzz.partial_token_set_ratio

Тот же алгоритм, что и в token_set_ratio, но вместо применения ratio к наборам токенов, использует partial_ratio,

fuzz.token_set_ratio("New York Mets vs Braves", "Atlanta vs New York Mets")
> 82
fuzz.partial_token_set_ratio("New York Mets vs Braves", "Atlanta vs New York Mets")
> 100    
fuzz.token_set_ratio("React.js framework", "Reactjs")
> 40
fuzz.partial_token_set_ratio("React.js framework", "Reactjs")
> 71

fuzz.QRatio, fuzz.UQRatio

Просто обертки вокруг fuzz.ratio с некоторой проверкой и коротким замыканием, включенным сюда для полноты.UQRatio является версией Unicode QRatio,

fuzz.WRatio

Попытка взвешивания (название обозначает "Взвешенное соотношение") является результатом различных алгоритмов для вычисления "наилучшего" результата. Описание из исходного кода:

1. Take the ratio of the two processed strings (fuzz.ratio)
2. Run checks to compare the length of the strings
    * If one of the strings is more than 1.5 times as long as the other
      use partial_ratio comparisons - scale partial results by 0.9
      (this makes sure only full results can return 100)
    * If one of the strings is over 8 times as long as the other
      instead scale by 0.6
3. Run the other ratio functions
    * if using partial ratio functions call partial_ratio,
      partial_token_sort_ratio and partial_token_set_ratio
      scale all of these by the ratio based on length
    * otherwise call token_sort_ratio and token_set_ratio
    * all token based comparisons are scaled by 0.95
      (on top of any partial scalars)
4. Take the highest value from these results
   round it and return it as an integer.

fuzz.UWRatio

Юникод версия WRatio,

Источник
Другие вопросы по тегам