Рубрика «сравнение строк»

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

Например, один адрес может выглядеть как «Тверская обл., Кашин г, Советская ул, 1, 5», а другой – как «Тверская область; город Кашин; улица Советская; дом 1; квартира 5». Похожи ли эти строки и насколько? Несомненно, похожи. И «невооруженным глазом» видна их структура: область – населенный пункт – улица – дом – квартира. Логично, что для адресов важно такое разбиение строк на группы; то есть сравнивать мы должны не «две каши» из сходных слов (где одна «каша» состоит из слов первой строки, а вторая – из слов второй), а именно осуществлять «погруппное» сравнение слов из первой строки со словами из второй. Просматривается и критерий разбиения на группы: в первой строке разделителем групп является «, », а во второй – «; ».
Читать полностью »

image
Привет!
На естественном языке сказать об одном и том же факте можно бесконечным числом способов. Можно переставлять слова местами, заменять их на синонимы, склонять по падежам (если говорим о языке с падежами) и тд.

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

Результатом работы, описанием процесса, кодом на git'е готов поделиться с вами.

Итак, кратко задачу можно озвучить так: «С определенной периодичностью из различных источников приходят актуальные новости. Необходимо фильтровать их таким образом, чтобы на выходе не было двух новостей об одном и том же факте.»

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

Читать полностью »

Здравствуй. Сегодня я напишу, как можно использовать полиномиальные хеши (далее просто хеши) при решении различных алгоритмических задач.

Введение

Начнем с определения. Пусть у нас есть строка s0..n-1. Полиномиальным хешем этой строки называется число h = hash(s0..n-1) = s0 + ps1 + p2s2 +… + pn-1sn-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а si — код i-ого символа строки s (почти во всех современных языках он записывается s[i]).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Читать полностью »

Предисловие

Есть у нашей компании своя собственная CRM и периодически в эту систему добавляются данные о неких организациях с точным адресом, и главное что адреса эти по сути уникальны, то есть в системе не должно быть нескольких организаций по одному адресу (специфика, на самом деле могут, но контролируется челфаком*). С недавнего времени в систему был прикручен КЛАДР, но и он не мог быть панацеей, т.к. КЛАДР имеет кучу неточностей, многие нас. пункты остались без номеров домов итд. итп., хотя адреса эти в реальности есть (данные предоставляют сотрудники компании и они достоверны). В общем ввод адреса оставили в свободной форме с подсказкой из КЛАДр. Сразу хочу сказать, что от комбинации полей мы отказались, т.к. многообразие аббревиатур сокращений не сулило ничего хорошего, к тому же вполне позволительным был адрес на подобии («Ололошское ш. 5км», «ТЦ Весельчак У» или даже «Центральный рынок»). И наконец главный враг программиста — челfuck, подразумевающий от неграмотности и опечаток до залипающей клавиатуры и опечаток. Остальное под катом…
Читать полностью »

Предисловие

Есть у нашей компании своя собственная CRM и периодически в эту систему добавляются данные о неких организациях с точным адресом, и главное что адреса эти по сути уникальны, то есть в системе не должно быть нескольких организаций по одному адресу (специфика, на самом деле могут, но контролируется челфаком*). С недавнего времени в систему был прикручен КЛАДР, но и он не мог быть панацеей, т.к. КЛАДР имеет кучу неточностей, многие нас. пункты остались без номеров домов итд. итп., хотя адреса эти в реальности есть (данные предоставляют сотрудники компании и они достоверны). В общем ввод адреса оставили в свободной форме с подсказкой из КЛАДр. Сразу хочу сказать, что от комбинации полей мы отказались, т.к. многообразие аббревиатур сокращений не сулило ничего хорошего, к тому же вполне позволительным был адрес на подобии («Ололошское ш. 5км», «ТЦ Весельчак У» или даже «Центральный рынок»). И наконец главный враг программиста — челfuck, подразумевающий от неграмотности и опечаток до залипающей клавиатуры и опечаток. Остальное под катом…
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js