Как найти похожие строки в python

Подобное делал для поиска цен из стима на игры из моей базы.

Для этого написал функцию, которая сравнивает приводя к одной форме полученные строки:

• В нижний регистр
• Удаление постфикса (необходимость из-за стандарта названий игр в базе)
• Удаление символов кроме буквенных, цифр и _

Например, в функцию передаются строки The Witcher 3: Wild Hunt и The Witcher® 3: Wild Hunt. После обработки эти строку станут thewitcher3wildhunt.

Пример:

def smart_comparing_names(name_1, name_2):
    """
    Функция для сравнивания двух названий игр.
    Возвращает True, если совпадают, иначе -- False.
    """

    # Приведение строк к одному регистру
    name_1 = name_1.lower()
    name_2 = name_2.lower()

    def remove_postfix(text, postfix='(dlc)'):
        if text.endswith(postfix):
            text = text[:-len(postfix)]

        return text
    
    def clear_name(name):
        import re
        return re.sub(r'W', '', name)

    name_1 = remove_postfix(name_1)
    name_2 = remove_postfix(name_2)

    return clear_name(name_1) == clear_name(name_2)


# Пример функции поиска цены для игры
def get_price(game):
    game_price = None

    # Пример спарсенного списка игр из стима по предварительному запросу
    steam_games = [
        ('The Witcher® 3: Wild Hunt', 1199),
        ('Call of Cthulhu®: Dark Corners of the Earth', 199),
        ('South Park™: The Stick of Truth™', 1499),
        ('Dishonored®: Death of the Outsider™', 859),
        ('Dishonored - The Knife of Dunwall', 199),
        ('Dishonored: The Brigmore Witches', 199),
    ]

    # Сначала пытаемся найти игру по полному совпадению
    for name, price in steam_games:
        if game == name:
            game_price = price
            break

    # Если по полному совпадению на нашли, пытаемся найти предварительно очищая названия игр
    # от лишних символов
    if game_price is None:
        for name, price in steam_games:
            # Если нашли игру, запоминаем цену и прерываем сравнение с другими найденными играми
            if smart_comparing_names(game, name):
                game_price = price
                break

    return game_price


my_games = [
    'The Witcher 3: Wild Hunt',
    'Call of Cthulhu: Dark Corners of the Earth',
    'South Park: The Stick of Truth',
    'Dishonored: Death of the Outsider',
    'Dishonored: The Knife of Dunwall (DLC)',
    'Dishonored: The Brigmore Witches (DLC)',
]

for game in my_games:
    print('{:44} -> {}'.format(game, get_price(game)))

Результат:

The Witcher 3: Wild Hunt                     -> 1199
Call of Cthulhu: Dark Corners of the Earth   -> 199
South Park: The Stick of Truth               -> 1499
Dishonored: Death of the Outsider            -> 859
Dishonored: The Knife of Dunwall (DLC)       -> 199
Dishonored: The Brigmore Witches (DLC)       -> 199

---

PS. конечно не всегда это работало, но в этом случае руками искалась цена для игры.

Недавно мы обсуждали расчет расстояния Левеншейна, настало время испытать его применение на практике. Библиотека FuzzyWuzzy содержит набор функций для нечеткого поиска строк, дедупликации (удаления копий), корректировки ошибок. Она позволяет стать поиску умнее, помогая преодолеть влияние человеческого фактор.

Начнем с установки:

pip install fuzzywuzzy python-Levenshtein

Модуль python-Levenshtein можно устанавливать по желанию: работать будет и без него, но с ним гораздо быстрее (в разы). Поэтому советую его установить, он мелкий, порядка 50 Кб.

Похожесть двух строк

Задача: есть две строки, требуется вычислить степень их похожести числом от 0 до 100. В FuzzyWuzzy для этого есть несколько функций, отличающихся подходом к сравнению и вниманием к деталям. Не забудем импортировать:

from fuzzywuzzy import fuzz

Функция fuzz.ratio – простое посимвольное сравнение. Рейтинг 100 только если строки полностью равны, любое различие уменьшает рейтинг, будь то знаки препинания, регистр букв, порядок слов и так далее:

>>> fuzz.ratio("я люблю спать", "я люблю спать")
100
>>> fuzz.ratio("я люблю спать", "Я люблю cпать!")
81
>>> fuzz.ratio("я люблю спать", "я люблю есть")
88

Обратите внимание, что рейтинг второго примера ниже, чем у третьего, хотя по смыслу должно быть наоборот.

Следующая функция fuzz.token_sort_ratio решает эту проблему. Теперь акцент именно на сами слова, игнорируя регистр букв, порядок слов и даже знаки препинания по краям строки.

