Всем привет. Хочу рассказать про следующую задачу, которую решал на работе: есть список организаций с свойствами(name, address, phone, latitude, longitude и остальные, которые в данной задаче не имеют смысла). К ним должны были добавится еще несколько тысяч организаций с такими же свойствами. Вся загвоздка в том, что среди новых организаций есть организации, которые есть и у нас в базе данных. Моя задача состояла в том, чтобы выявить сходства организаций и сделать так, чтобы одинаковые организации были сохранены в базе данных в единственном экземпляре. Кому интересна тема matching-а, то прошу под кат!
Изучив данные с нашей базы данных и данные новых организаций, можно было сделать вывод:
- Названия не совпадают у одинаковых организаций. Например, в одной базе указано название на русском языке, в другой базе — на английском. В одном месте указано более полное название с указанием улицы.
- Шаблон адресов не совпадают. В одном взято с Google, в другом непонятно откуда. Такое чувство, что разрешалось писать что угодно.
- Телефонные номера вовсе не указаны. В одной базе данных телефонные номера отсутствовали у большинства организаций. Позже выяснилось, что на странице создания организации, поле для ввода телефонного номера оказалось необязательным.
- Широта и долгота были единственными полями, которым можно было доверять.
Изучив существующие материалы в интернете, я наткнулся на тему неточного поиска, а точнее на расстояние Левенштейна. Кто не знает, расстояние Левенштейна находит минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной строки в другую.
То есть, для нашей задачи, это определение звучит так:
какое минимальное количество операций вставки одного символа, удаления одного символа и замены одного символа на другой, необходимых для превращения одной организации в другую. Под организацией имеется в виду, строка имеющая вид — {название организации} {адрес} {телефон}.
Расстояние Левенштейна и его обобщения активно применяется:
- для исправления ошибок в слове (в поисковых системах, базах данных, при вводе текста, при автоматическом распознавании отсканированного текста или речи).
- для сравнения текстовых файлов утилитой diff и ей подобными. Здесь роль «символов» играют строки, а роль «строк» — файлы.
- в биоинформатике для сравнения генов, хромосом и белков.
Цены операций могут зависеть от вида операции (вставка, удаление, замена) и/или от участвующих в ней символов, отражая разную вероятность разных ошибок при вводе текста. В общем случае:
- w(a, b) — цена замены символа a на символ b
- w(ε, b) — цена вставки символа b
- w(a, ε) — цена удаления символа a
Надо было решить какую цену назначать для замены, для вставки и для удаления. Довольно нетривиальная задача, и я пошел экспериментальным путем. Реализовал алгоритм Левенштейна на языке C#, которая принимает две строки, и три необязательных параметра: цены для замены, вставки, и удаления. По умолчанию они равны 1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | /// <summary> /// Calculates Edit Distance between S1 and S2 and the prescription /// </summary> /// <param name="s">First input string /// <param name="t">Second input string /// <param name="costInsert">Cost for insert /// <param name="costDelete">Cost for delete /// <param name="costReplace">Cost for replaces /// <exception cref="ArgumentNullException"></exception> /// <returns>Prescription - the edit distance and the path retraced</returns> public static Prescription Levenshtein(string s, string t, int costInsert = 1, int costDelete = 1, int costReplace = 1) { if (s == null) { throw new ArgumentNullException(nameof(s)); } if (t == null) { throw new ArgumentNullException(nameof(t)); } int m = s.Length, n = t.Length; var d = new int[m + 1, n + 1]; var p = new char[m + 1, n + 1]; int i, j; // First fill the basic values for (i = 0; i <= m; i++) { d[i, 0] = i * costDelete; p[i, 0] = 'D'; } for (i = 0; i <= n; i++) { d[0, i] = i * costInsert; p[0, i] = 'I'; } for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) { if (s[i - 1] == t[j - 1]) { d[i, j] = d[i - 1, j - 1]; p[i, j] = 'M'; continue; } if (d[i, j - 1] + costInsert < d[i - 1, j] + costDelete && d[i, j - 1] + costInsert < d[i - 1, j - 1] + costReplace) { //Inserting d[i, j] = d[i, j - 1] + costInsert; p[i, j] = 'I'; } else if (d[i - 1, j] + costDelete < d[i - 1, j - 1] + costReplace) { //Deleting d[i, j] = d[i - 1, j] + costDelete; p[i, j] = 'D'; } else { //Replacing d[i, j] = d[i - 1, j - 1] + costReplace; p[i, j] = 'R'; } } //Retracing var route = new StringBuilder(""); i = m; j = n; do { var c = p[i, j]; route.Append(c); switch (c ) { case 'R': case 'M': i--; j--; break; case 'D': i--; break; default: j--; break; } } while (i != 0 && j != 0); var charArray = route.ToString().ToCharArray(); Array.Reverse(charArray); return new Prescription(d[m, n], new string(charArray)); } |
Чтобы пользоваться данным алгоритмом в нашей задаче, нужно определится с ценами для удаления, вставки, и замены. Начал экспериментировать, и пришел к выводу, что такие значения подходят лучше всего:
- Цена удаления — 1.
- Цена вставки — 1.
- Цена замены — 2.
Немного подумав, можно объяснить почему так вышло: цена замены выше, так как пользователь с меньшей вероятностью мог нажать не ту кнопку, чем нажать лишнюю или забыть нажать кнопку (при нажатии, кнопка не сработала).
Так как, нам нужно сопоставлять по 3 параметрам, то этот алгоритм нужно применить 3 раза. Можно конечно объединить в одну строку все три слова, но тогда ошибок будет еще больше. Теперь нужно было определить пороговое значение ошибки X, которое бы считалось незначительной.
Алгоритм принял вид:
- Если организации находятся на расстоянии менее 30 метров, то перейти к шагу 2, иначе это разные компании
- Посчитать для каждого слова расстояние Левенштейна
- Просуммировать все расстояния
- Если эта сумма меньше либо равно порогового значения ошибки X, то считаем, что организации идентичны.
Довольно нетривиально определить пороговое значение той ошибки, которая считается незначительной. Результаты меня не впечатляли. Много оставалось организаций, которых надо было сопоставлять ручками. Были организации, которые были записаны в одной базе на русском языке, а в другой — транслитом. Такие случаи тоже были покрыты, с помощью использования структуры данных — ассоциативный словарь (map, dictionary), который хранит какая буква как переводиться на транслит, то есть, ключом является буква русского алфавита, а значением — написание на транслите данной буквы. Ничего сложного, все довольно просто.
Но кроме таких организаций, были еще те, у которых отсутствовали некоторые поля (например, номера телефона). И тогда расстояние Левенштейна оказывалось большим. За счет суммы расстояний получаются большие помехи. Тогда решил, изменить цены для действий каждого слова: удаление, вставка, замена. То есть, например в телефоне менее вероятно ошибиться, чем в названии, следовательно увеличиваем цену замены у телефона. Но увы, суммирование все портит.
Тогда я решил приступить к другому методу: убираем окончания, предлоги, приводим к одному регистру, и проверяем на вхождение одной строки в другую. Все вроде банально и просто. Ну и чуть своей добавки, которую пока не буду раскрывать.
Вывод: не всегда выгодно использовать классические алгоритмы. Да, их нужно знать и разбираться в них. Но, если они не подходят для вашей конкретной задачи, то не стоит их использовать. Можно и нужно придумать свое решение, которое будет работать лучше классической в конкретных специфических задачах.
А у кого какие идеи для решения данной задачи? Поделитесь в комментариях.