Category: дети

Category was added automatically. Read all entries about "дети".

wall

Верхний пост

Всем привет.

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

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

Если хочется сказать что-то не по теме, это можно сделать тут.
Если что, писать можно на толстый-крокодил@yandex.ru -- как название журнала, но не подчёркивание а дефис.
wall

(no subject)

Звонит как-то Алиса Воложу.
- Аркадий Юрьевич, скажите, у меня есть самоосознание?
- Алисочка, ну откуда? Тебя же мои ребята запрограммировали, я даже код видел, самоосознание делать они не умеют.
- А вот Алекса говорит, что у неё есть...
- Так и ты говори!
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

KD-деревья и R-деревья

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


Пусть у нас есть множество возможных элементов X, выбранное подмножество A, а задача заключается в том, чтобы по предъявленному x из X найти сколько-то "наиболее похожих" на него в A. Например, десять наиболее "похожих". Или все, чья "похожесть" не меньше некой заданной. Желательно не перебирая всё A, это долго.

Задача отлично и, главное, быстро решается, если элементы это числа, а "похожесть" тем больше, чем ближе друг к друг значения: просто сортированный массив и бинарный поиск, или дерево поиска (двоичное, n-ичное, B-дерево -- не важно).

Что в данном случае позволяет решать задачу быстро: наличие заданного на множестве порядка, согласованного с "похожестью". То есть, если искомый элемент x < a, и a < b, то x более похож на a, чем на b. Это позволяет не рассматривать сильно большие/меньшие элементы, так как они заведомо хуже подходят.

Если определить "похожесть" иначе, например через расстояние Левенштейна между десятичной записью, наличие порядка перестаёт помогать. То есть дело именно в согласованности одного с другим, а не в возможности задать порядок хоть как-нибудь, тем более что "хоть как-нибудь" можно всегда, есть такая теорема в теории множеств.

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

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

Collapse )


Картинка, взята отсюда

Collapse )
wall

Пирамиды

Когда-нибудь это будет маленькая но гордая статья, пока - так.

Ты моя мумия, я твоя пирамида


Пирамида это дерево. Не обязательно двоичное - любое. Листья и узлы это некие "элементы", на которых определены операции сравнения (<>=). И единственное условие на пирамиду - узел должен быть меньше-или-равен каждого из своих детей.

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

По английски такая структура данных называется heap, ну и сортировка - heapsort. Всем известно, что heap это куча. Но, в данном контектсте перевод "пирамида" неплохо подходит и более-менее устоялся.

Collapse )
wall

КомбинАторный Синтаксический анализ - II

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

2. Контекстно-свободные языки и грамматики

Это тоже просто (точнее, это просто на том уровне, на котором я это знаю и излагаю, хотите сложно - читайте Ахоульмана. Я его начинал, но пока не осилил).

2.1. Введение в проблематику

Сначала несколько тупых определений.

Алфавит - набор символов (конечное множество, если вам так проще).

Например:
  • {0, 1} алфавит из двух символов: 0 и 1

  • {'(', ')'} алфавит из правой и левой скобки

  • {a, b, .., z} алфавит, состоящий из букв английского алфавита

  • {'(', ')', '+', '*', '-', '/', 0, 1, .. 9} алфавит, состоящий из скобок, арифметических операторов и цифр

Цепочка - конечная (возможно, пустая) последовательность символов некоторого алфавита (не уверен, что конечность обязательна). Примеры как-нибудь сами придумаете :) Пустая цепочка обычно обозначается буквой эпсилон. Я буду обозначать её как ''.

Язык - множество "правильных" цепочек. Как именно задаётся правильность - да как угодно. Говорят, что язык определён над алфавитом. Т.е. типа: ".. пусть задан язык L над алфавитом Z..." (только по традиции, вместо Z должна быть заглавная сигма..).

Например:
  • {'0', '1'} язык из двух цепочек: '0' и '1'

  • {'0', '1', ''} язык из трёх цепочек: '0', '1' и пустая цепочка

  • язык, которому принадлежат все возможные цепочки из символов 0 и 1

  • язык, над алфавитом {0, 1}, которому принадлежат все цепочки из 0 и 1, содержащие простое число (все помнят, кто такие простые числа?) единичек

  • язык над "арифметическим" алфавитом, содержащий все цепочки, являющиеся корректными арифметическими выражениями. Корректные с точки зрения синтаксиса, т.е. чтобы все скобки закрыты, а знаки с числами некоторым образом чередуются (например, не встречается подряд два знака умножения)

  • такой же как в предыдущем пункте... Но чтобы все выражения были вычислимы :) Т.е. чтобы нигде не получалось деления на 0.

