Слегка математический вопрос

[spamsink]

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

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

Продемонстрирую на человеческих примерах:

Например, если один набор (корова, ворона, корона, собака), а другой (солнце, лошадь, молоко, дерево), то ответом будет [6] (в 6-й позиции в одном наборе буква А, а в другом - не А).

Или если один набор (голова, окорок), а другой (смалец, яичник), то ответом будет, например [1,2] - в одном наборе в этих позициях количество согласных чётное, а в другом - нечётное.

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

Comments

[qvz.livejournal.com]

> некоторая функция от конфигурации битов
в этих позициях позволяет определить

Вероятно, нужно заранее определиться, каков набор таких функций. Иначе это задача уже совсем другого уровня.

[spamsink]

Какая разница? Любая булевская функция от N переменных определяется таблицей истинности размером 2^N.

[qvz.livejournal.com]

Эээ, а разве переменные типа булево? Результат - булево, а переменные - нет.

[spamsink]

Если раскрыть спойлеры, то будет "Даны два набора битовых строк фиксированной длины. Нужно найти минимальный набор позиций в этих строках, такой, что некоторая функция от конфигурации битов в этих позициях позволяет определить, к какому набору принадлежит строка."

[qvz.livejournal.com]

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

[spamsink]

Ну да. Вопрос, есть ли что-нибудь более эффективное, чем экспоненциальное от длины строк.

[sab123.livejournal.com]

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

[spamsink]

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

[sab123.livejournal.com]

Можно попробовать использовать то же radix tree, но стараться его сбалансировать так, чтобы как можно ближе к корню дерева оказывалось, что строки из одного набора слева от узла, а из другого - справа. Тогда дерево можно подрезать, сократив все что ниже этого узла до двух листьев. Ну, и так далее для всех узлов - стараться подрезать дерево до как можно короткого состояния.

[spamsink]

Трюк в том, что идентифицирующей может оказаться функция от произвольного набора битов (например, XOR) и radix tree для ее поиска не помогает.

[sab123.livejournal.com]

Можно сначала построить radix tree, а потом пытаться его сокращать, прикладывая функции. Например, для XOR нужно найти два узла, где под-деревья под ними совпадают с точностью до противоположного направления выбора в самом узле.

[spamsink]

Увы, количество возможных функций возрастает экспоненциально с количеством переменных.

[sab123.livejournal.com]

Таки нет, для булевских функций все возможные функции можно привести в disjunctive normal form. Radix tree можно перевести в вид функции представленной в ДНФ, а потом применить обычную оптимизацию на ней.

[spamsink]

Т.е. мы возвращаемся к исходному пункту: я как раз логическую оптимизацию и пытаюсь делать.

[kcmamu.livejournal.com]

Ключевые слова: минимальный тест, тупиковый тест...

[kcmamu.livejournal.com]

Основополагающая статья 1958 года: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1281&option_lang=rus
Нынешее состояние: https://books.google.com/books?id=ZNl3CwAAQBAJ

[spamsink]

Спасибо! Посмотрел я начало "Теории тестового распознавания", и они там любят, чтобы число столбцов в матрице (число переменных) было много больше числа строк (наборов, задающих состояния), а у меня обычно наоборот.

Зато нашел вот это, и стало более или менее ясно.

[mtve.livejournal.com]

http://www.ics.uci.edu/~eppstein/pubs/Epp-SWAT-16-slides.pdf ?

[spamsink]

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

[pappadeux.livejournal.com]

- сделать из строковых наборов матрицы

- транспонировать, так что позицией будет номер строки

- применять волшебную функцию к строкам и смотреть на результат

[spamsink]

Не знаю, о какой волшебной функции речь. Пока решение такое:

Для наборов строк А и Б построить набор В из всех строк вида (a из A) XOR (б из Б). Решением будет минимальный набор позиций, такой, что в В не найдется строки с нулями во всех этих позициях. Это делается, например, с помощью итеративного применения SAT. Перед этим, конечно, можно применить очевидные эвристики.

[yuri-yurkevich.livejournal.com]

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

А то и сверху вниз.