>>> fuzz.token_sort_ratio("я люблю спать", "я люблю есть")
56
>>> fuzz.token_sort_ratio("я люблю спать", "Я люблю спать!")
100
>>> fuzz.token_sort_ratio("я люблю спать", "спать люблю я...")
100

>>> fuzz.token_sort_ratio("Мал да удал", "удал да МАЛ")
100
>>> fuzz.token_sort_ratio("Мал да удал", "Да Мал Удал")
100

Однако, смысл пословицы немного изменился, а рейтинг остался на уровне полного совпадения.

Функция fuzz.token_set_ratio пошла еще дальше: она игнорирует повторяющиеся слова, учитывает только уникальные.

>>> fuzz.token_set_ratio("я люблю спать", "люблю я спать, спать, спать...")
100
>>> fuzz.token_set_ratio("я люблю спать", "люблю я спать, спать и спать...")
100
>>> fuzz.token_set_ratio("я люблю спать", "но надо работать")
28

# повторы в token_sort_ratio роняют рейтинг! 
>>> fuzz.token_sort_ratio("я люблю спать", "люблю я спать, спать и спать.")
65

# но вот это странно:
>>> fuzz.token_set_ratio("я люблю спать", "люблю я спать, но надо работать")
100
>>> fuzz.token_set_ratio("я люблю спать", "люблю я спать, люблю я есть")
100

Последние два примера вернули 100, хотя добавлены новые слова, и это странно. Тут следует вспомнить о fuzz.partial_ratio, которая ведет себя также. А именно, проверяет вхождение одной строки в другую. Лишние слова игнорируются, главное – оценить, чтобы ядро было одно и тоже.

>>> fuzz.partial_ratio("одно я знаю точно", "одно я знаю")
100
>>> fuzz.partial_ratio("одно я знаю точно", "одно я знаю!")
92
>>> fuzz.partial_ratio("одно я знаю точно", "я знаю")
100

Еще еще более навороченный метод fuzz.WRatio, который работает ближе к человеческой логике, комбинируя несколько методов в один алгоритм в определенными весами (отсюда и название WRatio = Weighted Ratio).

>>> fuzz.WRatio("я люблю спать", "люблю Я СПАТЬ!")
95
>>> fuzz.WRatio("я люблю спать", "люблю Я СПАТЬ и есть")
86
>>> fuzz.WRatio("я люблю спать", "!!СПАТЬ ЛЮБЛЮ Я!!")
95

Нечеткий поиск

Задача: найти в списке строк одну или несколько наиболее похожих на поисковый запрос.

Импортируем подмодуль и применим process.extract или process.extractOne:

from fuzzywuzzy import process

strings = ['привет', 'здравствуйте', 'приветствую', 'хай', 'здорова', 'ку-ку']
process.extract("Прив", strings, limit=3)
# [('привет', 90), ('приветствую', 90), ('здравствуйте', 45)]

process.extractOne("Прив", strings)
# ('привет', 90)

Удаление дубликатов

Очень полезная функция для обработки данных. Представьте, что вам досталась 1С база номенклатуры запчастей, там полный бардак, и вам нужно поудалять лишние повторяющиеся позиции товара, но где-то пробелы лишние, где-то буква перепутана и тому подобное. Тут пригодится process.dedupe.

dedupe(contains_dupes, threshold=70, scorer=token_set_ratio)

Первый аргумент – исходный список, второй – порог исключения (70 по умолчанию), третий – алгоритм сравнения (token_set_ratio по умолчанию).

Пример:

arr = ['Гайка на 4', 'гайка 4 ГОСТ-1828 оцинкованная', 'Болты на 10', 'гайка 4 ГОСТ-1828 оцинкованная ...', 'БОЛТ']

print(list(process.dedupe(arr)))
# ['гайка 4 ГОСТ-1828 оцинкованная ...', 'Болты на 10', 'БОЛТ']

FuzzyWuzzy можно применять совместно с Pandas. Например так (без особых подробностей):

def get_ratio(row):
    name = row['Last/Business Name']
    return fuzz.token_sort_ratio(name, "Alaska Sea Pilot PAC Fund")

df[df.apply(get_ratio, axis=1) > 70]

Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway 👈 

7 919

Перейти к содержимому

В этом руководстве мы узнаем, как сопоставить строки, используя встроенную  библиотеку fuzzyWuzzy в Python, и определим, насколько они похожи, на различных примерах.

Python предоставляет несколько методов для сравнения двух строк. Ниже приведены основные методы:

• использование Regex;
• простое сравнение;
• использование dfflib.

Но есть еще один метод для нечеткого сравнения строк, который можно эффективно использовать, он называется fuzzywuzzy. Этот метод довольно эффективен для различения двух строк, относящихся к одному и тому же объекту, но написанных немного по-разному. Иногда нам нужна программа, которая может автоматически определять неправильное написание.

