Можно использовать класс DecimalFormat, в конечном счете отображение валюты оценивает. Это оказывает поддержку локализации и довольно расширяемо.
Ага - вы можете найти все строки на заданном расстоянии от строки за время O (log n), используя BK-Tree . Альтернативные решения, включающие создание каждой строки с расстоянием n, могут быть быстрее для расстояния Левенштейна, равного 1, но объем работы быстро выходит из-под контроля на больших расстояниях.
Вы можете сделать это с помощью Левенштейна в O (kl)
, где k
- ваше максимальное расстояние, а l - максимальная строка.
В основном, когда вы знаете, как вычислить базовый уровень Левенштейна, легко понять, что каждый результат, который больше, чем k
от главной диагонали должно быть больше k
. Так что, если вы вычисляете главную диагональ с шириной 2k + 1
, будет достаточно.
Если у вас 10000 адресов электронной почты, вам не понадобится более быстрый алгоритм. Компьютер может достаточно быстро вычислить с O (N ^ 2)
.
Левенштейн неплохо подходит для такого рода задач.
Также вы можете подумать о преобразовании писем с помощью soundex перед сравнением. Вероятно, вы получите лучшие результаты.
10 000 адресов электронной почты - это немного. Для поиска сходства в большем пространстве вы можете использовать шинглинг и мин-хеширование . Этот алгоритм немного сложнее реализовать, но он намного эффективнее на большом пространстве.
Допустим, у вас есть 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 (заменить каждый символ), это невозможно сделать вывод из результатов первых двух вычислений. Оценки не показывают, были ли выполнены операции удаления, вставки или замены.
Итак, я бы сказал, что Левенштейн - плохой выбор для большого списка.
Я не думаю, что вы можете сделать лучше, чем O (n ^ 2), но вы можете сделать несколько небольших оптимизаций, которых может хватить для ускорения работы вашего приложения:
РЕДАКТИРОВАТЬ: На самом деле вы можете сделать лучше чем O (n ^ 2), просто посмотрите на ответ Ника Джонсона ниже.
Можно добиться большего при условии устранения проблемы.
Я полагаю, что ваши 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
Если вы действительно сравниваете адреса электронной почты, то один из очевидных способов сделать это - объединить алгоритм Левенштейна с сопоставлением доменов. Я могу вспомнить случаи, когда я подписывался на что-то несколько раз, используя один и тот же домен, но с разными вариантами имени пользователя в адресе электронной почты.
Эта проблема известна как кластеризация и является частью более крупной проблемы дедупликации (где вы можете решить, какой член кластера является «правильным»), также известной как слияние-очистка .
] Я однажды прочитал несколько исследовательских работ именно по этой теме (имена приведены ниже), и в основном, авторы использовали скользящее окно ограниченного размера над отсортированным списком строк. Они будут только сравнивать (используя алгоритм расстояния редактирования ) N * N строк внутри окна, тем самым снижая вычислительную сложность. Если любые две строки выглядели одинаково, они объединялись в кластер (путем вставки записи в отдельную таблицу кластеров).
За первым проходом по списку следовал второй проход , где строки были перевернуты перед сортировкой. Таким образом, строки с разными головками имели еще один шанс приблизиться достаточно близко, чтобы их можно было оценить как часть одного окна. На этом втором проходе, если строка выглядела достаточно близко к двум (или более) строкам в окне, и эти строки уже были частями своих собственных кластеров (найденных на первом проходе), тогда два кластера будут объединены (путем обновления таблицы кластеров), и текущая строка будет добавлена к вновь объединенному кластеру . Этот подход к кластеризации известен как алгоритм поиска объединения .
Затем они улучшили алгоритм, заменив окно списком X по существу уникальных прототипов . Каждая новая строка будет сравниваться с каждым из X лучших прототипов. Если строка будет выглядеть достаточно близко к одному из прототипов, она будет добавлена в кластер прототипа . Если бы ни один из прототипов не выглядел достаточно похожим, строка стала бы новым прототипом , вытесняя самый старый прототип из верхнего списка X. (Для решения, какая из строк в кластере прототипа должна использоваться в качестве нового прототипа, представляющего весь кластер, использовалась эвристическая логика). Опять же, если бы строка выглядела похожей на несколько прототипов, все их кластеры были бы объединены.
Однажды я реализовал этот алгоритм для дедупликации записей имен / адресов с размерами списков, составляющих около 10-50 миллионов записей, и он работал хорошо. чертовски быстро (и обнаружил дубликаты тоже хорошо).
В целом для таких проблем, конечно, самая сложная часть - это найти правильное значение порога сходства . Идея состоит в том, чтобы фиксировать все дубликаты без получения слишком большого количества ложных срабатываний . Данные с разными характеристиками обычно требуют разных пороговых значений. Выбор алгоритма расстояния редактирования также важен, поскольку одни алгоритмы лучше подходят для ошибок оптического распознавания текста, в то время как другие лучше подходят для опечаток, а третьи лучше для фонетических ошибок (например, при получении имени по телефону).
реализован алгоритм кластеризации, хороший способ проверить его - получить список уникальных выборок и искусственно изменить каждую выборку для получения ее вариаций, сохраняя при этом тот факт, что все вариации произошли от одного и того же родителя. Затем этот список перемешивается и передается в алгоритм. Сравнение исходной кластеризации с кластеризацией, произведенной алгоритмом дедупликации, даст вам балл эффективности .
Эрнандес М. 1995, Проблема слияния / очистки больших баз данных.
Монж А. 1997, Эффективный домен-независимый алгоритм для обнаружения приблизительно повторяющихся записей в базе данных.