Tags: математика

wall

Morphing Match Chain

Изменяющиеся Цепи Совпадений?
Звучит загадочно. В общем, немного небесной красоты, высеченной в коде. Этим зимним вечером...

Задачка

Для поиска совпадений архиватору типа LZ77 нужно что-то типа списков указателей на строки с одним и тем же префиксом в рамках окна. Размер окна, допустим, 216, минимальная длина совпадения, о которой стоит говорить -- три символа. Скорее всего какое-то простое решение уже пришло в голову, если нет -- подумайте пару минут.

Мне приходит очевидное: словарь, в качестве ключей трёхсимвольные строки, элементы -- списки с указателями. Такое, вродебырешение.

Первое от чего придётся отказаться это словарь. Потому что очень большой перерасход по ресурсам. Комбинаций из трех символов 224, а актуальных в рамках окна не более 216, с учётом совпадений -- ещё в два-четыре-десять раз меньше. Как эффективно удалять из словаря просроченные ключи понятно не очень, а значит они там будут копиться вместе с просроченными списками и оценок по памяти не удаётся дать никаких (можно в принципе завести для каждого ключа счётчик ссылок; по памяти, сложности и скорости это будет не очень решение, но хотя бы оценку можно будет дать).

Поэтому не словарь а хеш, пусть с коллизиями, но зато обозримого размера. Что-то около размера окна должно хватить с запасом, может быть эксперименты покажут, что можно ещё раза в два уменьшить. Ну, а списки...

Цепочка хешей (Hash Chain)

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

Система состоит из двух частей:
  • хеш-таблица hash по префиксу возвращает самое свежее вхождение. В виде смещения от начала или в С просто адрес (который в сущности тоже смещение)

  • массив смещений-или-указателей chains размером с окно, в котором нужно искать совпадение

Дальше проще показать, как происходит поиск (chains будет массивом указателей):

window_size = 64 * 1024;                // размер окна, любое число; совпадает с размером chains  
const char* next = ...;                 // начало новых данных

ptr = GET_HASH(hash, next);             // внутри макроса GET_HASH вычисляется хеш по первым символам

while (ptr && (ptr > next - window_size)) {
    ... проверка совпадения next и ptr, запоминание лучшего варианта...
    ptr = chains[(long)ptr % window_size];   // получить следующее совпадение; обычно, конечно, не %, а & по маске
}

То есть:
  • chains используется как кольцевой буфер, хранящий информацию о window_size последовательных элементов

  • в элементе chains[(long)ptr % window_size] хранится указатель на следующее (если в хронологическом порядке, то предыдущее) совпадение

  • для каждого указателя в пределах окна существует ровно один свой элемент chains, значит для каждой позиции можно задать свою "предыдущую". Они не будут смешиваться, а "предыдущие" для слишком старых позиций автоматически заменяются новыми

А обновление, соответственно, как-то так:

ptr = GET_HASH(hash, next);              // получить старую голову списка
chains[(long)next % window_size] = ptr;  // сохранить её как следующий элемент для новой головы
GET_HASH(hash, next) = next;             // сохранить новую голову

Удивительно красивая схема, не уверен, что мне хватило бы смелости такое придумать. Тут нужен какой-то опыт, которого у меня совсем нет.

MMC

Переходим от красоты к прозе. У этой схемы есть один существенный недостаток -- она немного слишком простая. Если окно большое, то даже если у нас хороший хеш, который почти не даёт коллизий, список совпадений может получиться очень длинным, просто потому что действительно много совпадений. Есть два простых варианта: можно стиснув зубы идти до конца, либо можно пожертвовать степенью сжатия, и не ходить в глубину дальше чем на какую-то константу (этот вариант предложен в спецификации DEFLATE). Либо можно отказаться от цепочки хешей и использовать что-то совсем другое -- например бинарное дерево. Получив выигрыш в поиске, но сильно проиграв в сложности модификации (а значит и времени на модификацию). Это всё давно известные варианты, примерно с начала 90-х.

Morphing Match Chain это попытка вернуть в прозу красоту, совместить плюсы дерева и простоту модификации цепочки хешей, придумана вот только что, в конце 2010-го.

