Python процент схожести строк

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

В В теории информации, лингвистике и информатике расстояние Левенштейна представляет собой строковую метрику для измерения разницы между двумя последовательностями. Неформально расстояние Левенштейна между двумя словами — это минимальное количество односимвольных правок (вставок, удалений или подстановок), необходимых для замены одного слова на другое. [1]

В самых простых словах вы можете рассчитать, сколько преобразований нужно выполнить для строки сделать его равным строкеВ, Алгоритм также известен какИзменить расстояниетак что, возможно, этот термин вам более знаком.

Чтобы использовать его в Python, вам нужно установить его, скажем, череззернышко:

pip install python-Levenshtein

Вот и все. Давайте теперь посмотрим, как его использовать.

Потому что ‘Левенштейн’Так сложно набрать правильно, и я уже говорил ранее, что я использую его в основном для обнаружения опечаток, это будет отличный первый пример. Но, во-первых, импорт:

Теперь вы готовы рассчитать расстояние:

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

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

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

Вот где его косинус-брат приходит на помощь.

Косинус сходство

Как и прежде, давайте начнем с некоторого базового определения:

Косинусное сходство — это мера сходства между двумя ненулевыми векторами внутреннего пространства произведений, которое измеряет косинус угла между ними. [2]

Вам понадобитсястрокамодуль для удаления знаков препинания со строки — ‘приговор‘ а также ‘приговор.По умолчанию разные, и вы хотите избежать этого CountVectorizerпозаботится о преобразовании строк в числовые векторы, что тоже аккуратно. Наконец, поскольку эта статья написана на английском языке, вы хотите удалить наиболее часто встречающиеся слова, которые не имеют смысла — они называютсяигнорируемые слова— такие слова, как ‘я’,‘меня’,‘себя‘, так далее.

Если вы не удалите стоп-слова, вы получите пространство с более высокой размерностью, и угол между векторами будет больше, что подразумевает меньшее сходство, даже если векторы передают практически одинаковую информацию.

Теперь я объявлю список произвольных, в некоторой степени похожих предложений. Это список, потому что векторное пространство будет создано из всех уникальных слов, и это гарантирует, что каждый вектор будет иметь одинаковое количество измерений — так как вы не можете вычислить угол между векторами в разных пространствах измерений:

Помните импорт?Мы импортировали довольно много, и пришло время использовать это. Я объявлю функцию, которая будет делать следующее:

1. Удалить знаки препинания из заданной строки
2. Строчная строка
3. Удалить стоп-слова

Теперь вам не нужен цикл для применения этих преобразований к каждому предложению, вы можете использовать встроенныйкартафункция:

Отлично, подготовка почти завершена. Теперь вы будете использовать силуCountVectorizerсовершить магию (на самом деле, нет). Это создастКвекторы вNпространство, гдеКэто количество предложений, иNколичество уникальных слов во всех предложениях вместе взятых. Тогда, если предложение содержит определенное слово, значение будет 1 и 0 в противном случае:

И это все для подготовки. Было много (Что-то вроде), но это стоило того. Если вы теперь вычислите косинусное сходство из полученных числовых векторов, вы получите следующую матрицу:

Диагональные элементы 1, что имеет смысл, предложениеИкссовершенно «похож» на предложениеИкс, Однако разрезать эту матрицу неудобно, поэтому я решил определить функцию, которая будет вычислять сходство для двух заданных векторов. Имейте в виду, чтоcosine_similarity ()ожидаем двухмерные массивы, а входные векторы по умолчанию являются одномерными, поэтому нам нужно изменить форму:

И просто для подтверждения все работает:

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

Прежде чем ты уйдешь

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

В качестве упражнения было бы неплохо найти набор данных некоторых немеченых электронных писем или другого текста и попытаться использовать метрики сходства, чтобы как-то сгруппировать их. Это также может быть хорошей идеей для вас, чтобы посмотреть наTF-IDFкак я не объяснил в этой статье.

В любом случае, спасибо за чтение, надеюсь, вам удалось извлечь из этого что-то полезное.

