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

Question

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

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

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

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

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

Answer 1

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

Answer 2

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

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

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

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

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

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

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

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

Я предполагаю, что ваши 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 генерирует все возможные отклонения от предыдущего набора, за исключением отклонений, уже существующих на предыдущем уровне. Он сохраняет «origin» как значение, связанное с ключом.

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

  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

Answer 6

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

Answer 7

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

Answer 8

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

1 - "abc" 2 - "bcd" 3 - "кдэ"

L Расстояние между 1 и 2 равно 2 (вычтите «a», добавьте «d»). Расстояние L между 2 и 3 равно 2 (вычтите «b», добавьте «e»).

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

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

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