Yann Collet обратил внимание на следующее: цепочка составлена из совпадений по первым 3-4 символам (в разных архиваторах либо так либо так). Но если мы уже нашли совпадение в 5 или 6 символов, то более короткие совпадения нам больше не интересны. Поэтому было бы круто пропускать все более короткие и дальше просматривать только то что нужно.

Вторая мысль, видимо слишком очевидная, чтобы упоминать её явно: если с какой-то строкой не получилось совпадения больше чем на 3 (4) символа, то строки, начинающиеся так же тоже уже не интересны.

Итого, вместо списка типа:

abcDX.. --> abcRT.. --> abc12.. --> abcDY.. --> abcRN.. --> abcDY.. --> abc34..

хочется иметь что-то такое:
                                          ----------------> abcDY..
                                        /
     -----------------------------> abcDY..
    /
abcDX.. --> abcRT.. --> abc12.. --------------------------------------> abc34..
               \
                ------------------------------> abcRN..

То есть, есть основной ствол, для элементов которого общим является только фиксированный префикс, и от него отделяются всё более и более специализированные ветки. Поиск начинается с корня, и постепенно уходит по веткам дальше и дальше. По своей идее это практически суффиксное дерево, отличие только в том, что его удалось скрестить с подходом цепочки хешей и этим обеспечить очень простое и быстрое обновление.

Предлагаемая реализация:
  • массив chains содержит не указатели, а структуры из двух указателей: next и up. next это следующее совпадение на том же уровне, а up это переход на уровень выше. Каждый из них может быть пустым. Указатели такие же как в цепочке хешей, т.е. указатели на данные, одновременно используемые как индексы.

  • когда дерево полностью построено, поиск выглядит так: двигаемся от корня вперёд, пока не найдём совпадение большее минимального. С этого места пытаемся уйти вверх, если дороги вверх нет, то всё, ничего лучшего дальше нету (т.к. дерево построено). Если есть, то переходим на уровень выше и дальше аналогично.

  • для позиций, попавших внутрь совпадения соответствующие новые элементы просто добавляются в корень дерева, так что next элемента указывает на старый корень, никакой перестройки дерева не происходит. То есть почти в точности тот же код, что и для hash chain. После таких добавлений дерево оказывается не до конца построенным. Это может выглядеть как-то так:
                                              ----------------> abcDY.. 
                                            /
    abcDX.. --> abcRT.. --> abc12.. --> abcDY.. --> abcRN.. --------------> abc34..

  • поскольку это единственный фактор, нарушающий структуру дерева, можно заметить, что, хотя структура и нарушена, если двигаясь по основному стволу добраться до первой подходящей ветки, то дальше ей можно доверять (если она полностью правильно структурирована)

  • восстановление структуры дерева происходит при поиске совпадения и (в относительно простом варианте) только для совпадающих.

Collapse )

Вот такая штука.
Это, конечно, уже слишком сложно для сакуры, но всё же очень изящное решение хорошей проблемы, так что вполне икебана. MMC используется в lz4HC.
wall

Последний пример: lz4

Про lzo писать не стоило. Нужно было два примера, один хорошо сжимающий, второй быстрый. DEFLATE -- единственный естественный кандидат на первый, а на второй надо было брать lz4. Он проще и стройнее lzo, да к тому же ещё и быстрее. И вроде бы уже популярнее, хотя появился совсем недавно -- в 2011-м. И есть не только код (с комментариями!), но и текстовое описание! Я бы, конечно, так и сделал. Но о том, насколько переусложнён lzo я не знал, пока с ним не разобрался, а когда разобрался, было уже жалко выбрасывать :)

С другой стороны, вполне вероятно, что Yann Collet (автор lz4) смотрел на lzo и восклицал: о сумрачный германский гений! ну зачем же так сложно-то?!

Так что будет много похожего, но гораздо проще и понятнее.

Формат блока

Описан автором в блоге (такая современная замена RFC). Помните байку Дейкстры про туалеты в вагонах (рус.)? Ну вот. Блок состоит из последовательности пакетов (автор называет их "sequence"), каждый из которых объединяет в себе строку литералов (возможно пустую) и совпадение (всегда непустое).

Первый байт пакета ("token") состоит из двух 4-битовых полей: старшие четыре бита относятся к длине строки литералов, младшие -- к длине совпадения.

