Поиск почти-дубликатов и геометрия

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

Мне очень интересен бенчмарк алгоритма на таких вот текстах:

Казнить, нельзя помиловать.

Казнить нельзя, помиловать.

следующие два текста совсем близки геометрически

Мне сразу вспомнилась эта статья на Хабре: 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?

Посмотрите этот пост, особенно первый пример, про опечатки.

Вы сможете значительно повысить качество распознавания слов с исправленными опечатками, а знаки пунктуации можно отрабатывать и расстоянием Левенштейна, но не на буквах, а на словах.

Можно брать и шар, но индекс нужен для того, чтобы сократить сложность поиска пар. Если считать без индекса, то сложность будет порядка квадрата от количества точек. С индексом — почти-линейная.
Также куб легче интерпретировать. Вставка/удаление буквы — плюс/минус к координате.

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

Кстати, для кодирования текста вашим способом тогда хорошо было бы еще использовать положение буквы по модулю, например буква «а» на первом месте добавляет 1, на втором — 2, на третьем — 3, а на четвертом — снова 1. Выбирая период (чтобы не было переполнения), но с другой стороны чтобы он был достаточно большим, можно учесть текст, в котором много одинаковых букв, но которые различаются по смыслу.

Спасибо за интересную статью. Думаю, что можно взять вместо букв n-граммы и использовать Locality Sensitive Hashing. Если его использовать то можно избежать поиска ближайших точек с помощью r-дерева, которое будет плохо работать с n-граммами из-за большой размерности. Про поиск похожих текстов с помощью Locality Sensitive Hashing хорошо рассказывает Ульман в курсе Mining Massive Datasets (вторая неделя) class.coursera.org/mmds-001. Еще есть мысль попробовать понизить размерность n-грамных представлений с помощью Principal Component Analysis.

Поправьте меня, если я говорю что-то не так.
А нельзя ли пробежаться по текстам, сложить ASCII коды символов, и сравнить их? Если в тексте содержится немного опечаток, то разница между суммами символов должна быть небольшой. А если тексты отличаются друг от друга, то и разница будет большая.