Поиск, если две строки почти одинаковы

Я хочу узнать, похожи ли вы на строки. Например, строка типа «Mohan Mehta» должна соответствовать «Mohan Mehte» и наоборот. Другой пример: строка, подобная «Umesh Gupta», должна соответствовать «Umash Gupte».

В принципе, одна строка правильная, а другая – неправильная запись. Все мои строки – это имена людей.

  • Поддерживает ли флажок регулярные выражения в маршрутизации URL-адресов?
  • Как тайм-аут функции в python, тайм-аут меньше секунды
  • Удалить дубликаты символов с помощью регулярных выражений?
  • Поиск перестановки символов подстроки в Python
  • Как разбить целые числа и символы операторов из строки в python?
  • Замените строку, расположенную между
  • Любые предложения о том, как достичь этого.

    Решение не должно быть на 100 процентов эффективным.

  • Как определить, находится ли подстрока в другой строке
  • Как закодировать целое число в строку base64 в python 3
  • Как сравнить две строки в python?
  • Подавить / печатать без префикса b для байтов в Python 3
  • Python Удалить последние 3 символа строки
  • Функция замены Python
  • 5 Solutions collect form web for “Поиск, если две строки почти одинаковы”

    Вы можете использовать difflib.sequencematcher, если хотите что-то из stdlib:

    from difflib import SequenceMatcher s_1 = 'Mohan Mehta' s_2 = 'Mohan Mehte' print(SequenceMatcher(a=s_1,b=s_2).ratio()) 0.909090909091 

    fuzzywuzzy – одна из многочисленных библиотек, которые вы можете установить, она использует модуль difflib с python-Levenshtein . Вы также должны проверить wikipage на Approximate_string_matching

    Другой подход заключается в использовании « фонетического алгоритма »:

    Фонетический алгоритм – это алгоритм для индексации слов по их произношению.

    Например, используя алгоритм soundex :

     >>> import soundex >>> s = soundex.getInstance() >>> s.soundex("Umesh Gupta") 'U5213' >>> s.soundex("Umash Gupte") 'U5213' >>> s.soundex("Umesh Gupta") == s.soundex("Umash Gupte") True 

    То, что вам нужно, – это расстояние до строки . Там много вкусов, но я бы рекомендовал начать с расстояния Левенштейна .

    вы можете захотеть взглянуть на NLTK (набор инструментов Natural Language Toolkit), в частности пакет nltk.metrics , который реализует различные алгоритмы строковых расстояний, включая уже упоминавшееся расстояние Левенштейна.

     // calculate the similarity between 2 strings public static double similarity(String s1, String s2) { String longer = s1, shorter = s2; if (s1.length() < s2.length()) { // longer should always have greater length longer = s2; shorter = s1; } int longerLength = longer.length(); if (longerLength == 0) { return 1.0; /* both strings are zero length */ } /* // If you have StringUtils, you can use it to calculate the edit distance: return (longerLength - StringUtils.getLevenshteinDistance(longer, shorter)) / (double) longerLength; */ return (longerLength - editDistance(longer, shorter)) / (double) longerLength; } // Example implementation of the Levenshtein Edit Distance // See http://rosettacode.org/wiki/Levenshtein_distance#Java public static int editDistance(String s1, String s2) { s1 = s1.toLowerCase(); s2 = s2.toLowerCase(); int[] costs = new int[s2.length() + 1]; for (int i = 0; i <= s1.length(); i++) { int lastValue = i; for (int j = 0; j <= s2.length(); j++) { if (i == 0) costs[j] = j; else { if (j > 0) { int newValue = costs[j - 1]; if (s1.charAt(i - 1) != s2.charAt(j - 1)) newValue = Math.min(Math.min(newValue, lastValue), costs[j]) + 1; costs[j - 1] = lastValue; lastValue = newValue; } } } if (i > 0) costs[s2.length()] = lastValue; } return costs[s2.length()]; } 
    Python - лучший язык программирования в мире.