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

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

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

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

1 - «abc» 2 - «bcd» 3 - «cde»

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

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

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

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

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

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

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

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