Mrrl

Не читал и не слышал о ней. В 91-м у меня были другие заботы — работа над диссертацией.

В случае, если нужно передать действительно произвольный код Хаффмана, то выиграть почти ничего нельзя. Код определяется N-элементным вектором m-битных чисел (с условием, что все элементы различны) — это буквы, отсортированные по кодам, и расстановкой скобок в выражении из N операндов — это двоичное дерево. Число векторов равно (2^m)!/(2^m-N)!, число деревьев — C(N,2*N)/(4*N-2). Если N заметно меньше, чем 2^m, то первое из этих чисел можно оценить как 2^(m*N), а второе — как 2^(2*N)/(4*N-2)/sqrt(pi*N). Общее число бит в их произведении — примерно m*N+2*N.
По мере приближения N к 2^m появляется возможность выиграть до 1.4*N бит (за счет того, что (2^m)!< (2^m)^(2^m).

Что-то не так в условии. 24-битных чисел всего 16*10^6, их никак не наберется 2^9.
И вопрос — нужно получить именно заданные коды Хаффмана, или достаточно, чтобы получились какие-нибудь эквивалентные по длине (а алгоритмы упаковки и распаковки сами договорятся, чтобы распакованные коды были именно теми, которые используются при упаковке основного сообщения)?

В случае, если векторов между потенциально видимыми кубиками не безумно много (например, если на карте много комнат, но в каждой комнате не очень много кубиков), то всю задачу можно решить быстрее, чем за O(n). Берем равномерную сетку, но помещаем в нее не координаты кубиков, а вектора между ними (номера двух кубиков и вектор). Скорее всего, даже хеширования не понадобится — будет плотно заполненный двумерный массив списков. Берем любой вектор между двумя видимыми кубиками, находим соответствующий ему список векторов между кубиками базы, и идем по нему. Для каждой пары из списка находим положение наблюдателя и выполняем шаги (6,7) из алгоритма DankoUA (т.е. сетка с кубиками нам тоже понадобится).

А, кстати, если известны и относительные координаты маяков, и направление север-юг, то все вообще просто. Для каждой пары «маяк из базы — видимый маяк» вычисляется наше положение для случая, если они соответствуют друг другу, после чего в полученном облаке из 100 точек определяется самый плотный 5-точечный кластер (за последнее время задача обсуждалась здесь по меньшей мере трижды).

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

1 (предобработка). Для каждой точки из базы определяем расстояния до остальных 19 точек, полученный вектор сортируем. Получаем 20 векторов LB[20][19].
2. Для видимых точек делаем то же самое — получаем 5 векторов отсортированных расстояний LS[5][4].
3. Для каждой пары «вектор из LB / вектор из LS» определяем меру того, насколько второй вектор является подмножеством первого — для каждого элемента второго вектора ищем ближайший элемент первого и находим максимум или сумму отклонений.
4. Для каждого вектора из LS берем ближайший (в смысле заданной в (3) меры) вектор из LB. Получили первую кандидатуру на соответствие точек. Проверяем, соответствуют ли друг другу расстояния, и если да — пытаемся найти преобразование системы координат. Если видимые точки с хорошей точностью совпали с базой, то нам повезло.
Если не повезло, то дальше есть два пути.
5a. Начинаем просматривать не наилучшие соответствия, а следующие за ними (какой-нибудь динамикой). В конце концов повезет — у нас всего 5 индексов для перебора.
5b. Выбираем вектор из LS, соответствие которого с вектором из LB было наиболее надежным в том смысле, что второе по качеству соответствие (того же вектора из LS но с другим вектором из LB) гораздо хуже. Говорим, что самое надежное соответствие — правильное, т.е. один кубик мы узнали. Корректируем меру соответствий, добавляя новый критерий — расстояния до найденного кубика должны совпадать. После чего снова выбираем наиболее надежное соответствие, и т.д. Скорее всего, повезет.
Если не повезло, придется повышать сложность — например, сравнивать не расстояния между парами точек, а форму треугольников. Но я надеюсь, что до этого не дойдет.

Я всегда беру Seagate, причем самый «толстый» на данный момент. Пока ни разу не подвели, а дискового пространства много не бывает (6 TB уже кончаются, придется рискнуть поставить трехтерабайтник вместо самого старого диска).
Рейдов не пользую. Самые важные и уникальные файлы стараюсь держать в двух местах, желательно, на разных континентах.

Можно сделать так. Если известна хотя бы одна пара соседних точек растра, на которых функция имеет разные знаки (например, f(x,y)>0, f(x+1,y)<0), то линия проходит межу ними. Можно взять один из квадратов, ограничивающих этот отрезок (например, (x,y)-(x+1,y)-(x+1,y+1)-(x,y+1) ), и, проверив знаки функции f(x+1,y+1) и f(x+1,y), узнать, какую вторую сторону квадрата пересечет график. Процесс продолжать, пока график не дойдет до границы области или не замкнется.
Для поиска стартовых точек можно взять значения в точках (Nx,Ny) при каком-нибудь N, и уже на этом растре искать соседние точки с разными знаками: график наверняка пройдет между ними. Маленькие компоненты при этом могут потеряться, но для их поиска пришлось бы использовать очень серьезные методы — например, решать систему f(x,y)=0, df(x,y)/dx=0 (ее решения дадут экстремальные точки всех компонент). Можно для этого применить метод Ньютона (тоже стартуя из всех точек (Nx,Ny)).

Непонятно, зачем вообще статистика поступления пакетов и время опыта. Достаточно того, что «линия связи состоит из 2 каналов… При поступлении сообщения каждый из каналов може бути занят с вероятностью 0.4. Если оба канала заняты, то информация теряется» Ясно, что как бы посылки не поступали, теряться будет в среднем 16%.

Метод наименьших квадратов. Если расстояние от искомой точки (x,y) до одной из известных (xi,yi) равно ri, то (x-xi)^2+(y-yi)^2-ri^2=0 (с точностью до шума). Строим f(x,y)=Sum(((x-xi)^2+(y-yi)^2-ri^2)^2) (это многочлен 4-й степени от двух переменных), и решаем систему уравнений {df/dx=0, df/dy=0} например, методом Ньютона. Но не факт, что корень будет единственным, так что надо пробовать много стартовых точек, и для каждого результата проверять значение f.

Нет, там берется центр масс (xc,yc), потом считаются коэффициенты a11=sum(xi-xc)^2, a12=a21=sum((xi-xc)*(yi-yc)), a22=sum((yi-yc)^2), где (xi,yi) — координаты всех точек. Дальше у матрицы ((a11 a12) (a21 a22)) надо взять собственные векторы — они и дадут ориентацию объекта. Или не дадут… Отделить бы как-нибудь внутренние точки от внешних… Надо много экспериментировать, задача непростая и очень эвристическая.

Я бы искал ось симметрии. Но пока не очень представляю, как именно. Например, брать все пары точек, строить для них серединный перпендикуляр, и считать статистику их параметров в пространстве прямых (угол, расстояние от центра). Не исключено, что максимум даст правильное направление.

Задача сия мне попадалась неоднократно. В разных размерностях (от 1 до 6, причем шестимерное пространство было совсем не декартовым — оно описывало перемещения трехмерного пространства) и с разным числом точек, но всегда без точной формулировки. Хорошего решения я, кажется, не написал ни разу, каждый раз махал рукой и шел другим путем. Но мысли остались следующие.
1) без понятия «масштаб» задача не имеет смысла. То есть, прежде чем решать ее, надо задаться неким «размером окошка», «радиусом размытия точки», «шириной серой зоны» и т.п.
2) чаще всего этот размер заранее неизвестен. Если взять его с запасом, то результат будет правдоподобен, но неточен а если размер окажется слишком маленьким, то наоборот, найдется локальное скопление среди пустоты. Лучше всего, наверное, выбрать убывающую последовательность r1>r2>r3>r4… (например, для окна 2000х2000 это моут быть степени двойки от 128 до 8), найти квадрат со стороной r1, содержащий максимальное количество точек, в нем — квадрат со стороной r2, и т.д. В этом случае наш результат будет правдоподобен во всем диапазоне масштабов.
3) Искать границы квадратов с точностью до пикселя смысла нет. Если мы ищем квадрат NxN, то достаточно перебрать квадраты с шагом N/4 по каждой координате. Например, если мы ищем квадрат 128х128 на плоскости размером 2000х2000, то достаточно рассмотреть 3600 возможных положений этого квадрата (вершина имеет координаты от 0 до 1888 с шагом 32). Завести целочисленный массив такого размера. Каждая точка попадает в 16 квадратов (или меньше) — увеличить 16 ячеек на 1. Найти максимальную — она даст стартовый квадрат.
После этого в этом квадрате перебрать 25 квадратов 64х64, в максимальном из них 25 квадратов 32х32 и т.д.
Если r1 выбран слишком маленьким, а плоскость была слишком большой, то вместо массива (который был 60х60) можно воспользоваться каким-нибудь деревом (для экономии памяти и времени на инициализацию).
Не исключено, что имеет смысл просмотреть не одну последовательность квадратов, а несколько (выбрать 10 квадратов размером r1 с наибольшим весом, из всех квадратов со стороной r2, лежащих в них — 10 наибольших и т.д.) Но это будет писать сложнее, а сработает оно только если скопление выражено нечетко, а где-то есть разреженная туманность. Впрочем, в этой ситуации надо сразу уменьшать r1.

Все raw (сейчас примерно 560 ГБ) + обработанные JPEG (90 ГБ) — на внутренних дисках. Изредка копирую на внешний.

Есть пример для L=22:
0011 1111 1111 1100 0000 00
0000 0000 1111 1111 1111 00
0101 0101 0101 0101 0101 01
1010 1010 1010 1010 1010 10

Здесь «жадный» алгоритм выдаст пару (1,2) — 18 единиц, и уйти из нее уже не удастся, остальные пары кроме (3,4) дают только 17. Так что моя эвристика тоже не работает.