Формулировка
Есть большая база текстов (сотни тысяч текстов). Длины текстов примерно одинаковые, около 250 символов, язык — английский. Некоторые из текстов отредактированы (исправлены опечатки, расставлены запятые и т.п.); таким образом в базе оказывается как оригинальный текст, так и его исправленная копия. Таких пар не очень много, скажем не более 1%. Задача: найти все такие пары.
Для формального определения, что такое «отредактированный текст», хорошо подходит редакционное расстояние (я использую модуль difflib в python). Так как обычно правок немного, то достаточно взять пары текстов, отличающиеся не более чем на 2-3 правки.
Проблема заключается в том, что текстов очень много, и попарно их сравнить не получается из-за того, что редакционное расстояние вычисляется довольно медленно. Более того, нет простого естественного способа разбить тексты на маленькие группы (например, по тематике), чтобы сократить счет.
Основная идея
Хочется разбить все множество текстов на маленькие подмножества таким образом, чтобы вычислять редакционное расстояние нужно было только внутри подмножеств. Сделать это можно следующим образом: сопоставим каждому тексту точку в некотором многомерном пространстве таким образом, чтобы близкие в редакционном смысле тексты перевелись в близкие точки, а далекие тексты в, скажем так, не очень близкие точки. Достаточно вычислять редакционное расстояние только для близких в геометрическом смысле текстов.
Второе требование на отображение достаточно мягкое — можно ошибаться, и переводить далекие тексты в близкие точки. Но каждая такая ошибка приводит к лишнему вычислению расстояния.
Для быстрого поиска близких точек можно воспользоваться пространственным индексом.
Реализация
В качестве такого отображения «текст -> точка» подойдет считающее буквы отображение. Пространство, которое мы рассматриваем, будет иметь размерность, равную количеству букв в алфавите языка. Координата, соответствующая некоторой букве, будет равна количеству вхождений буквы X в тексте. Например, f(«aac») = [2, 0, 1, 0, ..., 0]. Мы используем в качестве координат только буквы, и не используем пунктуацию, потому что наблюдения за текстами показали, что пунктуация может поменяться гораздо сильнее (и не обязательно из-за редактирования человеком; например, внешне похожие пунктуационные символы могут кодироваться разными юникод-последовательностями).
Таким образом, мы получаем из определения, что близкие тексты будут отображены в близкие точки.
Оказывается, что и обратное условие будет выполняться достаточно точно (для небольших расстояний — как раз наш случай).
После того, как каждому тексту поставлена в соответствие точка, мы строим пространственный индекс на этих точках (я использую модуль rtree для python). Индекс позволяет делать быстрые запросы типа «найти все точки, попавшие в определенный многомерный параллелепипед».
Вокруг каждой точки описываем куб со стороной = 4 (~ 2 * количество правок) и смотрим все точки, попавшие в этот куб. Поиск отредактированных текстов можно ограничить только этим кубом.
Небольшая оптимизация
Можно сократить количество точек для тестирования редакционным расстоянием увеличивая размерность пространства. Естественный кандидат на увеличение размерности — введение n-грамм в качестве координат. С другой стороны увеличение размерности уменьшает производительность пространственных индексов. Естественным образом встает задача выделения «полезных» n-грамм.
Однако даже простое введение небольшого количество координат вида
hash(bigramm) % 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».
Комментарии (17)
boeing777
08.07.2015 23:35следующие два текста совсем близки геометрически
Мне сразу вспомнилась эта статья на Хабре: habrahabr.ru/post/236503 — на первый взгляд, никак не связанные показатели статистики, но очень сильно коррелируют.
Вы рассмотрели интересную задачу, но, похоже, оптимизация алгоритма отрицательно сказалась на результатах. На мой взгляд, функция отображения в N-мерное пространство слишком сильно размазывает полезную информацию. Как я понял, эта функция отобразит два бесконечно длинных текста практически в одну точку? Ведь частотность конкретной буквы полностью определяется языком (в русском наиболее частая буква «о»). Думаю, функцию обязательно нужно усложнить. Первое, что приходит на ум, это увеличить размерность пространства в 2 раза. Одной букве будет соответствовать два числа: число вхождений в текст (как и сейчас) и сумма расстояний этой буквы от начала текста. Пример: допустим, алфавит всего из тех букв abc, текст «aabbbaaaccc» отобразится в точку ( (5,19), (3,9), (3,27) ). Числа 5,3,3 — это количество вхождений букв a,b,c. Число 19 для буквы a получено, как сумма позиций буквы a в тексте, то есть 0+1+5+6+7=19.
И еще один момент, по поводу куба вокруг каждой точки. Возможно, я что-то не так понял. Не проще ли было обойтись методом наименьших квадратов вместо R-tree?
ushanov Автор
09.07.2015 00:09Спасибо за комментарий.
функция отображения в N-мерное пространство слишком сильно размазывает полезную информацию
По-видимому Вы правы, и предложенный метод сработает только в случае коротких текстов и малом допустимом расстоянии Левенштейна. Однако на имеющейся базе скопления точек в одном кубе оказались редким исключением; как ни странно, в количестве букв довольно много информации.
Одной букве будет соответствовать два числа: число вхождений в текст (как и сейчас) и сумма расстояний этой буквы от начала текста.
Боюсь это соображение я не понял. Получается, что
«aabbbaaaccc»->( (5, 19), (3, 9), (3, 27) )
«aabbbaaacc»->( (5, 19), (3, 9), (3, 17) )
и расстояние между точками получается приличное.
Не проще ли было обойтись методом наименьших квадратов вместо R-tree?
Поясните пожалуйста, как тут применить метод наименьших квадратов.boeing777
09.07.2015 08:14метод сработает только в случае коротких текстов
Это действительно так. Несколько лет назад в институте была курсовая, где нужно было расшифровать текст, зашифрованный методом простой замены (перестановки букв в алфавите). В исходный данных было сказано, что язык — русский. Так вот, за счет ограниченной длины (порядка 300-400 символов) преподавателю удалось добиться «нестандартного» распределения плотности различных букв, и даже эвристика с наиболее частой буквой «о» в большинстве заданий не прокатывала. Были, например, тексты с наиболее повторяемой «и».
и расстояние между точками получается приличное
Я просто привел пример, как с помощью координат можно сохранить (иными словами, сжать с потерями) какую-то информацию об исходной строке. Для определения похожести, действительно, не годится.
метод наименьших квадратов
В данном случае я имел в виду обычное определение отклонения между двумя точками X(x1,x2...xn) и Y(y1,y2...yn):
R=(x1-y1)^2+(x2-y2)^2...(xn-yn)^2
Ограничив значения R некоторым порогом R0, можно получить множество точек внутри N-мерной сферы вокруг заданной точки. Такой способ не годится?ushanov Автор
09.07.2015 10:59Промахнулся
habrahabr.ru/post/262063/#comment_8492011boeing777
09.07.2015 12:20Тогда все ясно — я подозревал, что R-tree выбрано для понижения сложности. Просто не до конца понял идею.
ServPonomarev
09.07.2015 08:51Посмотрите этот пост, особенно первый пример, про опечатки.
Вы сможете значительно повысить качество распознавания слов с исправленными опечатками, а знаки пунктуации можно отрабатывать и расстоянием Левенштейна, но не на буквах, а на словах.
ushanov Автор
09.07.2015 08:58Можно брать и шар, но индекс нужен для того, чтобы сократить сложность поиска пар. Если считать без индекса, то сложность будет порядка квадрата от количества точек. С индексом — почти-линейная.
Также куб легче интерпретировать. Вставка/удаление буквы — плюс/минус к координате.
PsyHaSTe
09.07.2015 11:43Мне кажется, стоило воспользоваться стандартными методами кластерного анализа, возможно получилось бы быстрее и более научным способом.
Кстати, для кодирования текста вашим способом тогда хорошо было бы еще использовать положение буквы по модулю, например буква «а» на первом месте добавляет 1, на втором — 2, на третьем — 3, а на четвертом — снова 1. Выбирая период (чтобы не было переполнения), но с другой стороны чтобы он был достаточно большим, можно учесть текст, в котором много одинаковых букв, но которые различаются по смыслу.ushanov Автор
09.07.2015 21:41стоило воспользоваться стандартными методами кластерного анализа
Можно, пожалуйста, чуть подробнее этот момент.
К сожалению, я плохо разбираюсь в кластерном анализе, однако когда использовал (в другой задаче) разбиение на кластеры (в матлабе linkage/cluster), то мне пришлось вычислить заранее матрицу всех попарных расстояний. Статья же про то, что не обязательно вычислять все попарные расстояния.
ratatosk
09.07.2015 13:08+1Спасибо за интересную статью. Думаю, что можно взять вместо букв n-граммы и использовать Locality Sensitive Hashing. Если его использовать то можно избежать поиска ближайших точек с помощью r-дерева, которое будет плохо работать с n-граммами из-за большой размерности. Про поиск похожих текстов с помощью Locality Sensitive Hashing хорошо рассказывает Ульман в курсе Mining Massive Datasets (вторая неделя) class.coursera.org/mmds-001. Еще есть мысль попробовать понизить размерность n-грамных представлений с помощью Principal Component Analysis.
Nerock
09.07.2015 13:54Поправьте меня, если я говорю что-то не так.
А нельзя ли пробежаться по текстам, сложить ASCII коды символов, и сравнить их? Если в тексте содержится немного опечаток, то разница между суммами символов должна быть небольшой. А если тексты отличаются друг от друга, то и разница будет большая.ushanov Автор
09.07.2015 21:51Спасибо, я посмотрю распределение таких сумм, может быть что-то вскроется.
Мне кажется, что это — огрубление описанного метода. Вы фактически получаете линейное отображение из многомерного пространства (где координаты соответствуют буквам) в одномерное отображение. Если точки с трудом разделяются в многомерном, то, скорее всего, в одномерном будет только хуже.
slawter
Спасибо за довольно интересную статью, но лично мне немного не хватило конкретики, как минимум небольшие выдержки из кода были бы кстати, а если бы разбавить текст поясняющими картинками, то вообще было бы замечательно.