Источник

Python. Сравнить строки на похожесть

Помните ваш стартап с самыми актуальными новостями дня? Кажется, у него появился конкурент — он нагло крадёт ваши аутентичные новости, рерайтит их, и рассылает ничего не подозревающим клиентам, подрывая вашу репутацию.

Судите сами, вот ваши новости:

genuine = [ "«Братец-хлеб» из Китая носит плащ и корону из булочек, чтобы кормить чаек", "Мясо гигантских тараканов станет вкусной и недорогой альтернативой говядине", "Скандал в ботаническом саду: 10 миллионов рублей ушло на зарплату кактусам", ] 

А вот новости жалкого подражателя:

plagiary = [ "Китайский хлебный братец кормит чаек плащом и короной из булочек", "Гигантское мясо тараканов станет говядине недорогой и вкусной альтернативой", "Зарплата кактусов в ботаническом саду составила 10 скандальных миллионов рублей", ] 

Нужны какие-то основания для судебного иска, и нужны быстро. Хорошо, что в стандартной библиотеке Питона есть модуль difflib. Сделаем на нём функцию сравнения:

import difflib def similarity(s1, s2): normalized1 = s1.lower() normalized2 = s2.lower() matcher = difflib.SequenceMatcher(None, normalized1, normalized2) return matcher.ratio() 

similarity(genuine[0], plagiary[0]) 0.51 similarity(genuine[1], plagiary[1]) 0.69 similarity(genuine[2], plagiary[2]) 0.55 

АГА! 51%, 69% и 55% похожести! Всё ясно, какие ещё нужны доказательства.

Подписывайтесь на канал, чтобы не пропустить новые заметки 🚀

Источник

Как найти процент совпадения 2х строки?

Здравствуйте, подскажите как вычислить процент совпадения двух строк? Берем их из файла или массива не важно.
например есть строка «Мама мыла раму» в нашем массиве array1 и такая же строка есть в массиве array2.
Совпадение 100%.
в массиве array1 есть строка «Мама мыла раму» и в массиве array2 есть строка «Мама мыла малину»
Совпадение 70%

Как вычислить процент совпадения строк на всех страницах?
Здравствуйте,Господа Можете ли Вы, помочь мне в решении одной задачи ? Задача по математике -.

Процент совпадения значения в ячейках
Всем привет. Нужна помощь. Необходимо сравнить две ячейки на совпадения. Результат вывести в.

Сравнить текстовые файлы и определить процент совпадения
Даны два текстовых файла. Сравнить их и определить процент совпадения. Результат представить в виде.

Найти совпадения дата/логин в 2 таблицах и вывести рядом факт совпадения
Коллеги, задачка следующая: Дана таблица (A-B-C) с указанием логина сотрудника и периода его.

Найти все совпадения строки и вывести их в текстовое поле
Добрый день! Застряла в написании обработки кнопки. По нажатию открывается диалоговое окно, куда.

def fun(s1, s2): if len(s1) > len(s2): s1, s2 = s2, s1 p = 0 for i in range(len(s1)): if s1[i] == s2[i]: p += 1 return str(int(p/len(s1)*100))+'%' print(fun(input(), input()))

Редакционные расстояния между строками\словами вычисляются специализированными функциями статистической направленности с применением тех или иных метрик. Для строк традиционно используется метрика Левенштейна (хотя есть еще и уточненная метрика Левенштейна-Дамерау, метрика Хэмминга (работает только для слов\строк одинаковой длины), менее точная чем прочие метрика Джаро-Винклера и т.д.)
Вот пример использования соответствующих функций из сторонних модулей:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

from fuzzywuzzy import fuzz import Levenshtein import statistics as st # токенизируем слова по пробелу - самый элементарный способ, хотя в модулях для natural language processing (например, nltk) есть спец. токенизаторы sentences = "Мама мыла раму".split(), 'Мама мыла малину'.split() l =[] l2=[] l3=[] for w1,w2 in zip(sentences[0],sentences[1]): l.append(Levenshtein.ratio(w1,w2)) l2.append(fuzz.ratio(w1,w2)) l3.append(Levenshtein.jaro_winkler(w1,w2)) print('Levenshtein:',st.mean(l)) # 0.8 print('fuzzywuzzy %:',st.mean(l2)) # 80 print('jaro_winkler:',st.mean(l3)) # 0.8796296296296297

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

