Сегментация текста

[Mr. Dred]

Здравствуйте. Столкнулся вот с такой задачей:

есть некоторый текст символов в алфавите мощностью $m$. Необходимо найти такое разбиение (сегментацию) текста, при котором целевой функционал $f(x)$ (это может быть функция от частот отдельных символов текста, или среднее растояние в символах между одинаковыми символами) находится в глобальном оптимуме.

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

[PAV]

Допустим, что некоторая позиция в тексте является точкой разбиения. Можно ли считать, что рассматривая два фрагмента текста слева и справа от этой точки как самостоятельные тексты, и сегментируя их независимо друг от друга, объединение оптимальных разбиений даст оптимальное разбиение исходного текста (среди всех, которые содержат эту точку)? Это кажется необходимым условием для того, чтобы можно было сделать хоть что-то в духе динамического программирования, и не рассматривать полный перебор всех разбиений.

[Mr. Dred]

Спасибо за идею, попробую её задействовать.

[PAV]

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

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

[Mr. Dred]

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

Тоесть пусть мы имеем текст S=ABBAAABBAB

Под интервалом $i$-ого символа понимается растояние в символах от предъидущего такого же символа, или от начала, если он встретился впервые. Для приведенного текста соответствующими интервалами будут
1 2 1 3 1 1 4 1 3 2
A B B A A A B B A B

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

[PAV]

Пока что я не вижу никакого противоречия с принципом применимости ДП. Значения, которые Вы приписали каждому символу, от разбиения не зависят. Вопрос в том, как определяется целевая функция.