Слияние дубликатов в списке? - Вопрос сложнее, чем кажется

Question

Итак, у меня есть огромный список записей в БД ( MySql )

Я использую Python и Django при создании моего веб-приложения.

Это базовая модель Django, которую я использую:

class DJ(models.Model):
    alias = models.CharField(max_length=255)
    #other fields...

В моей БД у меня есть сейчас дубликаты

например. Выше и дальше , Выше и дальше , Выше и дальше , DJ Выше и дальше , диск Jokey выше и дальше , ...

Это проблема ... так как она проделывает большую дыру в моей БД и, следовательно, в моем приложении.

---

Я уверен, что другие люди сталкивались с этой проблемой и думали об этом.

Мои идеи следующие:

• Создать набор правил, чтобы нельзя было создать новую запись?

  например. «DJ Above and Beyond» нельзя создан потому, что "Вверх и за" находится в БД

• Как-нибудь связать эти псевдонимы друг с другом?

  например. относятся "DJ Above and Beyond" к "Above & Beyond"

---

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

Любая помощь будет принята с благодарностью! Спасибо, ребята.

Answer 1

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

Если вы не можете определить систему правил, которая может работать для любых x и y, является ли x дубликатом y, вам придется столкнуться с этим в нечеткой, человеческой способ.

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

Answer 2

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

• Строковое расстояние на самом деле не работает, так как строки, которые алгоритмически близки, могут не быть семантически близкими (например, «DJ Above & Beyond» должен соответствовать «Above and Beyond», но не «DJ Above & Beyond 2», который ближе в Расстояние Левенштейна.
• Некоторые дешевые альтернативы синтаксическому анализу на естественном языке: soundex , который будет совпадать по фонетическим звукам, и Stemming , который удаляет префиксы / суффиксы для нормализации основ слов. Я полагаю, вы могли бы создать связанный список корней слов, но это было бы не очень точно.
• Если это программа, взаимодействующая с пользователем, вы можете повторить "почти промахи" пользователю, например, «Является ли один из них тем, что вы хотели ввести?»
• Вы могли бы нормализовать записи некоторым способом, чтобы разные записи отображались на одно и то же нормализованное значение (например, case normalize, "&" -> "And" и т. Д., И т. Д., Что некоторые из приведенных выше предложений могут быть шагом к ) для поиска ошибок или сопоставления нескольких входных данных с одним значением.

Добавьте оговорку, что мой опыт применим только к английскому языку, например английский PorterStemmer не распознает одно французское название, которое вы там вставили.

Answer 3

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

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

Это действительно процесс, в котором должен участвовать человек.

Answer 4

Как насчет изменения модели, чтобы "псевдоним" представлял собой список ключей для другой таблицы, которая выглядит следующим образом (пропуская такие маленькие слова, как "the", "and" и т. Д.): 1 => выше; 2 => Вне; 3 => Диск; 4 => Джокей;

Затем, когда вы хотите вставить новую запись, просто проверьте, сколько значащих слов из заголовка уже есть в таблице и соответствуют существующим в данный момент модельным объектам. Если более 50% (например), возможно, у вас есть совпадение, и вы можете показать их список посетителю и спросить: «Вы имеете в виду кое-что из этого».

Answer 5

Прежде всего, конечно, интересно задание на программирование (НЛП и т. Д.). Но, как уже упоминалось, это излишнее стремление к совершенству.

Но, как уже упоминалось, другой взгляд («социальный»): кто вводит данные, кто их просматривает, как долго и насколько правильно оно должно быть? Так что это проблема соглашения об именах, напоминающая мне отличный проект musicbrainz.org - если ваш сайт «просто работает» или вы предпочитаете следовать стандартам, в последнем случае я бы сориентировался в проекте mb - если вы не Я сделал это и не слышал об этом. то есть. см. здесь для Above & Beyond : для них определен псевдоним, они используют его для поиска пользователей. http://musicbrainz.org/show/artist/aliases.html?artistid=58438 проверьте также страницу Artist_Alias ​​в вики.

Модель данных стоит посмотреть, и есть даже несколько привязок API для синхронизации данных, также в Python.

Answer 6

Вы можете попытаться решить эту проблему только для этого экземпляра (заменив «&» на «&» и «DJ» на «Disk jokey» или проигнорировав «DJ» и т. Д.). Если ваш стол содержит только диджеев, вы можете установить несколько таких правил. Если ваша таблица содержит более разнообразные вещи, вам придется использовать более структурный подход. Не могли бы вы дать образец вашего набора данных?

Answer 7

Это не полное решение, но одна мысль, которая у меня была:

class DJ(models.Model):
    #other fields, no alias!

class DJAlias(models.Model):
    dj = models.ForeignKey(DJ)

Это позволит вам иметь несколько псевдонимов для одного и того же диджея.

Но, тем не менее, вам нужно будет найти правильный способ убедиться, что псевдонимы добавлены в правильный dj. См. Доминик пост.

Но если вы проверите псевдоним по нескольким другим псевдонимам, указывающим на один dj, алгоритмы могут работать лучше.

Answer 8

Если вы используете только имена исполнителей или имена, связанные со СМИ, было бы гораздо лучше использовать API last.fm или echonest, поскольку у них уже есть огромный набор правил и огромная база данных, на которую можно рассчитывать.

Answer 9

Похоже, fuzzywuzzy идеально соответствует вашим потребностям.

Эта статья объясняет причину ее создания, которая очень точно соответствует вашим требованиям - в основном, для обработки ситуаций, в которых две разные вещи были названы немного по-разному:

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