Нужен алгоритм для поиска почти дублированных текстовых значений

Question

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

Я хотел бы сохранить возможность свободного тегирования, но хотел бы иметь способ отфильтровывать такие почти дубликаты.Общая коллекция тегов в настоящее время составляет 1500.Моя идея состоит в том, чтобы прочитать все из базы данных в mem и затем запустить алгоритм, который отображает «подозреваемые».

Моя идея подозреваемого состоит в том, что x% символов в строке совпадают(тот же символ и порядок), где х настраивается.Возможно, я мог бы написать действительно неэффективный способ сделать это, но мне было интересно, существует ли существующее решение этой проблемы?

Редактировать: Забыл упомянуть: недостаточно просто отсортировать теги, так как для этого потребуетсямне пройти весь набор, чтобы найти обманщиков.

Answer 1

Возможно, вы ищете алгоритм приблизительного соответствия строк. http://en.wikipedia.org/wiki/Approximate_string_matching.

по данному слову вы можете сопоставить его со списком слов и, если «расстояние» близко, добавить его к подозреваемым.

Быстрая реализация заключается в использовании динамического программирования, такого как алгоритм Нидлмана-Вунша. Я сделал пример этого в блоге на C #, где вы можете настроить «расстояние», используя файл поиска символов матрицы. http://kunuk.wordpress.com/2010/10/17/dynamic-programming-example-with-c-using-needleman-wunsch-algorithm/

Answer 2

В вашей логике есть некоторые недостатки.Например, что происходит, когда множественное число объекта отличается от единственного числа (т. Е. Человек против людей или даже конфета против конфет).

Если английский является основным языком, проверьте Soundex , что позволяет фонетические совпадения.Также рассмотрите возможность использования модели синонимов из краудсорсинга, где пользователи могут создавать ссылки на существующие теги.

Answer 3

Если вы действительно хотите сделать это эффективно, я бы предложил какую-то реализацию JavaScript, которая отображает возможности, когда пользователь вводит желаемый тег. Мало того, что это сэкономит время пользователя, чтобы счастливо увидеть 5 предложений по мере их ввода. Это автоматически остановит их от ввода «подозреваемых», когда «подозреваемый» появится в качестве предложения. Это, конечно, если они действительно не хотят «подозреваемых» в качестве неотложного.

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

Answer 4

Хорошо "либо содержит либо" хорошо? Вы можете выполнить SQL-запрос примерно так, если ваши изображения находятся в базе данных (что имеет смысл только):

SELECT * FROM ImageTags WHERE INSTR('theNewTag', TagName) > 0 OR INSTR(TagName, 'theNewTag') > 0 LIMIT 1;