from difflib import SequenceMatcher s = SequenceMatcher(lambda x: x==" ", "Мама мыла раму", "Мама мыла малину") print('difflib:',s.ratio()) #0.8

Источник

Степень схожести строк (коэффициент Танимото)

Иногда нужно определить степень схожести двух строк, т.е., насколько одна строка похожа на другую. Например, у вас есть список названий фильмов. Источники разные, нет никаких уникальных идентификаторов, только заголовки. При этом стоит учесть, что даже самые простые названия могут быть написаны по-разному: «ЗАЛОЖНИЦА 2» и Заложница 2. Очевидно, что сравнение этих строк в лоб ничего не даст: лишние символы, разный регистр.

Строки можно рассматривать как множество символов. Две строки — два множества. Коэффициент Танимото позволяет определить степень схожести двух множеств:

• k — сам коэффициент от 0 до 1;
• a — количество элементов в первом множестве;
• b — количество элементов во втором множестве;
• c — количество общих элементов в двух множествах.

Изящная функция на Питоне:

def tanimoto(s1, s2): a, b, c = len(s1), len(s2), 0.0 for sym in s1: if sym in s2: c += 1 return c / (a + b - c) 

print tanimoto('Иван Гришаев', 'Гришаев И.В.') 0.846153846154 print tanimoto('tanimoto test 1', 'testing Tanimoto #2') 0.7 

В Питоне работает т.н. утиная типизация, когда важен не тип объекта, а его поля и методы. Нетрудно заметить, что код функции требует от объектов методов длины, вхождения элемента и итерации. Это значит, что вместо строк можно передавать списки, кортежи, словари и другие структуры:

print tanimoto( (1, 2, 3, 4, 5, 4), (4, 2, 5, 4, 9, 3), ) 0.714285714286 

Конечно, расчет коэффициента нужно производить с умом. Например, вычистить регулярными выражениями лишние символы или передавать строки в одинаковом регистре. И конечно, лучше оперировать строками в юникоде.

Возвращаясь к нашему примеру:

print tanimoto( u'«ЗАЛОЖНИЦА 2»'.lower(), u'Заложница 2'.lower(), ) 0.846153846154 

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

Нашли ошибку? Выделите мышкой и нажмите Ctrl/⌘+Enter

А на такие строки будет коэффициент 1:
abc и cba
Но они совсем разные. Бесполезный способ.

Строки слишком короткие. И лучше сравнивать не по Танимото, а триграммами.

Проведенный метод сравнивает не строки, множества символов. Можно привести пример длинной строки, что это изменит в алгоритме?

Я уже написал: Танимото не подходит для строк, потому что в строках важен порядок. Этому посту 4 года, сделайте скидку. Сравнивайте триграммами.

Здравствуйте!
Код имеет ошибки:
1. если сравнивать ‘1111’ и ’11’, то результат больше единицы.
2. Сравните слова «фотосессии» и «фотосессию» — результат будет 1.

Исправленный вариант на js:

function tanimoto(s1, s2) s1 = Array.from(s1);
s2 = Array.from(s2);

var a = s1.length;
var b = s2.length;
var c = 0;

for (var sym of s1) var index = s2.indexOf(sym);
if ( index > -1) s2.splice(index, 1);
c += 1;
>
>
return c / (a + b — c)
>

смысл в том, что мы убираем символы, которые уже встречались из второго массива.

u’«ЗАЛОЖНИЦА 2»’.lower(),
u’Заложница 2′.lower(),

Вы же привели к единому регистру. Совпадение должно быть 100%.

Если нет, то в алгоритме ошибка.

Как вариант — не учитывать повтор букв. А во второй позиции не то же самое, что А в последней позиции.

Writing on programming, education, books and negotiations.

Источник