Количество литералов определяется следующим образом:
количество = (токен >> 4) & 0x0f      // старшие 4 бита
если количество == 0xf:               // предположительно не влезло
    ду:
        количество += следующий_байт
    пока следующий_байт == 255        // предположительно, опять не влезло
Если получилось 0, значит литералов нет. Если не 0, то сразу после этого идёт строка литералов.

Потом двухбайтное смещение в little endian, на котором не стали экономить единичку -- смещение 0 невалидно, корректные смещения начинаются с 1 и означают сами себя.

И наконец, если длина совпадения не влезает в 4 бита, дополнительные байты длины. Алгоритм тот же, что и у количества литералов, с той поправкой, что минимальная длина совпадения -- 4.

Итого, формат пакета:
  • первый байт -- токен. Разбивается на два поля по 4 бита. Старшие 4 относятся к длине строки литералов, младшие к длине совпадения.

  • [если старшие четыре бита токена -- 0xf] дополнительные байты для длины строки литералов

  • [если старшие четыре бита токена не 0] литералы, столько сколько получилось

  • два байта смещения, little endian

  • [если четыре младших бита токена -- 0xf] дополнительные байты длины совпадения

Ээ, гм, собственно почти всё. Последняя деталь -- нужно как-то заканчивать блок. Формат не предполагает специального признака конца блока и при декодировании полагается на то, что вовремя кончится строка (т.е. что вызывающий код знает какой длины сжатые данные), при этом последний пакет:
  • может не содержать совпадения, т.е. кончаться сразу после литералов

  • более того, по стандарту должен не содержать совпадения: последние пять байт должны быть литералами (для совместимости с декодером, который настолько быстр, что не проверяет границы буферов)

  • и ещё одно правило -- совпадения не должны начинаться слишком близко к концу строки, не ближе чем 12 символов (для того же)
Вот теперь совсем всё. Декодер помещается на одну страничку:

Collapse )

Прикольно, правда, что формат настоящего, не игрушечного архиватора может быть настолько простым? Можно даже без примера в этот раз.
При тестировании со стандартным питоновским пакетом нужно учесть, что при архивации он добавляет в начало четыре байта с размером декодированных данных.

Формат потока

Совсем недавно, уже в этом году, был предложен стандартный формат для потока данных и API для него в библиотеке.

Описание формата: http://fastcompression.blogspot.fr/2013/04/lz4-streaming-format-final.html
И рассуждения об API в трёх частях (о том, чем руководствовался, без кода или даже прототипов функций): 1, 2, 3.

Всё довольно прозрачно, ничего особенно неожиданного. Не знаю, используется ли уже где-либо. python-lz4 ничего такого пока не поддерживает.

Кодер

Есть две версии кодера: быстрая и хорошая (lz4HC). Быстрая сделана как все быстрые, по заветам LZRW1: хеш-таблица, проверка единственного совпадения, побежали дальше. А вот хорошая сделана гораздо интереснее, про это будет следующий пост.

Доб.: А вот и он: http://fat-crocodile.livejournal.com/196593.html



Всё, ура. Про простые LZ-архиваторы я написал всё что хотел, теперь можно заняться чем-то совсем другим.
wall

Пример: lzo1x

Нельзя просто так взять и написать lzo!

Продолжаем тему LZ-алгоритмов и LZ-архиваторов. Совсем другой архиватор.

LZO это библиотека алгоритмов архивирования, написанных с прицелом на максимальную скорость работы. Название расшифровывается как Lempel-Ziv-Oberhumer; Markus Franz Xaver Oberhumer -- автор LZO. Алгоритмов я насчитал 39, форматов в которые они сохраняю данные – 9 (я считал по экспортируемым функциям; вот здесь в середине есть табличка, правда там только 37 алгоритмов). И всё это не описано нигде кроме исходного кода, о котором автор честно пишет:

Be warned: the main source code in the 'src' directory is a real pain to understand as I've experimented with hundreds of slightly different versions. It contains many #if and some gotos, and is *completely optimized for speed* and not for readability. Code sharing of the different algorithms is implemented by stressing the preprocessor - this can be really confusing. Lots of marcos and assertions don't make things better.

Подтверждаю, всё правда, но всё-таки не ужас-ужас-ужас, в чём-то разобраться можно. А из алгоритмов автор советует пользоваться lzo1x-1 либо lzo1x-999, второй сжимает несколько медленнее, но лучше.

