Согласен, на эти грабли тоже можно наступить. Вопрос к Илье: можешь ли сообщить свою статистику по одно-, двух-, трех- и т.д.-словным запросам?
Увы, не вижу, как можно улучшить этот алгоритм принципиально, т.е. сделать лучше, чем O(суммы позиций). Мелкие улучшизмы, конечно, возможны: оптимизировать работу с редкими позициями, например.
Если я правильно понял вопрос (поиска близких позиций n объектов), то есть простое решение методом последовательного спуска.
Заводится массив из n первых позиций всех объектов. Находим объект с минимальной позицией, переводим его к следующей позиции. Снова находим минимум. Повторяем. Все.
Таким образом можно решить все задачи со взаимным положением внутри какого-то интервала.
Насколько я понял, из-за "кракозябрицы". Хотя распознать во многих случаях неправильной кодировку - задача решенная, и довольно давно, если правильно помню, то самим Марковым (вероятности дву- и триграмм). Однако, может, у Des, были дополнительные соображения.
Иначе говоря, нужно определять словоизменение и словообразование, при этом не используя словаря. Вероятно, словари суффиксов-приставок-окончаний также использовать нельзя. Тогда задача в данной постановке сводится к пустяку: написать алгоритм преобразования слов естественного языка. Тогда ключевым словом становится - "не обязательно точный". В этом случае годится практически любой алгоритм сравнения по буквам, например, сравнивающий последовательность N букв в слове (n-граммы). В случае n=4 этот алгоритм прекрасно сведет бокра и бокренка. Формально все в порядке, конечно, если не обращать внимания на вероятность ошибок :)
Простите, но я просил чуть подробнее. Неужто такой секрет? К тому же вы не находите в приведенных совете и ответе некоторого противоречия?
Повторюсь, что для различных задач сжатия эффективного универсального алгоритма, увы, нет. Данная задача принципиально неуниверсальна. Ссылок вам дали много, есть даже кусочек алгоритма, так что выбирайте, что нужно. Что до универсальности, то такое пожелание напоминает желание найти универсальный клей, поскольку нет времени разбираться в типах склеиваемых материалов. Что бы вы ни взяли, хорошо и прочно не будет в большинстве случаев.
Простите, можно чуть подробнее, как вы оценили качество работы кластеризации уважаемого мной Сергея Шумского. Насколько я понял, у него на сайте приведен только один пример кластеризации ("советы Путину"). Причем этот пример - уже готовая замороженная структура, а не живая программа (к тому же необученная заранее на похожих рубриках), где можно поиграться пусть даже с фиксированным и хорошо разделяющимся массивом.
Думается, в данном случае подобрать такой универсальный алгоритм будет довольно затруднительно. Мы сами используем несколько алгоритмов для таких задач, оптимизированных по постановке. Например, кроме сжатия критична скорость разворота, как для случая инвертированных списков, или возможность быстрого пополнения (причем есть нюансы, куда пополнять), или возможность быстрого доступа в произвольное место структуры и т.д. Кроме того, важна внутренняя структура сжимаемых данных, например, упорядоченность.
В конце концов, может оказаться, что не так важно даже однозначное восстановление, например, JPEG. На этом можно очень много выиграть и по сжатию, и по скорости.
Идея неплохая. Поиск по тезаурусу давно уже сделан и хорошо работает, например, см. УИС Россия Доброва-Лукашевич.
