Алгоритм обнаруживает повторяющиеся / похожие строки в корпусе данных, например, в темах электронной почты, в Python

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

Я специально имею в виду информационные бюллетени, которые часто приходят с одного и того же адреса и повторяют название продукта / услуги / группы в теме.

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

Теперь многие строки темы не смогут сопоставить строку, но «Друзья Google: Наши последние новости» «Друзья Google: Чем мы занимаемся сегодня» больше похожи друг на друга, чем случайная строка темы, например: «У Virgin Airlines есть отличная распродажа сегодня "" Летите рейсом Virgin Airlines "

Итак - как я могу начать автоматически извлекать тенденции / примеры строк, которые могут быть более похожими.

Подходы, которые я рассмотрел и отверг («потому что должен быть какой-то лучший способ»):

  • Извлечение всех возможных подстрок и их упорядочение по частоте их появления, а также выбор соответствующих подстрок вручную.
  • Удаление первого или двух слов, а затем подсчет появления каждой подстроки
  • Сравнение расстояния Левенштейна между записями
  • Какой-то индекс подобия строк ...

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

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

После этого я бы сопоставил появление определенных строк темы с адресами 'От' - я не уверен, есть ли хороший способ построить структуру данных, которая представляет, насколько вероятно / нет два сообщения являются частью 'одного и того же электронного письма. list »или путем фильтрации всех моих тем / адресов электронной почты в пулы вероятных« связанных »писем, а не - но эту проблему нужно решить после этого.

Любое руководство будет оценено.


python string email fuzzy-search data-mining
person Rizwan Kassim    schedule 02.05.2010    source источник
comment
Слово, которое вы ищете, - ‹a href=en.wikipedia.org/wiki / ›.   -  person Ignacio Vazquez-Abrams    schedule 02.05.2010
comment
Я нашел этот вопрос SO, который также устанавливает некоторые более известные алгоритмы. stackoverflow .com / questions / 653157 /   -  person Rizwan Kassim    schedule 03.05.2010

Ответы (2)


arrow_upward
4
arrow_downward

Сначала я бы превратил каждую строку символов в набор или мультимножество слов (игнорируя пунктуацию и различия в нижнем / верхнем регистре). (Если этого недостаточно, во втором проходе я мог бы попробовать пары или даже тройки соседних слов, известные как биграммы и триграммы). Ключевой мерой сходства между сокращенными таким образом строками является то, какие слова, которые не часто встречаются в целом (не the, and и т. Д .;-), являются общими для обеих строк, поэтому простое пересечение множеств (или мультимножество пересечения, но для вашего простого случая использования я думаю, что просто наборы будут работать нормально, особенно наборы биграмм) должны быть достаточными для измерения "общности". Слово, которое является общим для этих двух строк, должно иметь большее значение, чем реже оно встречается, поэтому отрицательный логарифм частотности слова во всем корпусе - отличная отправная точка для этой эвристики.

person Alex Martelli    schedule 02.05.2010
comment
Это интересный подход - проблема: одной из моих целей в этом проекте было изучить уже существующие алгоритмы, а не писать свой собственный для этой проблемы, чтобы я лучше понимал проблемное пространство. Это похоже на конкретный подход типа «подойдет для этого случая», а не на «вот обычно используемый инструмент», и я немного боюсь вычислительной интенсивности. (Опять же, это все еще лучший ответ, который я получил, так что спасибо!) - person Rizwan Kassim; 03.05.2010
comment
@RizwanK, работа с потоками слов (часто несколько нормализованных, например, по регистру), а не с символами, является очень распространенным подходом (а не инструментом ;-) в поиске информации, а также наборами или мультимножествами (слов, биграмм, триграмм) что угодно, только не редко. Если вы ищете существующий код Python, чтобы помочь с этим, вы можете найти что-то в NLTK, хотя я не уверен. Но я определенно не изобретал подходы к управлению данными на лету только для вашей конкретной проблемы ;-). Во всяком случае, краткость темы электронного письма относительно обычных документов, обрабатываемых в IR, должна снизить вычислительную нагрузку! - person Alex Martelli; 04.05.2010
comment
Но я определенно не изобретал подходы к управлению данными на лету для решения вашей конкретной проблемы, только ухмылка Справедливо. Вы знаете, есть ли название для предложенного вами подхода? Спасибо! - person Rizwan Kassim; 05.05.2010
comment
@Rizwank, я не уверен, что есть конкретное имя для превращения строк символов в строки слов и т. Д. - person Alex Martelli; 05.05.2010

arrow_upward
1
arrow_downward

Гладкий BLEU

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

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

К сожалению, у меня нет указателя на реализацию Python BLEU, но вы найдете реализацию Perl из NIST здесь.

person dmcer    schedule 03.05.2010