[Из песочницы] Поиск почти-дубликатов и геометрия
Недавно мне попалась задачка на поиск почти-дублей среди большого количества коротких текстов. Поиск готового решения не привел к успеху, а полученное решение оказалось довольно интересным, и я не смог отказать себе в удовольствии поделиться им.
Формулировка
Есть большая база текстов (сотни тысяч текстов). Длины текстов примерно одинаковые, около 250 символов, язык — английский. Некоторые из текстов отредактированы (исправлены опечатки, расставлены запятые и т.п.); таким образом в базе оказывается как оригинальный текст, так и его исправленная копия. Таких пар не очень много, скажем не более 1%. Задача: найти все такие пары.
Для формального определения, что такое «отредактированный текст», хорошо подходит редакционное расстояние (я использую модуль difflib в python). Так как обычно правок немного, то достаточно взять пары текстов, отличающиеся не более чем на 2–3 правки.
Проблема заключается в том, что текстов очень много, и попарно их сравнить не получается из-за того, что редакционное расстояние вычисляется довольно медленно. Более того, нет простого естественного способа разбить тексты на маленькие группы (например, по тематике), чтобы сократить счет.
Основная идея
Хочется разбить все множество текстов на маленькие подмножества таким образом, чтобы вычислять редакционное расстояние нужно было только внутри подмножеств. Сделать это можно следующим образом: сопоставим каждому тексту точку в некотором многомерном пространстве таким образом, чтобы близкие в редакционном смысле тексты перевелись в близкие точки, а далекие тексты в, скажем так, не очень близкие точки. Достаточно вычислять редакционное расстояние только для близких в геометрическом смысле текстов.
Второе требование на отображение достаточно мягкое — можно ошибаться, и переводить далекие тексты в близкие точки. Но каждая такая ошибка приводит к лишнему вычислению расстояния.
Для быстрого поиска близких точек можно воспользоваться пространственным индексом.
Реализация
В качестве такого отображения «текст → точка» подойдет считающее буквы отображение. Пространство, которое мы рассматриваем, будет иметь размерность, равную количеству букв в алфавите языка. Координата, соответствующая некоторой букве, будет равна количеству вхождений буквы X в тексте. Например, f («aac») = [2, 0, 1, 0, …, 0]. Мы используем в качестве координат только буквы, и не используем пунктуацию, потому что наблюдения за текстами показали, что пунктуация может поменяться гораздо сильнее (и не обязательно из-за редактирования человеком; например, внешне похожие пунктуационные символы могут кодироваться разными юникод-последовательностями).
Таким образом, мы получаем из определения, что близкие тексты будут отображены в близкие точки.
Оказывается, что и обратное условие будет выполняться достаточно точно (для небольших расстояний — как раз наш случай).
После того, как каждому тексту поставлена в соответствие точка, мы строим пространственный индекс на этих точках (я использую модуль rtree для python). Индекс позволяет делать быстрые запросы типа «найти все точки, попавшие в определенный многомерный параллелепипед».
Вокруг каждой точки описываем куб со стороной = 4 (~ 2 * количество правок) и смотрим все точки, попавшие в этот куб. Поиск отредактированных текстов можно ограничить только этим кубом.
Небольшая оптимизация
Можно сократить количество точек для тестирования редакционным расстоянием увеличивая размерность пространства. Естественный кандидат на увеличение размерности — введение n-грамм в качестве координат. С другой стороны увеличение размерности уменьшает производительность пространственных индексов. Естественным образом встает задача выделения «полезных» n-грамм.
Однако даже простое введение небольшого количество координат вида
hash(bigramm) % p
(остаток от деления хэша биграммы на натуральное число p) дает сильное уменьшение количества точек в кубе.
(Выбор параметров зависит от свойств базы текстов, реализации функции hash, но, на имеющейся у меня базе, использование p = 3 уменьшает количество тестируемых пар в два раза).
Не все биграммы одинаково полезны. Оказывается, что увеличение размерности (модуля p) не обязательно уменьшает количество тестируемых пар. Это связано с тем, что, при взятии остатка, некоторые биграммы, полезные сами по себе, сливаются в одну координату.
Забавное наблюдение
Оказывается, что почти-одинаковыми наборами букв иногда можно описывать десятки совсем разных по смыслу предложений (т.е. в один куб с небольшой длиной стороны может попадать большое количество текстов). Однако такое случается редко (на имеющейся у меня базе).
Сложно поверить, но следующие два текста совсем близки геометрически: «JSE closes at a record high JSE MARKET REPORT» и »365 Data Centers Offers Cloud Storage in 17 US Markets 25 September 2014».
