?

Log in

No account? Create an account

Слегка математический вопрос - Общество дровосеков Бердичева по изучению Мишны

Aug. 3rd, 2016

06:55 pm - Слегка математический вопрос

Previous Entry Share Next Entry

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

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

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

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

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

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

Tags:

Comments:

[User Picture]
From:qvz
Date:August 4th, 2016 07:40 am (UTC)
(Link)
> некоторая функция от конфигурации битов
в этих позициях позволяет определить

Вероятно, нужно заранее определиться, каков набор таких функций. Иначе это задача уже совсем другого уровня.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 07:54 am (UTC)
(Link)
Какая разница? Любая булевская функция от N переменных определяется таблицей истинности размером 2^N.
(Reply) (Parent) (Thread)
[User Picture]
From:qvz
Date:August 4th, 2016 10:57 am (UTC)
(Link)
Эээ, а разве переменные типа булево? Результат - булево, а переменные - нет.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 06:31 pm (UTC)
(Link)
Если раскрыть спойлеры, то будет "Даны два набора битовых строк фиксированной длины. Нужно найти минимальный набор позиций в этих строках, такой, что некоторая функция от конфигурации битов в этих позициях позволяет определить, к какому набору принадлежит строка."

(Reply) (Parent) (Thread)
[User Picture]
From:qvz
Date:August 4th, 2016 08:48 pm (UTC)
(Link)
Пардон, тупанул.
Так я правильно понял, что хочется универсальную оптимизацию поиска для произвольного набора целевых функций?
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 08:52 pm (UTC)
(Link)
Ну да. Вопрос, есть ли что-нибудь более эффективное, чем экспоненциальное от длины строк.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 4th, 2016 06:23 pm (UTC)
(Link)
Так это ж похоже на radix tree, которое используется для маршрутизации. Там проблема аналогичная - найти минимальный набор элементов в строках, только не символов, а битов. Но требуется получить в результате конкретную строку, а не набор.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 06:30 pm (UTC)
(Link)
"Символов" у меня для примера. Под спойлером, конечно, биты. Находить для каждой строки минимальный (или близкий к нему) набор, уникально идентифицирующий эту строку, я уже умею; теперь задача посложнее.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 4th, 2016 07:23 pm (UTC)
(Link)
Можно попробовать использовать то же radix tree, но стараться его сбалансировать так, чтобы как можно ближе к корню дерева оказывалось, что строки из одного набора слева от узла, а из другого - справа. Тогда дерево можно подрезать, сократив все что ниже этого узла до двух листьев. Ну, и так далее для всех узлов - стараться подрезать дерево до как можно короткого состояния.

Edited at 2016-08-04 07:24 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 07:31 pm (UTC)
(Link)
Трюк в том, что идентифицирующей может оказаться функция от произвольного набора битов (например, XOR) и radix tree для ее поиска не помогает.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 4th, 2016 07:41 pm (UTC)
(Link)
Можно сначала построить radix tree, а потом пытаться его сокращать, прикладывая функции. Например, для XOR нужно найти два узла, где под-деревья под ними совпадают с точностью до противоположного направления выбора в самом узле.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 07:50 pm (UTC)
(Link)
Увы, количество возможных функций возрастает экспоненциально с количеством переменных.
(Reply) (Parent) (Thread)
[User Picture]
From:sab123
Date:August 4th, 2016 08:21 pm (UTC)
(Link)
Таки нет, для булевских функций все возможные функции можно привести в disjunctive normal form. Radix tree можно перевести в вид функции представленной в ДНФ, а потом применить обычную оптимизацию на ней.
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:August 4th, 2016 08:26 pm (UTC)
(Link)
Т.е. мы возвращаемся к исходному пункту: я как раз логическую оптимизацию и пытаюсь делать.
(Reply) (Parent) (Thread)
[User Picture]
From:kcmamu
Date:August 4th, 2016 10:11 pm (UTC)
(Link)
Ключевые слова: минимальный тест, тупиковый тест...
(Reply) (Thread)
[User Picture]
From:kcmamu
Date:August 4th, 2016 10:23 pm (UTC)
(Link)
Основополагающая статья 1958 года: http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1281&option_lang=rus
Нынешее состояние: https://books.google.com/books?id=ZNl3CwAAQBAJ
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 5th, 2016 07:24 am (UTC)
(Link)
Спасибо! Посмотрел я начало "Теории тестового распознавания", и они там любят, чтобы число столбцов в матрице (число переменных) было много больше числа строк (наборов, задающих состояния), а у меня обычно наоборот.

Зато нашел вот это, и стало более или менее ясно.
(Reply) (Parent) (Thread)
[User Picture]
From:mtve
Date:August 6th, 2016 01:27 pm (UTC)
(Link)
http://www.ics.uci.edu/~eppstein/pubs/Epp-SWAT-16-slides.pdf ?
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 6th, 2016 03:38 pm (UTC)
(Link)
Задача похожа, но у них нет цели минимизировать количество бит, на основании которых делается заключение о принадлежности элемента к подмножеству.
(Reply) (Parent) (Thread)
[User Picture]
From:pappadeux
Date:August 9th, 2016 08:59 pm (UTC)
(Link)
- сделать из строковых наборов матрицы

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

- применять волшебную функцию к строкам и смотреть на результат
(Reply) (Thread)
[User Picture]
From:spamsink
Date:August 9th, 2016 09:20 pm (UTC)
(Link)
Не знаю, о какой волшебной функции речь. Пока решение такое:

Для наборов строк А и Б построить набор В из всех строк вида (a из A) XOR (б из Б). Решением будет минимальный набор позиций, такой, что в В не найдется строки с нулями во всех этих позициях. Это делается, например, с помощью итеративного применения SAT. Перед этим, конечно, можно применить очевидные эвристики.
(Reply) (Parent) (Thread)
[User Picture]
From:yuri_yurkevich
Date:August 11th, 2016 03:33 pm (UTC)
(Link)
Вот, кстати, хорошая задача для программиста - написать форматовщик, чтобы тексты на кириллице или латинице можно было читать справа налево, как в семитских языках.

А то и сверху вниз.
(Reply) (Thread)