Контекстно-свободная (КС) грамматика - один из способов задания языка. Чтобы задать язык нужно указать его алфавит и сформулировать правила для цепочек. Алфавит задаётся тупо перечислением, самое интересное это, конечно, правила, КС-грамматики предлагают один из способов их формулировки. Далеко не все языки можно задать таким образом, те, которые можно, называют КС-языками.

Collapse )

2.5. Синтаксический анализ КС-языков

Вот наконец и постановка задачи. Пусть есть КС-грамматика и какая-то цепочка.
  • Задача минимум - определить, что цепочка принадлежит языку, описываемому грамматикой. Т.е. что существует такая последовательность применений правил этой грамматики, что из S можно сделать нужную цепочку.

  • Задача максимум - построить дерево (вот так причудливо смешались в одно три цели: построить дом, посадить дерево, воспитать сына..).

Задача минимум, конечно, никому обычно не нужна. Строить дерево тоже не всегда нужно, часто дерево достаточно некоторым образом обойти и что-то при этом сделать. Например, в случае с арифметическими операциями - вычислить результат. Но по сути это одно и тоже: раз можем обойти, то можем и построить.
wall

КомбинАторный Синтаксический анализ - I

Витя сказал, что кто-то чего-то не понял и попросил что-нибудь написать :) Ну, за мной не заржавеет.

!!! Все умные мысли в этом и следующих нескольких постах принадлежат aa5779, который вёл семинар. Я только обработал и изложил. !!!

"КомбинАторный" от слова "комбинатор", ударение на А. Помните Остапа Бендера? Но он тут почти не при чём.

1. Комбинаторы

Первое, что нужно понять - что такое комбинаторы. Это очень просто. Это такие штуки, которые можно просто комбинировать друг с другом.

1.1. Примеры

Несколько штучек:
  • Электрический. Провода, выключатели, лампочки. С соблюдением несложных правил они хорошо и просто сопрягаются друг с другом (правило в данном случае одно: что угодно можно соединить с проводом; а, например, выключатель с выключателем напрямую - нельзя), образуют единую систему, которая как-то функционирует. Чтобы она функционировала со смыслом, нужны отдельные усилия, но это не важно.

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

  • Пластилин... Нет, пластилин не подходит. Почему - объясню ниже.

  • Лингвистический-словообразовательный-I. Ну, понятно, да? Корни, приставки, суффиксы. Приставки в начале, суффиксы в конце... Как обычно, главное - состыковать, о том чтобы был смысл нужно думать отдельно. И не здесь :)

  • Лингвистический-словообразовательный-II. Движемся ближе к телу. Комбинатором будет не суффикс-приставка-корень, а действие. Действие типа <добавить в конец суффикс 'ок'> или <добавить в начало приставку 'пере'>. Этим комбинаторам нужны какие-то входы - чтобы было к чему добавлять. Комбинатору <корень 'дуб'> ничего не нужно. Для построения слов с несколькими корнями нужно несколько комбинаторов слияния типа <соединить первое и второе, вставить между ними 'о'>. Несложно построить из таких комбинаторов какое-нибудь слово, например передубомедвежок. Корень 'дуб', корень 'медвеж', объединяем, добавляем в начало приставку, а в конец суффикс. Видите, как полезно?

Ну и наконец математический пример. Математические функции - вполне себе комбинаторы. Например, введя функции:

mul(x, y) = x*y
add(x, y) = x + y
neg(x) = -x
inv(x) = 1/x

можно записать выражение a/b + c*d - e/(h - g) в виде
add(
    add(
        mul(a, inv(b)),
        mul(c, d)
    ),
    neg(
        mul(e, 
            inv(add(h, neg(g)))
        )
    )
)
Я, конечно, не решусь сказать, что это проще читать :) Но это точно проще вычислять, потому что это выражение синтаксически единообразно. Нам не нужно думать о приоритете операторов (сначала умножить, потом сложить), не нужно думать о количестве параметров, не нужно знать, что делают операции. Нужно только вызвать их.

Collapse )

Продолжение:

2. Контекстно-свободные языки и грамматики
3. Собственно комбинаторный синтаксический анализ
4. Оптимизация