Pull to refresh

Поиск неточных совпадений, поиск с учетом ошибок ввода

Website development *PHP *Client optimization *
Sandbox

Предисловие



Есть у нашей компании своя собственная CRM и периодически в эту систему добавляются данные о неких организациях с точным адресом, и главное что адреса эти по сути уникальны, то есть в системе не должно быть нескольких организаций по одному адресу (специфика, на самом деле могут, но контролируется челфаком*). С недавнего времени в систему был прикручен КЛАДР, но и он не мог быть панацеей, т.к. КЛАДР имеет кучу неточностей, многие нас. пункты остались без номеров домов итд. итп., хотя адреса эти в реальности есть (данные предоставляют сотрудники компании и они достоверны). В общем ввод адреса оставили в свободной форме с подсказкой из КЛАДр. Сразу хочу сказать, что от комбинации полей мы отказались, т.к. многообразие аббревиатур сокращений не сулило ничего хорошего, к тому же вполне позволительным был адрес на подобии («Ололошское ш. 5км», «ТЦ Весельчак У» или даже «Центральный рынок»). И наконец главный враг программиста — челfuck, подразумевающий от неграмотности и опечаток до залипающей клавиатуры и опечаток. Остальное под катом…
Читать дальше →
Total votes 30: ↑23 and ↓7 +16
Views 14K
Comments 49

Полиномиальные хеши и их применение

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

Введение


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

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство.
Читать дальше →
Total votes 74: ↑69 and ↓5 +64
Views 66K
Comments 41

Используйте поиск по хешу, а не обыск массива

High performance *PHP *Algorithms *
Translation
Довольно-таки часто встречается задача: проверить, совпадает ли строка с другими строками из набора. Например, вам нужно проверить каждое слово из сообщения на форуме на предмет того, не содержится ли оно в списке запрещённых. Распространённое решение: создать массив со списком запрещённых слов, а затем с помощью функции in_array() делать проверку. Есть способы повысить производительность такого алгоритма.
Читать дальше →
Total votes 63: ↑33 and ↓30 +3
Views 27K
Comments 19

Нечёткое сравнение строк: пойми меня, если сможешь

Entertaining tasks Programming *.NET *Algorithms *C# *
image
Привет!

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

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

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

Итак, кратко задачу можно озвучить так: «С определенной периодичностью из различных источников приходят актуальные новости. Необходимо фильтровать их таким образом, чтобы на выходе не было двух новостей об одном и том же факте.»
Предупреждение: в статье присутствуют заголовки реальных новостей. Я отношусь к ним исключительно как к рабочему материалу, не представляю какую-либо точку зрения на политическую или экономическую ситуацию в какой бы то ни было стране.
Читать дальше →
Total votes 22: ↑22 and ↓0 +22
Views 48K
Comments 8

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

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

Например, один адрес может выглядеть как «Тверская обл., Кашин г, Советская ул, 1, 5», а другой – как «Тверская область; город Кашин; улица Советская; дом 1; квартира 5». Похожи ли эти строки и насколько? Несомненно, похожи. И «невооруженным глазом» видна их структура: область – населенный пункт – улица – дом – квартира. Логично, что для адресов важно такое разбиение строк на группы; то есть сравнивать мы должны не «две каши» из сходных слов (где одна «каша» состоит из слов первой строки, а вторая – из слов второй), а именно осуществлять «погруппное» сравнение слов из первой строки со словами из второй. Просматривается и критерий разбиения на группы: в первой строке разделителем групп является «, », а во второй – «; ».
Читать дальше →
Total votes 30: ↑18 and ↓12 +6
Views 10K
Comments 15