Это процесс поиска строк, соответствующих заданному шаблону. Он использует расстояние Левенштейна для вычисления разницы между последовательностями.

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

Посмотрим на следующий пример.

 
Str1 = "Welcome to Javatpoint" 
Str2 = "Welcome to Javatpoint" 
Result = Str1 == Str2 
print(Result) 

Выход:

True 

Приведенный выше код возвращает истину, потому что строки совпадают точно(100%), что, если мы внесем изменения в str2.

 
Str1 = "Welcome to Javatpoint" 
Str2 = "welcome to Javatpoint" 
Result = Str1 == Str2 
print(Result) 

Выход:

False 

Здесь приведенный выше код возвращает ложь, строки почти идентичны для человеческого глаза, но не для интерпретатора. Однако мы можем решить эту проблему, преобразовав обе строки в нижний регистр.

 
Str1 = "Welcome to Javatpoint" 
Str2 = "welcome to Javatpoint" 
Result = Str1.lower() == Str2.lower() 
print(Result) 

Выход:

True 

Но если мы внесем изменения в кодировку, у нас возникнет другая проблема.

 
Str1 = "Welcome to javatpoint." 
Str2 = "Welcome to javatpoint" 
Result = Str1.lower() == Str2.lower() 
print(Result)  

Выход:

True 

Чтобы решить такие проблемы, нам нужны более эффективные инструменты для сравнения строк. И fuzzywuzzy – лучший инструмент для вычисления строк.

Расстояние Левенштейна

Расстояние Левенштейна используется для вычисления расстояния между двумя последовательностями слов. Оно вычисляет минимальное количество правок, которые нам нужно изменить в данной строке. Эти изменения могут быть вставкой, удалением или заменой.

Пример –

 
import numpy as np 
 
def levenshtein_distance(s1, t1, ratio_calculation = False): 
 
    # Initialize matrix of zeros 
    rows = len(s1)+1 
    cols = len(t1)+1 
    calc_distance = np.zeros((rows,cols),dtype = int) 
 
    # Populate matrix of zeros with the indeces of each character of both strings 
    for i in range(1, rows): 
        for k in range(1,cols): 
            calc_distance[i][0] = i 
            calc_distance[0][k] = k 
 
    for col in range(1, cols): 
        for row in range(1, rows): 
            if s1[row-1] == t1[col-1]: 
                cost = 0 
                if ratio_calculation == True: 
                    cost = 2 
                else: 
                    cost = 1 
            calc_distance[row][col] = min(calc_distance[row-1][col] + 1,      # Cost of deletions 
                                 calc_distance[row][col-1] + 1,          # Cost of insertions 
                                 calc_distance[row-1][col-1] + cost)     # Cost of substitutions 
    if ratio_calculation == True: 
        # Computation of the Levenshtein calc_distance Ratio 
        Ratio =((len(s)+len(t)) - calc_distance[row][col]) /(len(s)+len(t)) 
        return Ratio 
    else: 
        return "The strings are {} edits away".format(calc_distance[row][col]) 

Мы будем использовать указанную выше функцию в предыдущем примере, где мы пытались сравнить «Добро пожаловать в javatpoint» и «Добро пожаловать в javatpoint». Мы видим, что обе строки, скорее всего, совпадают, потому что длина Левенштейна мала.

 
Str1 = "Welcome to Javatpoint" 
Str2 = "welcome to Javatpoint" 
Distance = levenshtein_distance(Str1,Str2) 
print(Distance) 
Ratio = levenshtein_distance(Str1,Str2,ratio_calc = True) 
print(Ratio) 

Название этой библиотеки какое-то странное и забавное, но она очень полезна. Она имеет уникальный способ сравнения обеих строк и возвращает результат из 100 возможных для соответствия количеству строк. Для работы с этой библиотекой нам необходимо установить ее в нашей среде Python.

Установка

Мы можем установить эту библиотеку с помощью команды pip.

 
pip install fuzzywuzzy 

Collecting fuzzywuzzy 
  Downloading fuzzywuzzy-0.18.0-py2.py3-none-any.whl(18 kB) 
Installing collected packages: fuzzywuzzy 
Successfully installed fuzzywuzzy-0.18.0 

Теперь введите следующую команду и нажмите ввод.

 
pip install python-Levenshtein 

Давайте разберемся в следующих методах библиотеки fuzzuwuzzy.

Модуль Fuzz

Модуль fuzz используется для одновременного сравнения двух заданных строк. Он возвращает оценку из 100 после сравнения с использованием различных методов.

Fuzz.ratio()

Это один из важных методов модуля fuzz. Он сравнивает строку и оценку на основе того, насколько данная строка соответствует. Давайте разберемся в следующем примере.

