Какой алгоритм вы бы лучше всего использовали для сходства строк?

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

Поэтому у меня может быть один адрес, который выглядит так:

1 someawesome street, anytown, F100 211

позже я могу найти этот адрес в немного другом формате.

1 someawesome street, F100 211,

или, возможно, столь же неопределенно, как

someawesome street F100

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

Какие алгоритмы / методы / метрики строк я должен смотреть? Расстояние Левенштейна кажется очевидным выбором, но любопытно, есть ли здесь другие подходы.

Алгоритм Левенштейна основан на количестве вставок, удалений и подстановок в строках.

К сожалению, он не принимает во внимание обычную орфографическую ошибку, которая представляет собой транспонирование двух символов (например, «что-то удивительное» или «что-то удивительное»). Поэтому я бы предпочел более надежный алгоритм Дамерау-Левенштейна .

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

1 someawesome street, anytown, F100 211       (reference) 
1 someawesome st.,anytown                     (difference of 15, same address)     
1 otherplaces street,anytown,F100211          (difference of 13, different ddress) 
1 sameawesome street, othertown, CA98200      (difference of 13, different ddress)
anytown, 1 someawesome street                 (28 different same address)
anytown, F100 211, 1 someawesome street       (37 different same address)

Эти эффекты имеют тенденцию ухудшаться для более короткого названия улицы.

Так что вам лучше использовать более умные алгоритмы. Например, Артур Рац опубликовал на CodeProject алгоритм для умного сравнения текста. Алгоритм не распечатывает расстояние (его можно соответствующим образом увеличить), но он идентифицирует некоторые сложные вещи, такие как перемещение текстовых блоков (например, перестановка между городом и улицей между моим первым примером и моим последним примером).

Если такой алгоритм является слишком общим для вашего случая, вам следует по-настоящему работать по компонентам и сравнивать только сопоставимые компоненты. Это непросто, если вы хотите разобрать любой формат адреса в мире. Но если цель более конкретна, скажем, США, это, безусловно, выполнимо. Например, «улица», «улица», «место», «площадь» и их обычные орфографические ошибки могут указывать на улицу, часть адреса, ведущей частью которой в принципе будет число. Почтовый индекс поможет найти город, или, возможно, он является последним элементом адреса, или, если вам не нравится угадывать, вы можете найти список названий городов (например, загрузить бесплатную базу данных почтовых индексов). Затем вы можете применить Damerau-Levenshtein только к соответствующим компонентам.

Расстояние Левенштейна лучше для слов

Если слова (в основном) написаны правильно, посмотрите на пакет слов . Может показаться, что я слишком убита, но сходство TF-IDF и косинуса .

Или вы можете использовать бесплатный Lucene. Я думаю, что они делают косинус сходства.

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

Расстояние Левенштейна полезно, но только после того, как вы разделите адрес на части. Рассмотрим следующие адреса. 123 someawesome st.и 124 someawesome st.эти адреса совершенно разные места, но их Левенштейна только 1. Это также может быть применено к чему - то , как 8th st.и 9th st.подобные названия улиц делать , как правило , не появляются на той же странице, но это не неслыханное. Например, на веб-странице школы может быть указан адрес библиотеки через улицу или церкви в нескольких кварталах вниз. Это означает, что единственными данными, по которым легко использовать расстояние Левенштейна, является расстояние между двумя точками данных, например расстояние между улицей и городом.

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

StreetNumber < Street < City < State < Country

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

Вы спрашиваете об алгоритмах сходства строк, но ваши строки являются адресами. Я бы отправил адреса в API определения местоположения, такой как Google Place Search, и использовал бы его formatted_addressкак точку сравнения. Это кажется самым точным подходом.

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

Один классный алгоритм, который полезен, но требует предустановленной базы данных предыдущих ответов, называется: Расстояние редактирования строки.

Расстояние редактирования строки, как функция, может вернуть обратно «насколько различны эти два слова».

Такие слова, как «догма» и «собака», вы получите значение 3 (для 3 дополнительных символов).

Или «кот» и «шляпа», вернуть значение 1 (для одного другого персонажа).

(Источник: https://en.wikipedia.org/wiki/Edit_distance )

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

Вы описываете широкую категорию алгоритмов здесь. Проверьте поиск ближайшего соседа

Как упоминалось в комментарии, если вы найдете способ разделить компоненты адреса (название улицы, номер и т. Д.), Это значительно облегчит задачу.

LongestCommonSubsequence (из Apache commons-text) может быть другим подходом, чтобы попробовать с адресами. Если вы определите сходство двух как отношение общая длина подпоследовательности / максимальная (длина адреса) », то вы можете применить порог допуска - например, 0,8, который будет определять совпадение / отсутствие совпадения. Таким образом, вы сможете сопоставлять адреса, такие как « 1 someawesome st., Anytown » и « 1 someawesome street., Anytown ».

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