Удаление "почти дублирующих" строк в субквадратичное время

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

Я хотел бы удалить "почти дубликаты" из набора данных на основе расстояния редактирования или чего-то подобного, а так как размер набора данных > 100 Кбайт, алгоритм должен быть субквадратичным по размеру набора данных. Сейчас я могу только подумать о том, чтобы помечать отдельные предложения или фразы, которые повторяются слишком часто, а затем удалять все отзывы, которые есть у них, но легко понять, как такая стратегия может иметь неприятные последствия. Есть ли общий алгоритм, который лучше работает?

Ответ 1

Очевидно, что решение этой проблемы в целом может потребовать написания достойной исследовательской работы. Вот мое предложение.

В биоинформатике мы все время сталкиваемся с этой проблемой. Наиболее используемым алгоритмом является BLAST (http://en.wikipedia.org/wiki/BLAST). Пожалуйста, пройдите через алгоритм, и вы можете получить представление о том, что задействовано.

Ответ 2

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

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