Чтобы не возиться с C, можно использовать обёртку python-lzo, она реализована следующим образом.

Collapse )
Т.е. как раз эти два алгоритма.

Декомпрессор

Расковыряв код декомпрессора, можно установить формат с его точки зрения (она несколько более общая, т.е. декомпрессор умеет разжимать больше, чем компрессор сжимать). Помимо того, что это LZ77, идея следующая:
  • сжатый поток состоит из блоков открытого текста и совпадений

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

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

  • признак конца данных это тоже такое специальное совпадение

  • интересная идея -- после каждого совпадения может быть хвост до трёх байт открытого текста, не нуждающихся в отдельном блоке.

  • после каждого блока открытого текста обязательно идёт совпадение, либо одно из обычных, либо специальное трехсимвольное совпадение

И ещё две оптимизации, влияющие на кодирование:
  • поскольку первым блоком совпадение быть не может (это вариант без предустановленного словаря, не с чем пока совпадать), длина первого блока может (но не обязана) кодироваться немного иначе, чем обычно

  • если у совпадения есть хвост, т.е. если после него идёт 1-3 байта открытого текста, то дальше не может быть блок открытого текста, только следующее совпадение.

Немножко запутано. Дальше будет хуже.

Collapse )

Collapse )

Collapse )

Код

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

Collapse )
wall

Пример: DEFLATE

Теория и обзор это здорово, но интересно же посмотреть, как устроен настоящий архиватор. DEFLATE это самая известная в мире реализация идеи LZ77+Huffman. Это zlib, gzip, он же внутри PNG, его использует SSL и http тоже обычно жмётся им же, и ещё много где. В общем, популярная штука.

Кажется, название формата-и-алгоритма правильно писать всеми большими буквами, но мне очень не понравилось, как это выглядит в тексте, поэтому дальше маленькими -- deflate.

Напоминаю общую идея алгоритмов этого класса: данные проходят через LZ77, потом результат кодируется Хаффманом. Формат, в котором сохраняются сжатые данные, и некоторые части рекомендуемого алгоритма, описаны в RFC 1951.

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

Первый этап, LZ77

Максимальное смещение -- 215, максимальная длина совпадения -- 258 байт.
На выходе последовательность из литералов и пар <длина, смещение>, смещения считаются не от начала окна, а от текущего символа. Совпадения короче трёх символов не рассматриваются. Изначально в окне нет ничего и генерируемое смещение не должно выходить за пределы данных.

Это была обязательная часть. Рекомендательная начинается словами (это раздел 4, "Compression algorithm details"):

... since many variations of LZ77 are patented, it is strongly recommended that the implementor of a compressor follow the general algorithm presented here, which is known not to be patented per se. The material in this section is not part of the definition of the specification per se, and a compressor need not follow it in order to be compliant.

Подчеркнул последнее предложение я. И дальше описывается следующее:
  • При сжатии для поиска совпадений используется хеш-таблица, содержащая списки вхождений.

  • Аргумент хеш-функции -- следующие три символа.

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

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

  • Вместо этого контролируется длина списка, если он стал слишком длинным, конец обрубается (чтобы поиск не превращался в линейный; вероятно имеется ввиду, что граница, по которой обрубается и граница, при пересечении которой обрубается -- это две разные границы).

  • Предлагается использовать "lazy matching". Найдя совпадение длины N, попробовать найти совпадение большей длины, начинающееся со следующего символа. Если получается, то вместо исходного совпадения на выходе литерал для текущего символа и более длинное найдённое. Если N уже и так неплохое, и нам не критично важна степень сжатия, эту логику можно отключать.

  • Если прежде всего важна скорость, хеш-таблица обновляется только тогда, когда найдено короткое совпадение или его не удалось найти совсем.

Когда обновляется хеш-таблица в обычной ситуации не написано: то ли на каждом шаге, то ли на каждый символ (насколько я понял, zlib в стандартном режиме обновляет на каждый символ).
Но в общем всё довольно просто и понятно.

Collapse )

Пример

Вот такие данные:

