Обнаружение дублированного текста / хэширование

Question

У меня есть наборы строк в базе данных. Каждый набор будет иметь менее 500 членов, будет десятки тысяч наборов, и строки будут на естественном языке. Я хотел бы обнаружить дубликаты строк в каждом наборе. Новые строки будут сравниваться с существующим набором и добавляться в базу данных, если они уникальны.

Существуют ли алгоритмы хеширования, которые были бы эффективны при поиске (очень) похожих строк? Например, строки могут содержать одинаковое количество слов, но кодировка может немного отличаться (UTF-8 против Latin-1).

Answer 1

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

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

Если вы хотите найти близкие совпадения, вы, вероятно, захотите выполнить какое-то хеширование сходства. В статье Википедии о Хешировании с учетом локальных особенностей описан ряд методов.

Основная идея, лежащая в основе ряда этих методов, состоит в том, чтобы вычислять несколько хэшей с очень потерями в каждой строке, от h [0] до h [n]. Чтобы найти новый набор строк, вы должны вычислить его хэши и посмотреть каждый из них. Все, что получает хотя бы одно совпадение, является «похожим», и чем больше совпадений, тем больше оно похоже (и вы можете выбрать, в какой пороге обрезать объекты).

Answer 2

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

Приведено описание алгоритма и ссылка на код. Короче говоря, это подход, основанный на n-граммах, который не предполагает предположения о содержании или структуре входных данных и генерирует подписи постоянной длины для всех входных документов.

Answer 3

Короткий ответ - просто угадайте, какой будет хороший хеш-параметр, который соответствует вашим представлениям о «похожих».

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

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

Answer 4

Если в базе данных всего 500 строк, возможно, вы можете напрямую сравнить каждую из них. Сначала преобразуйте в стандартное представление (скажем, UTF-16). Расстояние Левенштейна может быть хорошим способом сравнения сходства двух строк.

Answer 5

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

вместе с SVDLIBC , с которым довольно легко начать работу.

Answer 6

Это может быть излишним, но вы можете попробовать NLTK (Natural Language Toolkit) , основанный на Python.

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

Вы также можете использовать функции вероятности и классификации.