Алгоритмы. От частного к общему

http://en.wikipedia.org/wiki/Longest_common_subsequence

ничегонипонел… есть минимальное значение + некоторый set после него? что мешает сделать мап [a; b] для i -> [0; x] для j, где j=i–a?

Взять за базу первое число, и для каждого следующего числа делать diff, урезая расхождения. Пустые строки проматывать continue.

Так и не понял, в чем проблема.

>это где-то очень просто и элегантно реализовано.

http://ru.wikipedia.org/wiki/Операции_над_множествами

P.S. Табулятор Холлерита (1890 г.) http://chernykh.net/content/view/16/40/ :)

uniteMask = zipWith join
        where join x y |x==y       = x
                       |otherwise  = '?'
blank [] = True
blank (h:_) = h==' '
              
main = do
    content <- readFile "input.txt"
    putStrLn $ foldr1 uniteMask $ filter (not.blank) $ lines content

Или я чего-то не понял?

123 && 124 --> 120

> 123 && 124 --> 120

Думаешь, топикстартер твой намёк понял? Я чё-то сильно сомневаюсь:)

> Longest_common_subsequence

Не совсем то, что нужно.

Пустых строк нет, это я для наглядности.

Операции над множествами не то.

123 && 124 --> 120

Ну как-то так, если я правильно понял о чем речь.

Я наверно задачу неправильно описал. Есть множество чисел, точнее последовательность. Из них нам нужно сделать маску, которой будут соответствовать все числа последовательности.

Спать хочу, завтра с утра продолжу «ресерч» :).

Хотя мне почему-то кажется, что будет так:

Взять за базу первое число, и для каждого следующего числа делать diff, урезая расхождения.

Хотя это и не совсем то, что нужно.

>Хотя это и не совсем то, что нужно.

Зависит от того, должна ли эта маска быть десятичной или двоичной :)
Или восьмеричной, к примеру.

Если маска десятичная (122 && 126 → 120), можно обрабатывать числа как строки.

Если маска двоичная (122 && 126 → 122), проще использовать побитовые операции.

Если маска примененная к строке должна сработать в случае когда в последовательности чисел имеется такая же строка, то есть любопытный механизм в дайджесте сквида. Правда он срабатывает в 99%.

> нужно сделать маску, которой будут соответствовать все числа последовательности.

для такой постановки задачи ответ можно дать ответ «*». Следует всё же уточнить, что именно хочется :)

Зависит от того, должна ли эта маска быть десятичной или двоичной :)
Или восьмеричной, к примеру.

Если маска десятичная (122 && 126 → 120), можно обрабатывать числа как строки.

Десятичной.

Если маска примененная к строке должна сработать в случае когда в последовательности чисел имеется такая же строка, то есть любопытный механизм в дайджесте сквида. Правда он срабатывает в 99%.

А можно подробнее об этом? Со ссылками на хорошие доки. И насколько это сложно в реализации?

для такой постановки задачи ответ можно дать ответ «*». Следует всё же уточнить, что именно хочется :)

Ну да, видимо придется еще уточнить :)

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

112, 113, 114, 115, 116, 118, 120, 121, 122, 123
150, 151, 152, 153 ...

Все это внутри одной ноды. И если для первой последовательности, при составлении маски мы можем принебречь разрывами в 1-2 шага, то для второй нужна отдельная маска:

1[12]\d <--- все числа входят в маску, но маска немного шире последовательности
15\d

Root node
-Child node (sequence 1, sequence 2, ...)
--Child node (sequence 1, sequence 2, ...)
...

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

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

Постановка задачи. Дано множество чисел в десятичной записи. Например, 100, 101, 102, 105, 140, 5140, 5150. Требуется построить шаблон, по которому отсеивать большую часть чисел.

Решение задачи. Каждое число - это набор цифр - коэффициентов десятичного полинома (a_0,a_1,a_2,...,a_{k-1}). Таким образом, если взять k_max = max(n_i), i = 1,2,...,N - максимальное число ненулевых разрядов среди указанного множества полиномов, задача сводится к нахождению максимального, либо наибольшего, элемента указанного множества. Данное конечное множество, по-сути, является подмножеством N-мерного куба. Программно, максимальный и наибольший элементы могут быть найдены посредством построения структуры типа леса, связывающей сравнимые числа. Соответственно, максимальными элементами будут вершины деревьев леса. Наибольшим - максимальный элемент дерева, если лес состоит из одного дерева. В самом простом случае, задача имеет квадратичную сложность, по числу попарных сравнений строк.

http://www.squid-cache.org/CacheDigest/cache-digest-v5.txt

Более обще, задан конечный алфавит A, и конечное множество S строк конечной длины над заданным алфавитом. Необходимо построить регулярную грамматику (или регулярное выражение), которой удовлетворяет каждая из строк множества S и только они.

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

[Или к регулярному выражению, что гораздо интереснее, поскольку при этом возникает задача оптимизации полученного регулярного выражения. Например, после перехода может получиться что-то вроде ((a|b)c)|((a|b)d)].

Это «типа научный» подход. Кстати,прикольная тема. Займусь этим на досуге в свободное время :-)

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

Это «типа научный» подход.

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

Постановщик задачи говорит о _конечном_ языке, если я правильно понимаю.

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

Будет ли при этом потеряна эффективность разбора-вопрос спорный.

И вообще, граждане, Хватит деградировать, и приводить википедию в качестве источника информации. Ссылайтесь на заслуживающие доверия и уважения книги, как это принято и всегда было принято в научных кругах. Во-первых такая практика прошла проверку временем, а во-вторых, разработка ПО, как вид интеллектуальной деятельности человека, имеет непосредственное отношение к науке.

Конечно, нельзя набрать в гугле: регулярные выражения, и получить ссылки на несколько заслуживающих доверия книг, раздобыть их, прочесть за несколько секунд, и, как говорила бывало про меня в давние времена учительница литературы, «я не читал, но считаю» :-)

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