15 8d 51 0a c0 20 0c 43 ff 3d 45 ae 56 67 dd 8a 5d 0b d5 21 de 7e 0a f9 08 21 2f c9 4a 57 cb 12 05 5d ec de 82 18 c6 c3 28 4c 05 5e 61 72 3f 23 0d 6a 7c e2 ce c8 e1 8d 0d 73 77 3b c8 0a 94 29 36 e3 a8 ba 12 a9 62 f9 17 50 a9 9c b6 c3 e4 60 b8 e9 c2 24 19 e7 a1 7a ec 2d e9 78 fd 65 1b 07 a5 90 ce e9 07

Collapse )

Чтоб два раза не вставать

В природе deflate встречается как составная часть различных форматов и протоколов. Самые простые, не вносящие каких-то дополнительных смыслов это zlib и gzip.

Collapse )
wall

почему LZ77 лучше чем LZ78

Вот например пишут:

LZ77 и LZSS обладают следующими очевидными недостатками:

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

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

В 1978 г. авторами LZ77 был разработан алгоритм LZ78, лишенный названных недостатков.

Однако наблюдаемая реальность намекает нам, что что-то тут не чисто: алгоритмы на основе LZ78 гораздо менее распространены. Хотя в преимущества ещё можно смело добавить линейную скорость работы. Наверное частично повлияли проблемы с патентами на LZW, но дело всё же не в них.

Collapse )
wall

Алгоритмы LZ* и оптимизации

LZ это Lempel-Ziv, два израильских математика Abraham Lempel и Jacob Ziv, на высказанной ими идее основана примерно половина современных алгоритмов архивирования. В двух словах идея формулируется так: помни историю! То есть, если последовательность символов нам уже встречалась, то не будем повторяться, а сошлёмся на ту.

Несколько подробнее, но не опускаясь до уровня битов...
Статьи, на которые нет ссылок я брал с соответствующего раздела сайта comperssion.ru

Алгоритмы

LZ77
Оригинальная статья Ziv, Lempel "A Universal Algorithm for Sequential Data Compression", IEEE Transactions on Information Theory, vol. 23, no. 3, may 1977. Статья написана настоящими математиками! На высоком уровне абстракции, с большим количеством формул и доказательством каких-то оценок. Понять что-либо непросто. А доказательства я даже и не пытался читать.
Есть разные версии алгоритма, я буду следовать статье.


Collapse )

LZ78
Ziv, Lempel "Compression of Individual Sequences via Variable-Rate Coding", IEEE Transactions on Information Theory, vol. 24, no. 5, september 1978. Но эту статью совсем не надо читать. Алгоритм там действительно описан, но появляется он несколько неожиданно: в качестве конструктивного доказательства сформулированной теоремы о существовании некоторого алгоритма. Алгоритм простой, а уже даже формулировка теоремы сложная и вдаваться в её подробности не возникает ну ни какого желания.

Collapse )

LZW, 1984
"W" от Welch. Статья Terry A. Welch, "A Technique for High-Performance Data Compression", IEEE Computer, vol.17, N6, June 1984. Это статья написана инженером, формул тут нет совсем, зато есть картинки и псевдокод. Но сам алгоритм по прежнему абзаца на два, так что картинки не про него и вообще основное содержание статьи это рассуждения о том, как можно было бы реализовать прозрачную для пользователя архивацию данных и какие при этом возникают проблемы. Рассуждения разумные.

Collapse )

LZRW1, 1991
Ross N. Williams, "An Extremly Fast ZIV-Lempel Data Compression Algorithm", 1991. Наконец полноценная статья, посвященная именно алгоритму и сравнению скорости/качества работы его реализации с популярными архиваторами.
также см. http://www.ross.net/compression/lzrw1.html


Collapse )

Оптимизации

Допустим, реализуем LZ77. При архивации он выплёвывает тройки. Первый вопрос, который встаёт -- как их кодировать. И тут в голову почти сразу же приходят две мысли, первая и вторая.

Collapse )

Collapse )

Collapse )



Вроде бы это всё, что можно выжать из идеи LZ в чистом виде. Более интересные алгоритмы добавляют что-то ещё.
wall

Хаффман с ограниченной разрядностью

Все знаю про кодирование Хаффманом. Оказывается есть интересные вариации.

На всякий случай напомню о чём это. У нас есть некий алфавит и написанный им текст, и мы хотим записать этот текст в двоичном виде, причём очень простым способом:
  • сопоставить каждой букве алфавита двоичный код

  • записать текст, используя коды вместо букв

При этом
  • длины кодов различных букв могут отличаться

  • хочется, чтобы декодер, читая получившуюся бинарную строку от начала к концу мог однозначно определить границы кодов, не используя какие-то сложные правила. Требуем чтобы ни один код не был префиксом другого. Такой код называется префиксным.

    То есть набор кодов (0, 10, 110, 111) подходит, например строку 00101000100111110 можно однозначно разбить на 0-0-10-10-0-0-10-0-111-110. А (0, 10, 101, 111) не подходит: 1010 это 101-0 или 10-10?
    Это довольно слабое ограничение, например любой код фиксированной длины очевидно префиксный и т.п., отсекаются только довольно странные вещи

  • нужно чтобы бинарная строка была бы покороче

Ну и в общем понятно, что для того чтобы результат получился покороче, символам, которые встречаются почаще стоит дать коды покороче, а тем что пореже -- можно подлиннее. Это и есть основная мысль. Алгоритм построения оптимального (с точки зрения длины получающейся строки) кода, удовлетворяющего этим условиям, придумал David A. Huffman, статья опубликована в 1952-м.

Вот, кстати, интересно: учёный, дожил до 1999, а известен всем только как автор четырёхстраничной статьи написанной в аспирантуре, с алгоритмом, который можно объяснить школьнику. И даже в 1998, а потом в 1999 его ещё два раза наградили за неё, напоследок. Наверное ему было немного обидно от всего этого. Хотя вики и пишет, что у него были значительные достижения в других областях, видимо они были не настолько значительными, чтобы описывать в вики сами эти достижения. Просто хоть не становись знаменитым.

Подчёркиваю -- код строится для данного текста, с конкретным набором частот встречающихся букв, и оптимален он только для него. Для другого текста нужен другой код. Помимо прочего это означает, что вместе с текстом нужно сохранять словарь, иначе восстановить текст будет затруднительно.

Классический алгоритм Хаффмана несложный и широко известный, код действительно оптимальный. Но коды редких символов могут получаться довольно длинными, иногда это неудобно. И оказывается, что попытка наложить ограничение на максимальную длину значительно всё усложняет.

Теперь какие-то чуть менее всем известные вещи.

Collapse )

И собственно к поставленной задаче. То что написано ниже это пересказ в свободной форме следующей статьи:

LAWRENCE L. LARMORE, DANIEL S. HIRSCHBERG
"A Fast Algorithm for Optimal Length-Limited Huffman Codes"
Journal of the Association for Computing Machinery, Vol. 37, No. 3, July 1990

Статья гуглится.

Collapse )
wall

Хи-квадрат

Граждане математики, люди добрые, поможите кто чем может, не оставьте в беде.

Сестра попросила объяснить, можно ли использовать хи-квадрат для проверки гипотезы о законе зависимости случайных величин, и если да то как. Я поскольку про это дело помнил только названия полез читать... Чтобы как-то систематизировать, в процессе полез писать. А дойдя до конца понял, что ответ на заданный вопрос я так и не знаю :(

Ниже написавшийся текст, в конце нерешённая проблема. В процессе я тоже понял не то чтобы всё, но кажется в целом получилось более-менее внятно. Где не понял так и написал.

О чем вообще речь
Допустим у нас есть случайная величина x. Мы её n раз измерили и получили x1...xn. Построили гистограмму, посмотрели на график и воскликнули -- да это же Гаусс, родной! Глазами вижу. Но глаза к делу не пришьешь, нужно как-то измерить.

Гаусс тут просто для примера, метод работает с любыми распределениями.

Collapse )

Collapse )

Проверка гипотезы о законе зависимости
Ради чего всё затевалось. Пусть всё как в предыдущем пункте, но у нас есть гипотеза о том, как y зависит от x. То есть, фактически, мы предполагаем, что знаем условную вероятность P(y в Yj | x в Xi) для каждой клеточки. Тогда:

считаем P(x в Xi)
Tij = n * P(x в Xi) * P(y в Yj | x в Xi)

