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

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

15
задан Community 23 May 2017 в 11:53
поделиться

8 ответов

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

7
ответ дан 1 December 2019 в 03:14
поделиться

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

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

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

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

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

5
ответ дан 1 December 2019 в 03:14
поделиться

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

1
ответ дан 1 December 2019 в 03:14
поделиться

Допустим, у вас есть 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 (заменить каждый символ), это невозможно сделать вывод из результатов первых двух вычислений. Оценки не показывают, были ли выполнены операции удаления, вставки или замены.

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

1
ответ дан 1 December 2019 в 03:14
поделиться

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

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

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

2
ответ дан 1 December 2019 в 03:14
поделиться

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

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

1
ответ дан 1 December 2019 в 03:14
поделиться

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

1
ответ дан 1 December 2019 в 03:14
поделиться

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

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

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

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

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

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

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

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

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

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

5
ответ дан 1 December 2019 в 03:14
поделиться
Другие вопросы по тегам:

Похожие вопросы: