Тема, озвученная в заголовке статьи, не нова. На просторах Интернета можно найти множество вопросов, как ее реализовать, а вот ответов несколько меньше. И не редко они сводятся к советам использовать продукты сторонних разработчиков, например, Sphinx. Но зачастую в использовании таких громоздких надстроек нет необходимости.
Автоматическим просмотром БД выявить и сформировать пары похожих по какому-то критерию имен, которые передать для дальнейшего ручного анализа на предмет того, принадлежат ли они одной персоне или разным. Причем, поиск должен был обладать некой параноидностью. Т.е. в отличие от "Возможно, Вы имели в виду …" должен был выдавать несколько больше имен по принципу "Лучше перебдеть, чем недобдеть". А, значит, и анализировать на предмет схожести должен был несколько большее число пар. Причем, делать это не в реальном времени, но за реально конечное время. Т.е., не за сутки и недели, а, в худшем случае, за несколько часов.
В общем, если кратко, есть почти полторы сотни тысяч имен, прозвищ, псевдонимов без разделения на отдельные поля (фамилия, имя, отчество и т.д.) с произвольным порядком слов, опечатками, ошибками, с разными вариантами написания. Причем имена имеют самые разные национальные принадлежности — русские, английские, еврейские, польские, французские, корейские, китайские, японские, индийские, индейские и т.д. Требуется найти среди них всевозможные пары таких, которые сильно напоминают одно и то же имя.
Вначале задача показалась крайне сложной. Мне, незнакомому с нечетким поиском человеку, трудно было даже вообразить формальные критерии, позволяющие судить о схожести или различии имен.
Но постепенно начало формироваться понимание в используемых для этих целях подходах и алгоритмах. Прежде всего это были алгоритмы, специально ориентированные или просто хорошо зарекомендовавшие себя при поиске ошибок в написании имен:
Фонетическое кодирование не подходит в силу специфики наполнения БД. Фонетический поиск способен найти имена, записанные с ошибками на слух, но не переведенные дилетантами-любителями. Поясню на примере:
Вот приходит в наш родной паспортный стол капитан третьего ранга Jeannette Devereaux[6] и представляется по уставу четко и громко. И паспортистка может на слух записать ее фамилию и «Диверю» и «Девирю» и даже «Дивиру». Да еще удвоенные согласные в имени пропустить. Все эти «слуховые галлюцинации» прекрасно отслеживаются алгоритмами нечеткого поиска с фонетическим кодированием.
Но вот горе-«переводчик», не знающий специфики французского языка (но знакомый с английским языком), переписывая данные из военного билета, запросто может написать «Жэннетт Деверокс». А особо одаренные могут указать позывной или записать фамилию впереди имени.
Или даже многие англоязычные «переводчики» не знают, что имя «Ralph Fiennes» следует читать не «Ральф», а «Рэйф Файнс».
Так что, фонетическое кодирование здесь не подходит, потому что в данном случае ошибочные имена пишутся не «так, как слышаЦЦа», а «так, как видRTCR».
Попытка же применить фонетические алгоритмы к именам, воспринимаемым не на слух, а на глаз, может привести к тому, что фонетические индексы имен будут отличаться друг от друга даже больше, чем варианты их написания.
Неплохая была бы идея, если бы не тот факт, что эти метрики в большей степени рассчитаны именно на сравнение слов, а не словосочетаний с произвольным порядком слов. Стоит поменять имя и фамилию местами или вставить между ними псевдоним, и они показывают крайне неудовлетворительный результат.
Приходится в таком случае разбивать имена на отдельные слова и сравнивать уже каждое из них. А это существенно усложняет (и замедляет) работу алгоритма, даже если предварительно привести эти отдельные слова к их фонетическому индексу. Так же дополнительную сложность привносит то, что количество слов в имени является непостоянной величиной. С учетом возможных пропусков и перестановок слов уже сложно даже представить трудоемкость этого процесса.
К недостаткам метрики выделения общих форм можно отнести большую временную сложность вычисления релевантности при неясных возможностях индексирования, особенно коротких имен. Даже единичное выделение максимальной общей подстроки имеет временную сложность O(nm). А так как надо затем продолжить рекурсивный поиск общих подстрок в остатках, то вычисление функции релевантности представляется весьма накладной операцией, проигрывающей даже N-граммному сравнению.
Опять таки, при перемене словами мест, релевантность резко уменьшается.
Вычисление дистанции Джаро-Винклера работает существенно быстрее. Но, к сожалению, так же не является устойчивым к перемене слов местами.
Так что, чтобы не пришлось разделять и комбинировать слова в имени, волей-неволей пришлось остановиться на N-граммном анализе. Вернее, даже на триграммном, т.к. короткие корейские имена не располагают к выделению слишком длинных N-грамм.
Итак, для начала, чтобы составить представление о временной сложности триграммного сравнения, я написал самый простой вариант скрипта, попарно сравнивающего имена по всей БД.
Написание и тестирование скрипта проводилось в домашних условиях на компьютере восьмилетней давности еще с одноядерным Intel Pentium D 925 на материнской плате ASUS P5B-E и с обычными заезженными хардами Seagate примерно того же возраста.
Скрипт этот работал, что называется, в лоб. Считывал БД, каждое имя, предварительно нормализованное, разбивал на уникальные триграммы и подсчитывал число их вхождений в каждое из предыдущих имен (т.е., находящихся в БД ранее испытуемого). Если результат деления удвоенного числа совпадений на сумму уникальных триграмм в каждом из этих имен превышал некоторый порог (например, 0,75 или 0,8), то это фиксировалось в файле.
Нормализация имени заключалась в следующем:
В результате такой нормализации получалось упрощенное имя без знаков препинания, без транслитерных символов, в котором каждое слово обрамлено или отделено от других слов двойными пробелами.
Использование двойных пробелов между словами, а так же в начале и конце имени, делало алгоритм триграммного анализа совершенно нечувствительным к перемене мест слов.
В нормализованном имени выделялись всевозможные уникальные триграммы — сочетания из расположенных подряд трех символов (включая пробелы).
Затем для двух имен вычислялся следующий коэффициент релевантности: удвоенное число общих триграмм делилось на сумму уникальных триграмм в каждом имени.
Требование к уникальности триграмм озвучено неспроста. С одной стороны, подсчет общего количества триграмм в именах без учета их уникальности позволит уверенно различать такие имена, как «Джон Смит» и «Джон Джон Смит». А учет только уникальных триграмм приведет к тому, что эти имена будут считаться идентичными.
С другой стороны, во-первых, потребность в различении подобных имен будет возникать не часто. А, во-вторых, подсчет релевантности по всем триграммам, а не только по уникальным, значительно усложнит эту процедуру. Потому что вместо удвоенного числа общих триграмм придется считать сумму вхождений триграмм из первого имени во второе и триграмм из второго имени в первое. Т.е., грубо это увеличит временные расходы на вычисление релевантности примерно в 2 раза. Ну и, в-третьих, это не позволит применить к процедуре вычисления релевантности некоторые оптимизации, о которых пойдет речь далее.
Итак, лобовой алгоритм был написан и опробован на первых нескольких тысячах имен. Результат был удручающим. Как и следовало ожидать, время поиска совпадений по всему массиву имен имело ярко выраженную квадратичную зависимость от его размера. Прогноз тренда на обработку всего массива из 130-140 тысяч имен составил около двух лет. Многовато будет!
Зато появилась начальная оценка производительности алгоритма.
Прежде всего, пришлось оценить, какие элементы алгоритма нуждаются в оптимизации, а какой является пресловутым «бутылочным горлышком», тормозящим всю систему. Областей оптимизации было выявлено несколько:
Прежде всего, как самое простое, была выполнена попытка перехода от кодировки нормализованных имен UTF-8 к кодировке Windows-1251. Однако, оказалось, что MySQL весьма ревностно относится к хранению в БД строк в разной кодировке даже в разных таблицах. Что приводит к возникновению нелокализуемых ошибок при операциях с БД. Поэтому нормализованное имя хранится в дополнительной присоединенной таблице все равно в формате UTF-8, а при необходимости перекодируется в Windows-1251.
Хранение нормализованного имени существенно экономит время, т.к. нормализацию необходимо проводить для каждой записи только один раз.
Кроме того, в той же присоединенной таблице хранится число уникальных триграмм в нормализованном имени. Эта величина может быть использована для принудительного завершения вычисления релевантности в том случае, если становится очевидным слишком большое различие между именами. При этом вычислять каждый раз число уникальных триграмм в имени уже нет необходимости.
Ну и, самое главное, обработанные имена индексировались триграммным индексом. Т.е. в дополнительной таблице перечислялись все уникальные триграммы, присутствующие в нормализованном имени. При этом, сами триграммы, чтобы не хранить их в «медленной» кодировке UTF-8, хранились в виде целочисленного хеша — трем младшим байтам числа соответствовали числовые значения соответствующих символов в кодировке Windows-1251.
Но при этом был допущен совершенно неэффективный, как было выяснено в дальнейшем, подход — для каждой триграммы из проверяемого имени делалась своя собственная выборка имен-претендентов, которые потом объединялись в единый массив. При этом каждое имя в этом массиве сопровождалось счетчиком — в скольких выборках оно встретилось. Предполагалось, что это даст некоторый выигрыш в вычислении релевантности за счет того, что не надо будет затем раскладывать эти имена на триграммы — достаточно было использовать этот счетчик, чтобы сразу вычислить релевантность.
К сожалению, многократное проведение выборок из базы MySQL (в большей степени) и формирование объединенного массива имен (в меньшей степени) давали такие накладные расходы, которые многократно превышали выигрыш, получаемый в результате упрощения вычисления релевантности.
В результате описанных оптимизаций удалось достичь существенного сокращения временных затрат:
Применение триграммного индекса для начальной выборки сократило прогноз результирующего времени с двух лет до менее чем трех месяцев. Использование в его качестве числовых значений вместо подстрок в формате UTF-8 позволило дополнительно сократить время общей обработки еще на 10-12%. Но все равно 2,5 месяца непрерывной работы представлялись слишком большим сроком. Тонким местом оставалась начальная выборка похожих имен.
Многократное обращение к БД по каждому триграммному индексу оказалось не лучшей идеей. Мало того, что многочисленные выборки выполнялись достаточно долго, так еще и консолидированный массив получался очень большим, и его обработка требовала значительных временных затрат несмотря на использование счетчика общих триграмм для каждого элемента.
Пришлось отказаться от идеи этого счетчика, но получать весь начальный набор имен-претендентов за один запрос при помощи SQL-конструкции WHERE IN. Это позволило сократить прогноз еще в несколько раз до одного месяца.
Далее была изменена процедура вычисления релевантности. На основании нижней границы релевантности и числа уникальных триграмм в именах вычислялось максимально допустимое число «промахов» — число триграмм в имени-претенденте, не входящих в проверяемое имя. Затем все триграммы имени-претендента проверялись на вхождение в проверяемое имя. Как только число «промахов» превышало максимально допустимое, сравнение прекращалось. Это позволило сократить прогноз времени еще на несколько процентов. Но до промышленных значений было все равно очень далеко.
Задача казалось неразрешимой. С одной стороны требовалось значительно сократить число имен в начальной выборке, с другой же это сокращение не должно было быть слишком искусственным, чтобы не отсечь случайно имена, которые находятся близко к нижней границе допустимого диапазона релевантности.
Найти подход помог простой просмотр найденных пар сходных имен. Практически во всех таких парах находились общие подпоследовательности длиной 6-7 символов (включая окаймляющие двойные пробелы). Путем нехитрых рассуждений (которые здесь не приводятся ввиду их нестрогости) можно прийти к выводу, что для достижения релевантности более 0,75, нормализованные имена должны иметь общую подстроку из 5 символов или длиннее.
Таким образом, от индексации предварительного поиска триграммами переходим к индексации пентаграммами (5-символьными подстроками). Чтобы уместить хеш пентаграммы в целочисленной переменной, имеющей в 32-разрядной версии PHP размер 32 бита, каждый символ представляем в виде 5-бит, благо символов всего 31 (без «Ё» и «Ъ») и пробел.
Как писал выше, при вычислении релевантности уникальные триграммы одного из имен сравнивались на предмет совпадения с триграммами второго имени. При этом расчет прекращался при превышении числа «промахов» максимально допустимого количества.
Если число уникальных триграмм в первом имени значительно меньше числа уникальных триграмм во втором, то рассчитанное максимально допустимое число промахов может оказаться отрицательным. Это означает, что данные имена ну никак не могут быть сходными с заданной величиной релевантности. И проверять их нет необходимости.
Но эта отсечка не работает в противоположном случае, если число уникальных триграмм в первом имени значительно больше числа таковых во втором имени. Поэтому дополнительно в запрос выборки были введены граничные значения количества уникальных триграмм в нормализованном имени.
Это несколько спорное усовершенствование. При задании граничного значения релевантности 0,75 оно не приводит к ускорению, а, наоборот, приводит к потере производительности на 3% за счет увеличения сложности выборки. Но если задать границу релевантности 0,8, то получаем уже 3% выигрыша.
Тем не менее, данный прием был оставлен. Потери не такие уж большие, а вначале можно сделать предварительный поиск похожих пар с высокой степенью релевантности. И только после предварительной чистки задать граничное значение равным 0,75.
В результате перехода от начальной выборки по общим триграммам к выборке по пентаграммам удалось существенно ускорить работу скрипта. Поиск похожих с релевантностью 0,8 пар среди 138,5 тысячи имен составил около 5 часов вместо одного месяца. Т.е. единичный поиск похожих имен во всей БД для заданного имени составляет (если принять квадратичную зависимость времени обработки) около 0,26 с. Несколько много, но надо учитывать, что это был тестовый прогон не на сервере с мощным процессором и высокопроизводительной дисковой системой, а на полумертвом домашнем компьютере восьмилетней давности.
В принципе, можно было бы осуществлять первоначальный поиск даже гексаграммами (индексными подстроками из 6 символов). Это давало ускорение еще в несколько раз. Но возникло обоснованное опасение, что могут отсеяться много пар азиатских коротких имен (и не только их). Да и смысла особого нет, т.к. последующий ручной анализ полученных пар (а их набралось более 11 тысяч) займет в любом случае несколько месяцев.
Зато индексация гексаграммами вполне пригодна для подсказок вида «Возможно, Вы имели в виду …», когда излишняя параноидность не требуется, а наоборот, следует находить минимальное количество наиболее подходящих имен.
В принципе, при работе с длинными именами можно использовать индексы семисимвольных подстрок. А чтобы поместить их в 32-битные переменные произвести предварительное фонетическое кодирование с целью сокращения числа символов до 15 и пробела. Но такая задача в тот момент не стояла.
К сожалению, вскоре после написания скрипта, сайт был заблокирован по обвинению в нарушении авторских прав. Хотя вскоре он переехал на другой адрес, из-за навалившихся проблем стало не до поиска дублирующих имен.
1. Фонетическое кодирование.
> Фонетические алгоритмы. Хабрахабр
> «Как ваша фамилия», или Русский MetaPhone (Russian Metaphone description)
2. Расстояние Левенштейна. Википедия
3. Вычисление схожести слов на основе выделения общих форм реализована в PHP в функции similar_text. В документации PHP указывается, что в основе этой функции лежит алгоритм Оливера [1993]. Однако первоначально данный алгоритм под названием «Ratcliff/Obershelp Pattern Recognition Algorithm» был опубликован John W. Ratcliff на сайте программистов Dr. Dobb's (Pattern Matching: the Gestalt Approach) в 1988 году. А Ian Oliver всего лишь использовал его в своей книге «Programming Classics: Implementing the World's Best Algorithms».
4. Исходники алгоритма Джаро-Винклера можно посмотреть, например, здесь: Jaro-Winkler Distance
5. Триграммный индекс или «Поиск с опечатками». Хабрархабр
6. Жаннетта «Ангел» Деверю — персонаж культовой медиафраншизы "Wing Commander", включающей компьютерные космосимуляторы, стратегии, прочие формы игр, литературные произведения и фильм. Здесь приведена исключительно в связи с тем, что я, не разбираясь в звучании французских фамилий, долгое время считал, что она звучит «Деверо». Иллюстрация ошибочного перевода не «на слух», а «на глаз».
7. Основа функции форматированных SQL-запросов честно позаимствована у Камнева Артема и Месилова Максима из статьи «SQL-инъекции: борьба в удовольствие». К сожалению, сайт этих ребят в последнее время не загружается, но копию статьи еще можно найти: Sql-инъекции: борьба в удовольствие (к сожалению, без исходников). Убраны некоторые спорные возможности. Вместо них добавлена возможность передачи в качестве аргумента массива.
Не так давно возникла следующая задача:
- Есть в составе информационной системы (ИС) база данных (БД) актеров, музыкантов, DJ-ев, а так же иногда политиков, ученых и других публичных лиц.
- ИС заполнялась любителями и дилетантами, многие из которых затруднялись правильно перевести на русский язык ту или иную фамилию. А иногда случалось и такое, что имя звучало по-русски совсем не так, как писалось на иностранном языке.
- В БД имена заносились в достаточно свободной форме. Порядок слов в имени часто менялся (особенно для азиатских имен), дополнительно могли указываться (или не указываться) прозвища и псевдонимы.
- Бывали и просто описки — замены, пропуски или добавления букв. Иногда часть букв по какой-то причине писалась латиницей.
- Акцидентных символов, к счастью, не было.
- Имена хранились в MyISAM таблицах MySQL в кодировке UTF-8.
- Общее число имен в БД составляло примерно 138,5 тысяч.
Это то, что «дано». А «требовалось» следующее:
Автоматическим просмотром БД выявить и сформировать пары похожих по какому-то критерию имен, которые передать для дальнейшего ручного анализа на предмет того, принадлежат ли они одной персоне или разным. Причем, поиск должен был обладать некой параноидностью. Т.е. в отличие от "Возможно, Вы имели в виду …" должен был выдавать несколько больше имен по принципу "Лучше перебдеть, чем недобдеть". А, значит, и анализировать на предмет схожести должен был несколько большее число пар. Причем, делать это не в реальном времени, но за реально конечное время. Т.е., не за сутки и недели, а, в худшем случае, за несколько часов.
В общем, если кратко, есть почти полторы сотни тысяч имен, прозвищ, псевдонимов без разделения на отдельные поля (фамилия, имя, отчество и т.д.) с произвольным порядком слов, опечатками, ошибками, с разными вариантами написания. Причем имена имеют самые разные национальные принадлежности — русские, английские, еврейские, польские, французские, корейские, китайские, японские, индийские, индейские и т.д. Требуется найти среди них всевозможные пары таких, которые сильно напоминают одно и то же имя.
Вначале задача показалась крайне сложной. Мне, незнакомому с нечетким поиском человеку, трудно было даже вообразить формальные критерии, позволяющие судить о схожести или различии имен.
Но постепенно начало формироваться понимание в используемых для этих целях подходах и алгоритмах. Прежде всего это были алгоритмы, специально ориентированные или просто хорошо зарекомендовавшие себя при поиске ошибок в написании имен:
- Фонетическое кодирование (в частности, «Русский Метафон» Петра Каньковского и его модификации[1]).
- Мера схожести, основанная на дистанциях редактирования Левенштейна[2].
- Выделение общих форм[3].
- Алгоритм Джаро-Винклера[4].
- N-граммный анализ.[5].
По здравому размышлению принято было следующее:
Фонетическое кодирование не подходит в силу специфики наполнения БД. Фонетический поиск способен найти имена, записанные с ошибками на слух, но не переведенные дилетантами-любителями. Поясню на примере:
Вот приходит в наш родной паспортный стол капитан третьего ранга Jeannette Devereaux[6] и представляется по уставу четко и громко. И паспортистка может на слух записать ее фамилию и «Диверю» и «Девирю» и даже «Дивиру». Да еще удвоенные согласные в имени пропустить. Все эти «слуховые галлюцинации» прекрасно отслеживаются алгоритмами нечеткого поиска с фонетическим кодированием.
Но вот горе-«переводчик», не знающий специфики французского языка (но знакомый с английским языком), переписывая данные из военного билета, запросто может написать «Жэннетт Деверокс». А особо одаренные могут указать позывной или записать фамилию впереди имени.
Или даже многие англоязычные «переводчики» не знают, что имя «Ralph Fiennes» следует читать не «Ральф», а «Рэйф Файнс».
Так что, фонетическое кодирование здесь не подходит, потому что в данном случае ошибочные имена пишутся не «так, как слышаЦЦа», а «так, как видRTCR».
Попытка же применить фонетические алгоритмы к именам, воспринимаемым не на слух, а на глаз, может привести к тому, что фонетические индексы имен будут отличаться друг от друга даже больше, чем варианты их написания.
Так, может быть, использовать расстояние редактирования?
Неплохая была бы идея, если бы не тот факт, что эти метрики в большей степени рассчитаны именно на сравнение слов, а не словосочетаний с произвольным порядком слов. Стоит поменять имя и фамилию местами или вставить между ними псевдоним, и они показывают крайне неудовлетворительный результат.
Приходится в таком случае разбивать имена на отдельные слова и сравнивать уже каждое из них. А это существенно усложняет (и замедляет) работу алгоритма, даже если предварительно привести эти отдельные слова к их фонетическому индексу. Так же дополнительную сложность привносит то, что количество слов в имени является непостоянной величиной. С учетом возможных пропусков и перестановок слов уже сложно даже представить трудоемкость этого процесса.
Другие методы
К недостаткам метрики выделения общих форм можно отнести большую временную сложность вычисления релевантности при неясных возможностях индексирования, особенно коротких имен. Даже единичное выделение максимальной общей подстроки имеет временную сложность O(nm). А так как надо затем продолжить рекурсивный поиск общих подстрок в остатках, то вычисление функции релевантности представляется весьма накладной операцией, проигрывающей даже N-граммному сравнению.
Опять таки, при перемене словами мест, релевантность резко уменьшается.
Вычисление дистанции Джаро-Винклера работает существенно быстрее. Но, к сожалению, так же не является устойчивым к перемене слов местами.
Так что, чтобы не пришлось разделять и комбинировать слова в имени, волей-неволей пришлось остановиться на N-граммном анализе. Вернее, даже на триграммном, т.к. короткие корейские имена не располагают к выделению слишком длинных N-грамм.
Этап первый. Лобовой удар.
Итак, для начала, чтобы составить представление о временной сложности триграммного сравнения, я написал самый простой вариант скрипта, попарно сравнивающего имена по всей БД.
Написание и тестирование скрипта проводилось в домашних условиях на компьютере восьмилетней давности еще с одноядерным Intel Pentium D 925 на материнской плате ASUS P5B-E и с обычными заезженными хардами Seagate примерно того же возраста.
Скрипт этот работал, что называется, в лоб. Считывал БД, каждое имя, предварительно нормализованное, разбивал на уникальные триграммы и подсчитывал число их вхождений в каждое из предыдущих имен (т.е., находящихся в БД ранее испытуемого). Если результат деления удвоенного числа совпадений на сумму уникальных триграмм в каждом из этих имен превышал некоторый порог (например, 0,75 или 0,8), то это фиксировалось в файле.
Нормализация имени заключалась в следующем:
- Английские буквы и некоторые цифры заменялись сходными по написанию русскими буквами.
- Все строчные буквы заменялись прописными.
- Буква «Ё» заменялась на «Е», а «Ъ» на «Ь».
- Все прочие буквы, знаки, непечатные символы и их последовательности заменялись двумя пробелами.
- Имя обрамлялось двойными пробелами.
В результате такой нормализации получалось упрощенное имя без знаков препинания, без транслитерных символов, в котором каждое слово обрамлено или отделено от других слов двойными пробелами.
Использование двойных пробелов между словами, а так же в начале и конце имени, делало алгоритм триграммного анализа совершенно нечувствительным к перемене мест слов.
В нормализованном имени выделялись всевозможные уникальные триграммы — сочетания из расположенных подряд трех символов (включая пробелы).
Затем для двух имен вычислялся следующий коэффициент релевантности: удвоенное число общих триграмм делилось на сумму уникальных триграмм в каждом имени.
Требование к уникальности триграмм озвучено неспроста. С одной стороны, подсчет общего количества триграмм в именах без учета их уникальности позволит уверенно различать такие имена, как «Джон Смит» и «Джон Джон Смит». А учет только уникальных триграмм приведет к тому, что эти имена будут считаться идентичными.
С другой стороны, во-первых, потребность в различении подобных имен будет возникать не часто. А, во-вторых, подсчет релевантности по всем триграммам, а не только по уникальным, значительно усложнит эту процедуру. Потому что вместо удвоенного числа общих триграмм придется считать сумму вхождений триграмм из первого имени во второе и триграмм из второго имени в первое. Т.е., грубо это увеличит временные расходы на вычисление релевантности примерно в 2 раза. Ну и, в-третьих, это не позволит применить к процедуре вычисления релевантности некоторые оптимизации, о которых пойдет речь далее.
Итак, лобовой алгоритм был написан и опробован на первых нескольких тысячах имен. Результат был удручающим. Как и следовало ожидать, время поиска совпадений по всему массиву имен имело ярко выраженную квадратичную зависимость от его размера. Прогноз тренда на обработку всего массива из 130-140 тысяч имен составил около двух лет. Многовато будет!
Зато появилась начальная оценка производительности алгоритма.
Этап второй. Поиск способов оптимизации.
Прежде всего, пришлось оценить, какие элементы алгоритма нуждаются в оптимизации, а какой является пресловутым «бутылочным горлышком», тормозящим всю систему. Областей оптимизации было выявлено несколько:
- Начальная выборка из БД должна выдавать не весь массив имен, а только те, которые уже хоть чуть сходны с тестируемым, для уменьшения числа прочих операций. Анализ времени выполнения различных участков кода показал, что запросы к БД и являются «бутылочным горлышком». Необходимо было уменьшать, как время выполнения каждого запроса, так и число выдаваемых имен-претендентов в каждой выборке.
- Операции сравнения и копирования подстроки, проводимые со строками в мультибайтной кодировке UTF-8, по производительности в несколько раз уступают тем же операциям со строками в однобайтной кодировке.
- Не обязательно производить точное вычисление коэффициента релевантности, если доля общих триграмм мала. В этом случае появляется возможность прервать этот процесс, как только станет ясно. что даже если все остальные триграммы окажутся общими, это не приведет к превышению требуемого граничного значения.
- Прочее по мелочам.
Этап третий. Реализация.
Прежде всего, как самое простое, была выполнена попытка перехода от кодировки нормализованных имен UTF-8 к кодировке Windows-1251. Однако, оказалось, что MySQL весьма ревностно относится к хранению в БД строк в разной кодировке даже в разных таблицах. Что приводит к возникновению нелокализуемых ошибок при операциях с БД. Поэтому нормализованное имя хранится в дополнительной присоединенной таблице все равно в формате UTF-8, а при необходимости перекодируется в Windows-1251.
Хранение нормализованного имени существенно экономит время, т.к. нормализацию необходимо проводить для каждой записи только один раз.
Кроме того, в той же присоединенной таблице хранится число уникальных триграмм в нормализованном имени. Эта величина может быть использована для принудительного завершения вычисления релевантности в том случае, если становится очевидным слишком большое различие между именами. При этом вычислять каждый раз число уникальных триграмм в имени уже нет необходимости.
Ну и, самое главное, обработанные имена индексировались триграммным индексом. Т.е. в дополнительной таблице перечислялись все уникальные триграммы, присутствующие в нормализованном имени. При этом, сами триграммы, чтобы не хранить их в «медленной» кодировке UTF-8, хранились в виде целочисленного хеша — трем младшим байтам числа соответствовали числовые значения соответствующих символов в кодировке Windows-1251.
Но при этом был допущен совершенно неэффективный, как было выяснено в дальнейшем, подход — для каждой триграммы из проверяемого имени делалась своя собственная выборка имен-претендентов, которые потом объединялись в единый массив. При этом каждое имя в этом массиве сопровождалось счетчиком — в скольких выборках оно встретилось. Предполагалось, что это даст некоторый выигрыш в вычислении релевантности за счет того, что не надо будет затем раскладывать эти имена на триграммы — достаточно было использовать этот счетчик, чтобы сразу вычислить релевантность.
К сожалению, многократное проведение выборок из базы MySQL (в большей степени) и формирование объединенного массива имен (в меньшей степени) давали такие накладные расходы, которые многократно превышали выигрыш, получаемый в результате упрощения вычисления релевантности.
В результате описанных оптимизаций удалось достичь существенного сокращения временных затрат:
Применение триграммного индекса для начальной выборки сократило прогноз результирующего времени с двух лет до менее чем трех месяцев. Использование в его качестве числовых значений вместо подстрок в формате UTF-8 позволило дополнительно сократить время общей обработки еще на 10-12%. Но все равно 2,5 месяца непрерывной работы представлялись слишком большим сроком. Тонким местом оставалась начальная выборка похожих имен.
Этап четвертый. Дальнейшие улучшения.
Многократное обращение к БД по каждому триграммному индексу оказалось не лучшей идеей. Мало того, что многочисленные выборки выполнялись достаточно долго, так еще и консолидированный массив получался очень большим, и его обработка требовала значительных временных затрат несмотря на использование счетчика общих триграмм для каждого элемента.
Пришлось отказаться от идеи этого счетчика, но получать весь начальный набор имен-претендентов за один запрос при помощи SQL-конструкции WHERE IN. Это позволило сократить прогноз еще в несколько раз до одного месяца.
Далее была изменена процедура вычисления релевантности. На основании нижней границы релевантности и числа уникальных триграмм в именах вычислялось максимально допустимое число «промахов» — число триграмм в имени-претенденте, не входящих в проверяемое имя. Затем все триграммы имени-претендента проверялись на вхождение в проверяемое имя. Как только число «промахов» превышало максимально допустимое, сравнение прекращалось. Это позволило сократить прогноз времени еще на несколько процентов. Но до промышленных значений было все равно очень далеко.
Этап пятый. Решение.
Задача казалось неразрешимой. С одной стороны требовалось значительно сократить число имен в начальной выборке, с другой же это сокращение не должно было быть слишком искусственным, чтобы не отсечь случайно имена, которые находятся близко к нижней границе допустимого диапазона релевантности.
Найти подход помог простой просмотр найденных пар сходных имен. Практически во всех таких парах находились общие подпоследовательности длиной 6-7 символов (включая окаймляющие двойные пробелы). Путем нехитрых рассуждений (которые здесь не приводятся ввиду их нестрогости) можно прийти к выводу, что для достижения релевантности более 0,75, нормализованные имена должны иметь общую подстроку из 5 символов или длиннее.
Таким образом, от индексации предварительного поиска триграммами переходим к индексации пентаграммами (5-символьными подстроками). Чтобы уместить хеш пентаграммы в целочисленной переменной, имеющей в 32-разрядной версии PHP размер 32 бита, каждый символ представляем в виде 5-бит, благо символов всего 31 (без «Ё» и «Ъ») и пробел.
Еще одно небольшое дополнение.
Как писал выше, при вычислении релевантности уникальные триграммы одного из имен сравнивались на предмет совпадения с триграммами второго имени. При этом расчет прекращался при превышении числа «промахов» максимально допустимого количества.
Если число уникальных триграмм в первом имени значительно меньше числа уникальных триграмм во втором, то рассчитанное максимально допустимое число промахов может оказаться отрицательным. Это означает, что данные имена ну никак не могут быть сходными с заданной величиной релевантности. И проверять их нет необходимости.
Но эта отсечка не работает в противоположном случае, если число уникальных триграмм в первом имени значительно больше числа таковых во втором имени. Поэтому дополнительно в запрос выборки были введены граничные значения количества уникальных триграмм в нормализованном имени.
Это несколько спорное усовершенствование. При задании граничного значения релевантности 0,75 оно не приводит к ускорению, а, наоборот, приводит к потере производительности на 3% за счет увеличения сложности выборки. Но если задать границу релевантности 0,8, то получаем уже 3% выигрыша.
Тем не менее, данный прием был оставлен. Потери не такие уж большие, а вначале можно сделать предварительный поиск похожих пар с высокой степенью релевантности. И только после предварительной чистки задать граничное значение равным 0,75.
Итог.
В результате перехода от начальной выборки по общим триграммам к выборке по пентаграммам удалось существенно ускорить работу скрипта. Поиск похожих с релевантностью 0,8 пар среди 138,5 тысячи имен составил около 5 часов вместо одного месяца. Т.е. единичный поиск похожих имен во всей БД для заданного имени составляет (если принять квадратичную зависимость времени обработки) около 0,26 с. Несколько много, но надо учитывать, что это был тестовый прогон не на сервере с мощным процессором и высокопроизводительной дисковой системой, а на полумертвом домашнем компьютере восьмилетней давности.
В принципе, можно было бы осуществлять первоначальный поиск даже гексаграммами (индексными подстроками из 6 символов). Это давало ускорение еще в несколько раз. Но возникло обоснованное опасение, что могут отсеяться много пар азиатских коротких имен (и не только их). Да и смысла особого нет, т.к. последующий ручной анализ полученных пар (а их набралось более 11 тысяч) займет в любом случае несколько месяцев.
Зато индексация гексаграммами вполне пригодна для подсказок вида «Возможно, Вы имели в виду …», когда излишняя параноидность не требуется, а наоборот, следует находить минимальное количество наиболее подходящих имен.
В принципе, при работе с длинными именами можно использовать индексы семисимвольных подстрок. А чтобы поместить их в 32-битные переменные произвести предварительное фонетическое кодирование с целью сокращения числа символов до 15 и пробела. Но такая задача в тот момент не стояла.
К сожалению, вскоре после написания скрипта, сайт был заблокирован по обвинению в нарушении авторских прав. Хотя вскоре он переехал на другой адрес, из-за навалившихся проблем стало не до поиска дублирующих имен.
Фрагменты алгоритма:
Структуры таблиц БД
CREATE TABLE IF NOT EXISTS `prs_persons` (
`id` int(10) unsigned NOT NULL,
`name_ru` varchar(255) collate utf8_unicode_ci default NULL, //Переведенное на русский язык имя
//Прочие поля
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
CREATE TABLE IF NOT EXISTS `prs_normal` (
`id` int(10) unsigned NOT NULL,
`name` varchar(255) collate utf8_unicode_ci default NULL, //Нормализованное имя
`num` int(2) unsigned NOT NULL, //Число уникальных триграмм в нормализованном имени
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
CREATE TABLE IF NOT EXISTS `prs_5gramms` (
`code` int(10) unsigned NOT NULL, //Числовой код пентаграммы
`id` int(10) unsigned NOT NULL, //Идентификатор имени, в котором присутствует
KEY `code` (`code`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;
Константы и вспомогательные переменные, предварительные действия:
$opt_debug_show_sql = 0;
$opt_debug_mode = 0;
$opt_table_prefix = "prs";
define('MIN_RELEVANT', 0.8);
define('SITE_PREFIX', "…"); //Здесь храним префикс страницы персоны на сайте.
//Максимально допустимое соотношение количества уникальных триграмм,
//чтобы имена еще могли быть схожими.
$len_ratio = MIN_RELEVANT / (2 - MIN_RELEVANT);
$suitablesin = iconv("Windows-1251", "UTF-8",
"АаБбВвГгДдЕеЁёЖжЗзИиЙйКкЛлМмНнОоПпРрСсТтУуФфХхЦцЧчШшЩщЬъЫыЪьЭэЮюЯяAaBbCcEegHKkMmnOoPprTuXxYy03468");
$suitablesout =
"ААББВВГГДДЕЕЕЕЖЖЗЗИИЙЙККЛЛММННООППРРССТТУУФФХХЦЦЧЧШШЩЩЬЬЫЫЬЬЭЭЮЮЯЯААВЬССЕЕДНККМТНООРРГТИХХУУОЗЧБВ";
$charcode = array( ' ' => 0, 'А' => 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); //Пятибитные коды символов.
set_time_limit(0); //Время выполнения скрипта неограниченно.
function message_die($errno, $error, $file, $line)
{
if ($errno)
{
print "<p><b>Error " . $errno . " " . $file . "(" . $line . "):</b> " . $error;
die();
}
};
$fout = fopen("…", "w"); //Открываем файл для записи похожих пар.
//Здесь должны находиться подготовка списка имен к анализу и основной цикл сравнения.
fclose($fout);
Тело основного цикла сравнения:
//Для каждого еще непроанализированного имени:
$id = …; $name_ru = …; //Считываем ID персоны и имя в кодировке UTF-8.
$rusn = " "; //Нормализованное имя начинается двумя пробелами.
$ischar = FALSE;
for ($j = 0; $j < mb_strlen($name_ru, "UTF-8"); $j++)
{
$char = mb_substr($name_ru, $j, 1, "UTF-8");
if (($pos = mb_strpos($suitablesin, $char, 0, "UTF-8")) === FALSE)
{
if ($ischar)
{
//Все недопустимые символы заменяем двойными пробелами.
$rusn .= " ";
$ischar = FALSE;
}
}
else
{
//Прочие перекодируем в Windows-1251 с учетом возможного транслита.
$rusn .= $suitablesout{$pos};
$ischar = TRUE;
}
}
if ($ischar) $rusn .= " "; //Добавляем два пробела в конце.
if (strlen($rusn) < 5) continue; // Имена из одних пробелов не рассматриваются.
$norm = iconv("Windows-1251", "UTF-8", $rusn); //Перекодируем в UTF-8 для записи в БД.
//Заносим в массив уникальные пентаграммы нормализованного имени:
$subgramms = array();
//Нормализованное имя начинается с двух пробелов, имеющих код 0.
//Поэтому их просто не кодируем, а начинаем вычисление хеша пентаграммы с первой буквы.
$code = ($charcode[$rusn{2}] << 5) | $charcode[$rusn{3}];
for ($j = 4; $j < strlen($rusn); $j++)
{
$code = (($code << 5) | $charcode[$rusn{$j}]) & 0x1FFFFFF;
$subgramms[$code] = $code; //Записываем хеш пентаграммы в массив.
}
//Составляем список уникальных триграмм в нормализованном имени и подсчитываем их количество.
$trigramms = array();
for ($k = 0; $k < strlen($rusn) - 2; $k++)
$trigramms[$trigramm = substr($rusn, $k, 3)] = $trigramm;
$n = count($trigramms);
//Вычисляем граничные значения числа уникальных триграмм в сходных именах:
$nmin = ceil($n * $len_ratio);
$nmax = floor($n / $len_ratio);
//Считываем из БД список кандидатов на сходные имена.
$similars = fquery("SELECT n.id AS id, n.name AS name, n.num AS num FROM ^@5gramms AS g, ^@normal AS n WHERE g.code IN (^N) AND n.id = g.id AND
n.num >= ^N AND n.num <= ^N", $subgramms, $nmin, $nmax);
//Записываем в БД нормализованное имя и количество уникальных триграмм.
fquery("INSERT INTO ^@normal (id, name, num) VALUES (^N, ^S, ^N)", $id, $norm, $n);
//Записываем в БД список пентаграмм этого нормализованного имени.
foreach ($subgramms as $key=>$code)
fquery("INSERT INTO ^@5gramms (code, id) VALUES (^N, ^N)", $code, $id);
unset($subgramms); //И освобождаем его.
//Для каждого имени-кандидата:
for ($i = 0; $i < @mysql_num_rows($similars); $i++)
{
$similar = @mysql_fetch_assoc($similars) OR
message_die(@mysql_errno(), @mysql_error(), __FILE__, __LINE__);
$name = iconv("UTF-8", "Windows-1251", $similar['name']);
$simid = $similar['id'];
$m = $similar['num']; //Количество уникальных триграмм.
$nm = 0; //Число общих триграмм.
$done = TRUE;
$miss = floor($m - MIN_RELEVANT * ($n + $m) / 2); //Число допустимых "промахов".
for ($k = 0; ($k < strlen($name) - 2) & ($miss >= 0); $k++)
{
if (strpos($name, $trigramm = substr($name, $k, 3), 0) == $k)
{
//Если триграмма встретилась впервые (уникальная):
if (isset($trigramms[$trigramm])) $nm++; //Увеличиваем счетчик общих.
else $miss--; //Иначе уменьшаем оставшееся число допустимых промахов.
}
}
if ($miss >= 0)
//Если число промахов не превышено, выводим в файл информацию о
//схожей паре имен и величину релевантности.
fwrite($fout, SITE_PREFIX . $id ."\t" . $rusn ."\t" . SITE_PREFIX . $key . "\t" . $name . "\t" . ($nm + $nm) / ($m + $n) . "\r\n");
}
@mysql_free_result($similars) OR message_die(@mysql_errno(), @mysql_error(), __FILE__, __LINE__);
unset($trigramms); //Освобождаем список триграмм для повторного использования.
fclose($fout); //Закрываем файл со списком схожих пар.
Функция форматированных запросов к MySQL
[7]
// Syntax: fquery($query_template_text, $argument's_1_value, $argument's_2_value, ...)
// Special characters for a query template:
// ^@TableName - indicates that the combination ^@ is to be replaced with table prefix
// ^N - numeric parameter(s) (is not to be quoted), separated by comma if is array
// ^S - string parameter(s) (is to be quoted), separated by comma if is array
// ^0 - "NULL" or "NOT NULL"
// (c) Grigoryev Andrey aka GrAnd aka Pochemuk
// Thanks to Kamnev Artjom (Kamnium), Mesilov Maxim (Severus) for idea
// http://life.screenshots.ru
// When query successed returns Recordset for SELECT or True for others.
// When error occurs returns False.
function fquery()
{
global $opt_debug_mode;
global $opt_debug_show_sql;
global $opt_table_prefix; // getting prefix from the site's options
if (is_array(func_get_arg(0))) $args = func_get_arg(0);
else $args = func_get_args();
$qtext = $args[0]; // the first argument is always query template text
if (empty($qtext)) return false; // Hmm, nothing to do!
$qtext = str_replace("^@", ($opt_table_prefix == "") ? "" : ($opt_table_prefix . '_'), $qtext); // replacing with table prefixes
$i = 0; $curArg = 1;
$query = "";
while ($i < strlen($qtext)) // strlen is always up-to-date, even if special chars are replaced
{
if ($qtext{$i} == '^')
{
if ($curArg >= count($args)) return false; // too many parameters in the query template!
$i++;
switch ($qtext{$i})
{
case 'N':
{
if (is_null($args[$curArg]))
{
$query .= "NULL";
continue;
}
if (is_array($args[$curArg])) $query .= implode(", ", $args[$curArg]);
else $query .= $args[$curArg];
break;
}
case 'S':
{
if (is_null($args[$curArg]))
{
$query .= "NULL";
continue;
}
if (is_array($args[$curArg])) $query .= "'" . implode("', '", $args[$curArg]) . "'";
else $query .= "'" . $args[$curArg] . "'";
break;
}
case '0':
{
if (is_null($args[$curArg])) return false; // incorrect parameter, nulls are not allowed!
$args[$curArg] = strtoupper($args[$curArg]);
if (($args[$curArg] != "NULL") && ($args[$curArg] != "NOT NULL")) return false; // incorrect parameter, "NULL" or
"NOT NULL" only!
$query .= $args[$curArg];
break;
}
default: $query .= $qtext{$i};
}
$i++; $curArg++;
}
else $query .= $qtext{$i++};
}
if ($opt_debug_show_sql == 1) print('<P><CODE>Query string: "' . $query . '"<CODE></P>' . "\r\n");
$ResultData = mysql_query($query);
if (mysql_errno() <> 0)
{
if ($opt_debug_mode == 1)
{
print('<P><CODE>MySQL error: #' . mysql_errno() . ': ' . mysql_error() . '
');
print('Query string: ' . $query . '</CODE></P>');
}
}
return($ResultData);
} // End of fquery
Результат тестового прогона на первой тысяче записей:
Результат работы
| АДРЕС-1 | ИМЯ-1 | АДРЕС-2 | ИМЯ-2 | РЕЛЕВАНТНОСТЬ |
|---|---|---|---|---|
| /people/784 | ПИТЕР ДЖЕЙСОН | /people/389 | ПИТЕР ДЖЕКСОН | 0.8125 |
| /people/1216 | ЧАРЛЬЗ ДЭНС | /people/664 | ЧАРЛЬЗ ДЭННИС | 0.8 |
| /people/1662 | СТЮАРТ Ф УИЛСОН | /people/1251 | СТЮАРТ УИЛСОН | 0.914285714286 |
| /people/1798 | МАЙКЛ МАНН | /people/583 | МАЙКЛ ЛЕМАНН | 0.846153846154 |
| /people/2062 | МАЙКЛ БИРН | /people/265 | МАЙКЛ БИН | 0.8 |
| /people/2557 | ДЖИНА ДЭВИС | /people/963 | ДЖИН ДЭВИС | 0.8 |
| /people/3093 | ДЖ ДЖ ДЖОНСОН | /people/911 | ДОН ДЖОНСОН | 0.818181818182 |
| /people/3262 | ТОМ ЭВЕРЕТТ | /people/586 | ТОМ ЭВЕРЕТТ СКОТТ | 0.848484848485 |
| /people/3329 | РОБЕРТ РИТТИ | /people/3099 | РОБЕРТ БИТТИ | 0.827586206897 |
| /people/3585 | ТРЭЙСИ КЭЙ ВУЛЬФ | /people/2810 | ТРЭЙСИ ВУЛЬФ | 0.857142857143 |
| /people/3598 | АЛЕКСАНДР КАЛУГИН | /people/2852 | АЛЕКСАНДР КАЛЯГИН | 0.85 |
| /people/3966 | СЕРГЕЙ БОДРОВ | /people/2991 | СЕРГЕЙ БОДРОВ МЛ | 0.888888888889 |
| /people/3994 | СЕРГЕЙ БОБРОВ | /people/3966 | СЕРГЕЙ БОДРОВ | 0.8125 |
| /people/4049 | РИЧАРД ЛЬЮИС | /people/2063 | РИЧАРД ДЖ ЛЬЮИС | 0.882352941176 |
| /people/4293 | ДЖЕРРИ ЛИВЛИ | /people/2006 | ДЖЕРРИ ЛИ | 0.88 |
| /people/4377 | ДЖОАН КЬЮСАК | /people/3774 | ДЖОН КЬЮСАК | 0.827586206897 |
| /people/4396 | ДИН МАКДЕРМОТТ | /people/2614 | ДИЛАН МАКДЕРМОТТ | 0.833333333333 |
| /people/4608 | ШОН ДЖОНСТОН | /people/2036 | ДЖ ДЖ ДЖОНСТОН | 0.8 |
| /people/4981 | КРИСТОФЕР МЭЙ | /people/3233 | КРИСТОФЕР МЮРРЭЙ | 0.8 |
| /people/5019 | ДЖЕЙН АЛЕКСАНДР | /people/381 | ДЖЕЙСОН АЛЕКСАНДР | 0.842105263158 |
| /people/5551 | КАРЛОС АНДРЕС ГОМЕЗ | /people/1311 | КАРЛОС ГОМЕЗ | 0.810810810811 |
| /people/5781 | АЛЕКС НОЙБЕРГЕР | /people/4288 | АЛЕКС НЮБЕРГЕР | 0.8 |
| /people/5839 | ДЖОИ ТРАВОЛТА | /people/935 | ДЖОН ТРАВОЛТА | 0.8125 |
| /people/5917 | ДЖО ДЖОНСТОН | /people/2036 | ДЖ ДЖ ДЖОНСТОН | 0.833333333333 |
| /people/5917 | ДЖО ДЖОНСТОН | /people/4608 | ШОН ДЖОНСТОН | 0.8 |
| /people/6112 | ТОМАС РАЙАН | /people/4869 | ТОМАС ДЖЕЙ РАЙАН | 0.823529411765 |
| /people/6416 | БРАЙАН ДЖОРДЖ | /people/3942 | ДЖОРДЖ БРАЙАНТ | 0.848484848485 |
| /people/6520 | ДЖОН КАРНИ | /people/5207 | ДЖОН КАНИ | 0.8 |
| /people/6834 | ДЖОН ДЖ АНДЕРСОН | /people/5049 | ДЖО АНДЕРСОН | 0.838709677419 |
| /people/6836 | МАЙКЛ ЭСТОН | /people/5056 | МАЙКЛ УЭСТОН | 0.827586206897 |
| /people/6837 | ДЭВИД БАРОНЕ | /people/5884 | ДЭВИД БАРОН | 0.827586206897 |
| /people/7261 | БИЛЛИ ГРЭЙ | /people/1695 | БИЛЛИ РЭЙ | 0.8 |
| /people/7361 | АЛАН ДЭВИД | /people/3087 | ДЭВИД АЛАН БАШ | 0.838709677419 |
| /people/7447 | ДЭВИД ЭЙЕР | /people/2277 | ТЭЙЕР ДЭВИД | 0.814814814815 |
| /people/7497 | АЛЕКСАНДР КАРАМНОВ | /people/3857 | АЛЕКСАНДР КАРПОВ | 0.8 |
| /people/7499 | НИКОЛАС ЛАМЛИ | /people/4424 | НИКОЛАС ЛИ | 0.827586206897 |
| /people/7534 | РИЧАРД РИХЛЬ | /people/3547 | РИЧАРД НИХЛЬ | 0.857142857143 |
| /people/7547 | СВЕТЛАНА СТАРИКОВА | /people/1985 | СВЕТЛАНА СВЕТИКОВА | 0.8 |
| /people/7677 | ДЖЕЙС АЛЕКСАНДР | /people/381 | ДЖЕЙСОН АЛЕКСАНДР | 0.842105263158 |
| /people/7677 | ДЖЕЙС АЛЕКСАНДР | /people/5019 | ДЖЕЙН АЛЕКСАНДР | 0.833333333333 |
| /people/8000 | ГРЕГОРИ СМИТ | /people/7628 | ГРЕГОРИ П СМИТ | 0.909090909091 |
| /people/8137 | КАСПЕР КРИСТЕНСЕН | /people/128 | ДЖЕСПЕР КРИСТЕНСЕН | 0.8 |
| /people/8186 | ШЭЙН КОСУГИ | /people/6235 | КЭЙН КОСУГИ | 0.814814814815 |
| /people/8219 | БРЭНДОН ДЖЕЙМС ОЛСОН | /people/797 | ДЖЕЙМС ОЛСОН | 0.810810810811 |
| /people/8442 | ГУННАР ЙОЛФССОН | /people/7033 | ГУННАР ЙОНССОН | 0.8 |
| /people/8458 | ДЖОН АЛЕКСАНДР | /people/381 | ДЖЕЙСОН АЛЕКСАНДР | 0.810810810811 |
| /people/8458 | ДЖОН АЛЕКСАНДР | /people/5019 | ДЖЕЙН АЛЕКСАНДР | 0.8 |
| /people/8614 | ДЭВИД ХЕРМАН | /people/4945 | ДЭВИД ХЕЙМАН | 0.8 |
| /people/8874 | НИКОЛАС РОУГ | /people/1667 | НИКОЛАС РОУ | 0.827586206897 |
| /people/8987 | ДЭВИД РОСС | /people/4870 | ДЭВИД КРОСС | 0.814814814815 |
| /people/9132 | РОБЕРТ ЛОНГ | /people/7683 | РОБЕРТ ЛОНГО | 0.827586206897 |
| /people/9202 | РОБЕРТ МЕНДЕЛ | /people/3410 | РОБЕРТ МЭНДЕЛ | 0.8125 |
| /people/9229 | ЭШЛИ ЛОУРЕНС | /people/2534 | ЛОУРЕНС ЭШЛИ | 1 |
| /people/9303 | ДЖОН ЭЙЛАРД | /people/8703 | ДЖОН ЭЙЛУАРД | 0.827586206897 |
| /people/9308 | ШОН РОБЕРТС | /people/6552 | ШОН О РОБЕРТС | 0.903225806452 |
| /people/9347 | СТЕФЕН СЕРЖИК | /people/2911 | СТЕФЕН СУРЖИК | 0.8 |
| /people/9432 | ПОЛЛИ ШЕННОН | /people/2240 | МОЛЛИ ШЕННОН | 0.8 |
| /people/9583 | ДЖУЛИ ХАРРИС | /people/904 | ДЖУЛИУС ХАРРИС | 0.838709677419 |
| /people/9788 | ЭНТОНИ СТАРР | /people/8308 | ЭНТОНИ СТАРК | 0.8 |
| /people/9835 | МАЙКЛ У УОТКИНС | /people/4727 | МАЙКЛ В УОТКИНС | 0.864864864865 |
| /people/9893 | СТИВ МАРТИНО | /people/6457 | СТИВ МАРТИН | 0.827586206897 |
Ссылки и примечания:
1. Фонетическое кодирование.
> Фонетические алгоритмы. Хабрахабр
> «Как ваша фамилия», или Русский MetaPhone (Russian Metaphone description)
2. Расстояние Левенштейна. Википедия
3. Вычисление схожести слов на основе выделения общих форм реализована в PHP в функции similar_text. В документации PHP указывается, что в основе этой функции лежит алгоритм Оливера [1993]. Однако первоначально данный алгоритм под названием «Ratcliff/Obershelp Pattern Recognition Algorithm» был опубликован John W. Ratcliff на сайте программистов Dr. Dobb's (Pattern Matching: the Gestalt Approach) в 1988 году. А Ian Oliver всего лишь использовал его в своей книге «Programming Classics: Implementing the World's Best Algorithms».
4. Исходники алгоритма Джаро-Винклера можно посмотреть, например, здесь: Jaro-Winkler Distance
5. Триграммный индекс или «Поиск с опечатками». Хабрархабр
6. Жаннетта «Ангел» Деверю — персонаж культовой медиафраншизы "Wing Commander", включающей компьютерные космосимуляторы, стратегии, прочие формы игр, литературные произведения и фильм. Здесь приведена исключительно в связи с тем, что я, не разбираясь в звучании французских фамилий, долгое время считал, что она звучит «Деверо». Иллюстрация ошибочного перевода не «на слух», а «на глаз».
7. Основа функции форматированных SQL-запросов честно позаимствована у Камнева Артема и Месилова Максима из статьи «SQL-инъекции: борьба в удовольствие». К сожалению, сайт этих ребят в последнее время не загружается, но копию статьи еще можно найти: Sql-инъекции: борьба в удовольствие (к сожалению, без исходников). Убраны некоторые спорные возможности. Вместо них добавлена возможность передачи в качестве аргумента массива.
Поделиться с друзьями
Комментарии (23)
nikitasius
02.05.2017 14:00Вообще Deveraux нифига не Деверю. Французская концовка прямо таки и прет в глаза, что дает нам Девро (вторая е не произносится, и звучит только короткий звук в как 'ве').
Если же вы из тех, кто все на английский манер, то тут тоже никак не деверю, достаточно послушать великий гугл переводчик, скормив ему это слово и нажав на динамик.
Ваша отсылка
Вот приходит в наш родной паспортный стол капитан третьего ранга Jeannette Devereaux[6] и представляется по уставу четко и громко.
на
Жаннетта «Ангел» Деверю — персонаж культовой медиафраншизы "Wing Commander", включающей компьютерные космосимуляторы, стратегии, прочие формы игр, литературные произведения и фильм. Здесь приведена исключительно в связи с тем, что я, не разбираясь в звучании французских фамилий, долгое время считал, что она звучит «Деверо». Иллюстрация ошибочного перевода не «на слух», а «на глаз».
Полнейшая ахинея и незнание французского языка.
Если же кто-то до вас испортил слово, то… к чему это вообще?
Фонетический поиск способен найти имена, записанные с ошибками на слух, но не переведенные дилетантами-любителями.
kloppspb
02.05.2017 14:34Да, тоже резануло. На всякий случай полез проверять что там у бельгийцев (по сюжету она всё-таки не француженка), но… Для любого франкофона тут без вариантов. Разве что какие-то диалекты, но в любом случае если тут «самоназвание» отдельно взятого персонажа, то к общим правилам произношения это не относится.
ainoneko
02.05.2017 14:44Ещё меньшая проблема в том, что её фамилия вообще-то Deveraux (без третьей «e»), что тоже должно быть [дев(е)рО].
(Это же не японский, чтобы «всякие Ниномаэ» резвились с особенным чтением.)
Pochemuk
02.05.2017 14:51А вот это интересно. В блогах встречал с третьей «е», а на Кинопоиске этот персонаж записан без нее.
Надо обратиться к первоисточнику. Запущу дома DOSBox и WC первый под ним. И посмотрю, что там пишут.
Pochemuk
02.05.2017 14:45+1Ну так я же и писал, что французский я ни разу не знаю.
Во всяком случае, спасибо за это сообщение. Оно является прекрасной иллюстрацией написанному мной насчет перевода «на глаз, а не на слух».
В Интернете в блогах и всяких ЖЖ я встречал именно Деверю, и я думаю, что писали это люди в отличие от меня разбирающиеся во французском языке. В Вике, в статье про фильм — Деверо. Но фильм снимали как раз американоязычные кинодеятели. Они могли и ошибиться. А Вы пишете, что правильно — Девро.
Т.е. это имя уже могло быть написано, минимум, в трех вариантах.
Смысл как раз в том, чтобы найти сходные по написанию имена, а разбираться, принадлежат ли они одному персоналию или разным, и как звучит по-русски правильно — это уже совсем другая задача.kloppspb
02.05.2017 15:44писали это люди в отличие от меня разбирающиеся во французском языке
Не стоит сбрасывать со счетов и бритву Хэнлона :) Как это правильно произносится по-французски уже написали. Даже с учётом бельгийского происхождения Ангела — Деверо ещё допустимо, но Деверю — совершенно непонятно откуда могло взяться.
Ну и ссылочки:
http://wingcommander.wikia.com/wiki/Jeannette_Devereaux
http://www.wcnews.com/wcpedia/Jeannette_Devereaux
http://www.imdb.com/character/ch0018214/
https://en.wikipedia.org/wiki/DevereauxPochemuk
02.05.2017 16:07+1Ага! Все-таки Devereaux, а не Deveraux, как на КП написано!
Ну что ж… Я встречал еще и «Деверё» :)
Так что, от моего изобретения большая польза :D И оно не только дырку в стене закрывает.
Во всяком случае, думаю, если бы все эти написания присутствовали в этой БД, то анализатор нашел бы все пары сходных. А дальше пусть франко-бельгийцы голову ломают — как там по русски правильно писать.
Кстати, была еще идея сделать кластерный анализ по результатам его работы. Чтобы выдавал не разрозненные пары, а некие конгломераты сходных имен. Так, чтобы на концах списка находились самые отличающиеся, а в середине — максимально похожие на все остальные.
Но не задалось. Заказчик потерял интерес.kloppspb
02.05.2017 16:33Я встречал еще и «Деверё» :)
Devereux именно так и читается, во всяком случае окончание :-) Разница в одну букву в оригинальном написании тут существенна:
Devereaux is a name of French origin. It is a misspelling of the original surname Devereux based on the common English mis-pronunciation «Devero»
Проглатывание среднего звука «е» опционально, но вот между «eau» и «au» особой разницы в произношении (на русском) нет. Первый вариант более мягкий, второй пожёстче, но на нашенском это всё равно именно «о», в отличие от «eu».
P.S. Что-то вспомнились зарубы по поводу Paul Atreides — Пол он или Пауль :-)nikitasius
02.05.2017 17:00Проглатывание среднего звука «е» опционально
Французы как раз и проглатывают этот самый звук в устной речи. Не видел никого, кто бы его произносил, кроме туристов и тех, кто язык начал изучать :)
kloppspb
02.05.2017 17:44Я не про французов, а про франкофонов вообще — они очень разные бывают :) Хотя, конечно, далеко не профи, но язык в анамнезе с 8 лет, и пообщаться со многими доводилось, включая гвинейцев.
Они оба одинаковы. О оно и в африке О :)
На русском — да. Но между l'eau и beacoup есть же разница :)nikitasius
02.05.2017 20:05На русском — да. Но между l'eau и beacoup есть же разница :)
Ответ от француженки в полуметре от меня: разницы никакой.
Мадам окончила универ по специальности французский язык.
ainoneko
03.05.2017 07:26А разве слово «beacoup» (а не «beaucoup») уже есть во французском?
(Хотя «другой звук о» ([?]) у французов есть, но здесь вроде тот же самый?)
(Ешё хуже с тремя звуками «ё без й»: [?], [?] и [o] — их я никогда не различал.)nikitasius
03.05.2017 09:24А разве слово «beacoup» (а не «beaucoup») уже есть во французском?
Не обратил внимания на пропущенное u и прочли (и я и она) как beaucoup, где eau == au.
А на счет сабжа про закорючки в квадратных скобочках — моя кавалерия будет вечером, ибо [pl?-n?r] так тут никто не пишет и не говорит (кроме учебников в школах).
Так что отдам ваш комментарий на съедение моей мадам, как и плюсомет и напишу ответ.
nikitasius
04.05.2017 00:49И так, [?] — это носовой звук "con" например и там ничего общего с [o] "beau".
На счет трех звуков — там общего с [о] (тем самым О из beau) нет.
Pochemuk
02.05.2017 17:02Атрейдес или Атридис? :)
Ну так всё о том же я: Прежде чем спорить о русском написании следует обнаружить предмет спора. Т.е. различные варианты написания. А с этим анализатор худо-бедно справился.
Кстати, обратите внимание в результатах работы есть «Ричард Рихль» и «Ричард Нихль». А еще там в этой БД есть (в пример не вошли) «Ричард Риле» и «Ричард Рили». И все это — один и тот же человек! Но правильное написание — только «Рили» :)…
P.S. Все возможные пары этого имени были анализатором обнаружены с высокой степенью релевантности.
nikitasius
02.05.2017 17:07Первый вариант более мягкий, второй пожёстче
Они оба одинаковы. О оно и в африке О :)
Вот неплохое видео про О, правда оно не идеал языка (там с 28 секунды намек на юг франции в произношении maintenant).
С риском могу дать вот этот линк. Так как пополняется людьми, то не факт, что попадете на француза, который разговаривать умеет.
romamo
09.05.2017 10:20Боюсь, в вашей базе однофамильцев больше, чем задублированных персон. А это значит, что ваше решение не имеет практического смысла.
Задача решается элементарно по дополнительным признакам: дата рождения, год, фильмография и т.п.Pochemuk
09.05.2017 17:07+1Боюсь, я не вполне подробно описал суть проблемы.
1. БД персоналий создавалась полуавтоматически на основании списка актеров/режиссеров и прочих действующих лиц к фильму. Этот список представлял собой обычную текстовую строку, разделенную запятыми.
При добавлении фильма строка парсилась скриптом. Если имя уже присутствовало в БД, то создавалась связь между страничкой фильма и страничкой персоны. Если имени в БД еще не было, то страничка персоны (пустая) сначала создавалась.
Если имя в строке-списке было написано с ошибкой, то под него создавалась новая страница. Если ошибка была вовремя обнаружена и исправлена, то связь пересоздавалась, но ошибочная страница оставалась.
Если же ошибка не была исправлена, то получалось у одной персоны несколько страниц с разным написанием имени и с разным набором фильмов.
2. Дата рождения/смерти, место рождения и другие данные заполнялись теми же энтузиастами по мере возможностей и желания. Если страниц одного актера было несколько, то на одной могли быть эти данные, а на другой — биография и т.д. Причем, заполненных страниц было гораздо меньше, чем незаполненных.
3. Однофамильцы, действительно, есть. И достаточно много. Так что еще стояла задача их поиска и разделения их на разные страницы. Но это немного другая задача. Автоматически она не решается — только ручным анализом фильмографий и сравнением с другими БД, например с IMDb.
Только вот дело в том, что пока однофамильцы не разделены, у них всего одна страничка на всех. А если разделены, то каждому присвоен уникальный номер, например «Дэвид Прайс (II)». Поэтому их не могло быть «много» по определению. Либо на всех одна страница, либо их имена различаются уникальным номером.
А вот разных страниц одной персоны могло быть 2-3, а то и 4. Например, могло быть 4 страницы с такими именами:
- Так Сакагути
- Так Сакагучи
- Сакагучи Так
- Сакагути Так
А правильное из этого списка — только одно.
Вот и стояла задача обнаружить все имена, подозрительно схожие между собой. Чтобы провести ручной анализ их схожести, исправить и удалить лишние.
Во-первых, БД «худела», избавляясь от мусора. Поиск выдавал одну страницу, а не несколько, отличающихся только разным порядком слов.
Во-вторых, из нее удалялись имена с ошибочным написанием.
В-третьих, такие страницы объединялись — объединялись фильмографии.
Так что, практический смысл был вполне определенный.
Во всяком случае, среди найденных пар с релевантностью 1.0 было более 80% страниц двойников с разным порядком слов или с разными знаками препинания. Например, в одном прозвище написано в простых кавычках, а в другом — в двойных. Остальные принадлежали разделенным тезкам/однофамильцам.
Среди пар с меньшей релевантностью тезок не будет совсем, но будет достаточно много просто схожих имен разных персон. Вот поэтому и нужен ручной анализ, чтобы определить, что «Трейси Кэй» и «Трэйси Кэй Вульф» — это одна и та же актриса. Просто в разных фильмах она по разному в титрах указана. А так же в некоторых фигурировала под именем «Трэйси Вульф», но ничего общего с актрисой Трэйси Вульф, которая играла дочь чернокожего напарника в «Смертельном оружии» не имеет.
VolCh
Интересная статья, спасибо! Но, по-моему, очень не хватает человеческого описания окончательной версии алгоритма.
Pochemuk
Напишите, пожалуйста, что именно Вас интересует. Постараюсь дополнить или описать отдельным постом.
В принципе, основа описана в тексте, а фрагменты кода достаточно подробно комментированы. Отсутствуют некоторые фрагменты кода, т.к. они были заточены под конкретную реализацию исходного сайта и БД.
Т.е. повторюсь, основные идеи следующие:
1. Используется N-граммный анализ.
2. Для упрощения анализа имена нормализуются (см. в тексте).
3. Для начальной выборки используется 5-граммный индекс, вернее, его целочисленный хеш.
4. Внутри полученной выборки производится 3-граммный анализ по уникальным 3-граммам.
5. Перед началом вычисления релевантности определяется максимально допустимое число «промахов». При его превышении выисление релевантности прекращается без уточнения.
6. Дополнительно в начальной выборке можно указывать диапазон числа уникальных триграмм, т.к. существует их максимальное соотношение в сравниваемых именах, при превышении которого релевантность будет заведомо ниже заданной границы.
Остальное можно посмотреть в коде и комментариях к нему.
Если что будет непонятно — спрашивайте. Буду рад ответить.
VolCh
Спасибо. Собственно это и имел в виду.