Остались степени свободы. И вот тут у меня затор. Есть две гипотезы.
  • давайте считать параметры.

    • В каждом столбце у нас r-1 условная вероятность, итого k*(r-1)

    • плюс k-1 вероятность для P(x в Xi)

    • плюс фиксированное количество испытаний

    итого k*(r-1) + k-1 + 1 = k*r -- ни одной степени свободы не оставили. Приехали, хи-квадрат применять нельзя.

  • а почему собственно мы считаем условные вероятности значимыми параметрами, мы же брали их не из данных, а из головы. В нормальном распределении участвуют числа e и пи, но мы же их за параметры не считаем. С другой стороны, если вопрос в источнике параметров, то значит при честном угадывании E и D, а не подсчёте, в самом первом примере нужно было бы иначе считать количество степеней свободы? А если я случайно угадал точное число?

Upd: Задам вопрос иначе, менее общо. Цель всего предприятия следующая: есть две бинарных величины и табличка 2*2 с результатами измерений. Стандартный метод позволяет проверить гипотезу о зависимости-независимости, это понятно как. А теперь у нас есть рядом второй набор из двух бинарных величин, со своей табличкой. И мы хотим понять, правда ли, что оба набора величин распределены по одному закону. Можно ли это сделать и если да, то как?

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

Upd2: Collapse )

Upd3: fregimus нашёл ссылку http://stats.stackexchange.com/a/17148 в которой показана глубина проблемы. Кажется, тут на пальцах не получается :(
wall

Ж

Год назад писал про R-деревья. Там, помимо пересказа общеизвестного, содержалось оригинальное исследование, как сказали бы в википедии. Предположение о том, что R-деревья можно обобщить на произвольное метрическое пространство, не обязательно чтобы была система координат. В качестве примера там приводились слова с расстоянием Левенштейна в качестве метрики.

Ну, в общем, всё оказалось несколько сложнее. Не выходит что-то каменный цветок.

Есть такая штука -- индекс Жаккарда (Jaccard). Это мера похожести двух конечных множеств, считается так:



Т.е. количество общих элементов поделить на количество элементов в них всего. Для одного и того же множества индекс равен 1, для не пересекающихся 0, для остальных где-то между. Для чистоты нужно ещё дооопределить .

Можно, кстати, перетащить это на измеримые множества точек прямой/плоскости/и т.п., если брать не мощность, а меру. Уж не знаю, будет ли какой-нибудь интересный смысл.

Интересно, что d(A,B) = 1 - J(A, B) это честное расстояние.
  • очевидно, что d(a,a) = 0

  • очевидно, что d(a, b) > 0, если a != b

  • очевидно, что d(a, b) = d(b, a)

  • выполняется правило треугольника, хотя это и не очевидно. Можно доказать, выписав все конституенты для трёх множеств, всё умножить, сложить и вычесть. После этого останутся только положительные члены. Несложно, но ужасно муторно если делать руками, зато довольно легко автоматизируется. Более вменяемого доказательства я не знаю :(

Посмотрим, что за пространство у нас получилось. Напомню, точки -- элементы пространства -- конечные множества.
  • максимальное возможное расстояние -- 1

  • точка "пустое множество" находится от всех других точек на расстоянии 1

  • рассмотрим одноэлементное множество {a}. Ближе всего к нему, на расстоянии 1/2 лежат множества вида {a, b} для любых возможных b. Подальше, на расстоянии 2/3 -- все множества вида {a, b, c}. Потом 3/4 и т.п.

В общем, занятное пространство.

Collapse )

Но это только присказка. С двумя точками ситуация понятная. Сказка начинается, когда у нас n точек и нужно построить вокруг них не слишком большой шарик. А зачем нам это? А это шаг в построении R-дерева: разбиваем разросшийся узел и строим из него два маленьких. Побившись полночи головой об пол я так и не придумал, как найти шарику центр. Ну то есть можно добавляя по одному перемещать центр, стараясь угодить новому пришедшему, но там каждый раз случайный выбор -- что именно из него выбрать, чтобы пододвинуть к нему центр, с точки зрения метрики разницы нет. И что-то никаких оценок, почему такие выборы не будут слишком плохими слишком часто не придумывается.
wall

(no subject)

Решил задачку, горжусь :)

Там сначала идет недоделанное решение, работающее не во всех случаях и вопрос "что делать?", а потом upd и другое решение, более правильное. Что делать никто ответить не успел.

Если вы не знаете, что такое ординал, ходить по ссылке смысла нет...