Ответ 1

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

Ответ 2

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

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

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

Левенштейн неплохо справляется с этой проблемой.

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

Ответ 3

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

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

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

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

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

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

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

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

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

Monge A. 1997, эффективный независимый от домена алгоритм для обнаружения примерно дублирующих записей базы данных.

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

Я полагаю, что ваши 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

Ответ 7

Скажем, у вас есть 3 строки:

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

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

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

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

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

Ответ 8

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