Пример –

 
from fuzzywuzzy import fuzz 
Str1 = "Welcome to Javatpoint" 
Str2 = "welcome to javatpoint" 
Ratio = fuzz.ratio(Str1.lower(),Str2.lower()) 
print(Ratio) 

Выход:

100 

Как видно из приведенного выше кода, метод fuzz.ratio() вернул оценку, что означает очень небольшую разницу между строками.

Fuzz.partial_ratio()

Библиотека fuzzywuzzy предоставляет еще один мощный метод – partial_ratio(). Он используется для обработки сложного сравнения строк, такого как сопоставление подстрок. Посмотрим на следующий пример.

 
#importing the module from the fuzzywuzzy library 
from fuzzywuzzy import fuzz 
 
str1 = "Welcome to Javatpoint" 
str2 = "tpoint" 
Ratio = fuzz.ratio(str1.lower(),str2.lower()) 
Ratio_partial = fuzz.partial_ratio(str1.lower(),str2.lower()) 
print(Ratio) 
print(Ratio_partial) 

Выход:

44 
100 

Объяснение:

Метод partial_ratio() может обнаружить подстроку. Таким образом, дает 100% сходство. Он следует оптимальной частичной логике, в которой для короткой строки k и более длинной строки m алгоритм находит наилучшую совпадающую длину k-подстроки.

Fuzz.token_sort_ratio

Этот метод не гарантирует получения точного результата, потому что если мы внесем изменения в порядок строк, это может не дать точного результата.

Но модуль fuzzywuzzy предоставляет решение. Давайте разберем следующий пример.

 
str1 = "united states v. nixon" 
str2 = "Nixon v. United States" 
Ratio = fuzz.ratio(str1.lower(),str2.lower()) 
Ratio_Partial = fuzz.partial_ratio(str1.lower(),str2.lower()) 
Ratio_Token = fuzz.token_sort_ratio(str1,str2) 
print(Ratio) 
print(Ratio_Partial) 
print(Ratio_Token) 

Выход:

59 
74 
100 

Объяснение:

В приведенном выше коде мы использовали метод token_sort_ratio(), который дает преимущество перед partial_ratio. В этом методе строковые токены сортируются в алфавитном порядке и объединяются. Но есть и другая ситуация, например, когда строки сильно различаются по длине.

Пример –

 
str1 = "The supreme court case of Democratic vs Congress" 
str2 = "Congress v. Democratic" 
Ratio = fuzz.ratio(str1.lower(),str2.lower()) 
Partial_Ratio = fuzz.partial_ratio(str1.lower(),str2.lower()) 
Token_Sort_Ratio = fuzz.token_sort_ratio(str1,str2) 
Token_Set_Ratio = fuzz.token_set_ratio(str1,str2) 
print(Ratio) 
print(Partial_Ratio) 
print(Token_Sort_Ratio) 
print(Token_Set_Ratio) 

Выход:

40 
64 
61 
95 

В приведенном выше коде мы использовали другой метод, называемый fuzz.token_set_ratio(), который выполняет операцию набора и извлекает общий токен, а затем выполняет попарное сравнение ratio().

Пересечение отсортированного токена всегда одно и то же, потому что подстрока или меньшая строка состоит из больших фрагментов исходной строки, или оставшийся токен находится близко к другому.

Пакет fuzzywuzzy предоставляет модуль процесса, который позволяет нам вычислять строку с наибольшим сходством. Давайте разберемся в следующем примере.

 
from fuzzywuzzy import process 
strToMatch = "Hello Good Morning" 
givenOpt = ["hello","Hello Good","Morning","Good Evenining"] 
ratios = process.extract(strToMatch,givenOpt) 
print(ratios) 
# We can choose the string that has highest matching percentage 
high = process.extractOne(strToMatch,givenOpt) 
print(high) 

Выход:

[('hello', 90),('Hello Good', 90),('Morning', 90),('Good Evenining', 59)] ('hello', 90) 

Приведенный выше код вернет наивысший процент совпадений для данного списка строк.

Fuzz.WRatio

Модуль процесса также предоставляет WRatio, который дает лучший результат, чем простое соотношение. Он обрабатывает нижний и верхний регистры, а также некоторые другие параметры. Давайте разберемся в следующем примере.

Пример –

 
from fuzzywuzzy import process 
fuzz.WRatio('good morning', 'Good Morning') 
fuzz.WRatio('good morning!!!','good Morning') 

Выход:

100 

Заключение

В этом уроке мы обсудили, как сопоставить строки и определить, насколько они схожи. Мы проиллюстрировали простые примеры, но их достаточно, чтобы понять, как компьютер обрабатывает несовпадающие строки. Многие реальные приложения, такие как проверка орфографии, биоинформатика для сопоставления, последовательность ДНК и т. д., основаны на нечеткой логике.