Эффективный способ вычисления показателей сходства строк при большом размере выборки?

StackOverflow https://stackoverflow.com/questions/1609742

Вопрос

Допустим, у вас есть список из 10 000 адресов электронной почты, и вы хотели бы найти некоторых ближайших "соседей" в этом списке - определенных как адреса электронной почты, которые подозрительно близки к другим адресам электронной почты в вашем списке.

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

Допустим, я определяю "подозрительно близко к другому адресу электронной почты" как две строки, имеющие оценку Левенштейна меньше N.

Есть ли более эффективный способ найти пары строк, оценка которых ниже этого порога, помимо сравнения каждой возможной строки с любой другой возможной строкой в списке?Другими словами, можно ли решить проблему такого типа быстрее, чем O(n^2)?

Является ли оценка Левенштейна плохим выбором алгоритмов для решения этой задачи?

Это было полезно?

Решение

Да, вы можете найти все строки на заданном расстоянии строки за O (log n), используя BK-Tree . Альтернативные решения, включающие создание каждой строки с расстоянием n, могут быть быстрее для расстояния Левенштейна, равного 1, но объем работы быстро выходит из-под контроля на более длинные расстояния.

Другие советы

Вы можете сделать это с Левенштейном в O (kl) , где k - ваше максимальное расстояние, а l - максимальная строка.

По сути, когда вы знаете, как вычислить базовый Левенштейн, легко понять, что каждый результат, который дальше, чем k по главной диагонали, должен быть больше, чем k , Так что если вы рассчитываете основную диагональ с шириной 2k + 1 будет достаточно.

Если у вас 10000 адресов электронной почты, вам не понадобится более быстрый алгоритм. Компьютер может вычислить с помощью O (N ^ 2) достаточно быстро.

Левенштейн вполне подходит для такого рода проблем.

Кроме того, вы могли бы рассмотреть преобразование электронных писем с помощью soundex перед сравнением. Вы, вероятно, получите лучшие результаты.

Эта проблема известна как кластеризация и является частью более масштабного дедупликация проблема (когда вы должны решить, какой член кластера является "правильным"), также известная как слияние-очистка.

Однажды я прочитал несколько исследовательских работ именно на эту тему (названия приведены ниже), и в основном авторы использовали раздвижное окно ограниченного размера поверх отсортированного списка строк.Они будут только сравнивать (используя изменить расстояние алгоритм) N* N строк внутри окно, тем самым уменьшая вычислительную сложность.Если какие-либо две строки выглядели похожими, они объединялись в кластер (путем вставки записи в отдельную кластерную таблицу).

За первым прохождением по списку последовал второй проход там , где были струны перевернутый прежде чем приступить к сортировке.Таким образом, строки с разные головы у меня был еще один шанс подобраться достаточно близко, чтобы быть оцененным как часть того же окна.На этом втором проходе, если строка выглядела достаточно близко к двум (или более) строкам в окне, и эти строки уже были частями их собственных кластеров (найденных при первом проходе), то эти два кластера были бы объединенный (путем обновления таблицы кластеров), и текущая строка будет добавлена во вновь объединенный кластер.Этот подход к кластеризации известен как объединение-найти алгоритм.

Затем они улучшили алгоритм, заменив окно списком top X по существу уникальные прототипы.Каждая новая строка будет сравниваться с каждым из лучших X прототипов.Если бы строка выглядела достаточно близко к одному из прототипов, то она была бы добавлена в кластер прототипа.Если бы ни один из прототипов не выглядел достаточно похожим, строка стала бы новым прототипом, выталкивание самого старого прототипа из списка top X.(Использовалась эвристическая логика, чтобы решить, какая из строк в кластере прототипа должна использоваться в качестве нового прототипа, представляющего весь кластер).Опять же, если бы строка выглядела похожей на несколько прототипов, все их кластеры были бы объединены.

Однажды я реализовал этот алгоритм для дедупликации записей имен / адресов с размерами списков около 10-50 миллионов записей, и он работал чертовски быстро (и тоже хорошо находил дубликаты).

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

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

Библиография:

Эрнандес М.1995, Проблема слияния / очистки для больших баз данных.

Монж А.1997, Эффективный доменно-независимый алгоритм для обнаружения приблизительно повторяющихся записей базы данных.

Я не думаю, что вы можете сделать лучше, чем O (n ^ 2), но вы можете выполнить некоторые меньшие оптимизации, которых может быть достаточно для ускорения работы вашего приложения:

  • Вы могли бы сначала отсортировать все адреса электронной почты по части после @ и сравнивать адреса только там, где это одно и то же
  • Вы можете прекратить вычислять расстояние между двумя адресами, когда оно станет больше n

Редактировать:На самом деле вы можете сделать лучше, чем O (n ^ 2), просто посмотрите на ответ Ника Джонсона ниже.

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

Можно добиться большего успеха при условии решения проблемы.

Я предполагаю, что ваши 10.000 адресов довольно «фиксированы», в противном случае вам придется добавить механизм обновления.

Идея состоит в том, чтобы использовать расстояние Левенштейна, но в «обратном» режиме в Python: 

class Addresses:
  def __init__(self,addresses):
    self.rep = dict()
    self.rep[0] = self.generate_base(addresses)
      # simple dictionary which associate an address to itself

    self.rep[1] = self.generate_level(1)
    self.rep[2] = self.generate_level(2)
    # Until N

Метод generate_level генерирует все возможные изменения из предыдущего набора, за исключением изменений, которые уже существуют на предыдущем уровне. Он сохраняет «происхождение» как значение, связанное с ключом.

Тогда вам просто нужно найти свое слово в различном наборе: 

  def getAddress(self, address):
    list = self.rep.keys()
    list.sort()
    for index in list:
      if address in self.rep[index]:
        return (index, self.rep[index][address]) # Tuple (distance, origin)
    return None

При этом вы вычисляете различные наборы один раз (это занимает несколько раз ... но затем вы можете сериализовать его и сохранить его навсегда).

И тогда поиск гораздо эффективнее, чем O (n ^ 2), хотя точно определить его довольно сложно, поскольку он зависит от размера сгенерированных наборов.

Для справки посмотрите: http://norvig.com/spell-correct.html.

Допустим, у вас есть 3 строки:

1 - "abc" 2 - "bcd" 3 - "cde"

L Расстояние между 1 & amp; 2 - это 2 (вычтите «а», добавьте «д»). Расстояние L между 2 & amp; 3 - это 2 (вычтите «b», добавьте «e»).

Ваш вопрос заключается в том, можем ли мы определить расстояние L между 1 & amp; 3, используя 2 сравнения выше. Ответ - нет.

L Расстояние между 1 & amp; 3 - 3 (замените каждый символ), это невозможно сделать из-за результатов первых двух вычислений. Оценки не показывают, были ли выполнены операции удаления, вставки или замены.

Итак, я бы сказал, что Левенштейн - плохой выбор для большого списка.

Если вы действительно сравниваете адреса электронной почты, то очевидным способом сделать это было бы объединить алгоритм Левенштейна с сопоставлением доменов. Я могу вспомнить случаи, когда я подписывался на что-то несколько раз, используя один и тот же домен, но это были различия в части имени пользователя в адресе электронной почты.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top