Разделить строку на строку допустимых слов с помощью динамического программирования
Мне нужно найти алгоритм динамического программирования, чтобы решить эту проблему. Я пытался, но не мог понять это. Вот проблема:
Вам дается строка из n символов s[1...n], которую вы считаете поврежденным текстовым документом, в котором все знаки препинания исчезли (так что это выглядит примерно как "itwasthebestoftimes..."). Вы хотите восстановить документ, используя словарь, который доступен в виде булевой функции dict(*), такой, что для любой строки w dict(w) имеет значение 1, если w является допустимым словом, и имеет значение 0 иначе.
- Дайте алгоритм динамического программирования, который определяет, можно ли восстановить строку s[*] как последовательность допустимых слов. Время выполнения должно быть не более O(n^2), при условии, что каждый вызов dict занимает единицу времени.
- Если строка верна, ваш алгоритм должен вывести соответствующую последовательность слов.
6 ответов
Пусть длина вашего сжатого документа будет равна N.
Пусть b (n) будет логическим: true, если документ можно разбить на слова, начиная с позиции n в документе.
b (N) - истина (поскольку пустая строка может быть разбита на 0 слов). Учитывая b(N), b(N - 1), ... b(N - k), вы можете построить b(N - k - 1), рассматривая все слова, начинающиеся с символа N - k - 1. Если есть любое такое слово, w, с установленным b(N - k - 1 + len(w)), затем установите b(N - k - 1) в true. Если такого слова нет, тогда установите b(N - k - 1) в false.
В конце концов, вы вычисляете b(0), который сообщает вам, можно ли разбить весь документ на слова.
В псевдокоде:
def try_to_split(doc):
N = len(doc)
b = [False] * (N + 1)
b[N] = True
for i in range(N - 1, -1, -1):
for word starting at position i:
if b[i + len(word)]:
b[i] = True
break
return b
Есть некоторые приемы, которые вы можете сделать, чтобы получить "слово, начинающееся с позиции i", но вас просят об алгоритме O(N^2), так что вы можете просто посмотреть каждую строку, начинающуюся с i, в словаре.
Чтобы сгенерировать слова, вы можете либо изменить приведенный выше алгоритм для сохранения хороших слов, либо просто сгенерировать его следующим образом:
def generate_words(doc, b, idx=0):
length = 1
while true:
assert b(idx)
if idx == len(doc): return
word = doc[idx: idx + length]
if word in dictionary and b(idx + length):
output(word)
idx += length
length = 1
Здесь b - логический массив, сгенерированный из первой части алгоритма.
Чтобы формализовать то, что предложил @MinhPham.
Это динамическое решение для программирования.
Учитывая строку str, пусть
b [i] = true, если подстрока str [0... i] (включительно) может быть разбита на допустимые слова.
Например, добавьте начальный символ к str, например,!, Чтобы обозначить пустое слово. str = "!" + ул
Базовый случай - пустая строка, поэтому
b[0] = верно.
Для итеративного случая:
b [j] = true, если b [i] == true и str[i..j] - слово для всех i
ДП решение в с ++:
int main()
{
set<string> dict;
dict.insert("12");
dict.insert("123");
dict.insert("234");
dict.insert("12345");
dict.insert("456");
dict.insert("1234");
dict.insert("567");
dict.insert("123342");
dict.insert("42");
dict.insert("245436564");
dict.insert("12334");
string str = "123456712334245436564";
int size = str.size();
vector<int> dp(size+1, -1);
dp[0] = 0;
vector<string > res(size+1);
for(int i = 0; i < size; ++i)
{
if(dp[i] != -1)
{
for(int j = i+1; j <= size; ++j)
{
const int len = j-i;
string substr = str.substr(i, len);
if(dict.find(substr) != dict.end())
{
string space = i?" ":"";
res[i+len] = res[i] + space + substr;
dp[i+len] = dp[i]+1;
}
}
}
}
cout << *dp.rbegin() << endl;
cout << *res.rbegin() << endl;
return 0;
}
O(N^2) ДП понятен, но если вы знаете слова из словаря, я думаю, вы можете использовать некоторые предварительные вычисления, чтобы получить его еще быстрее O(N), Ахо-Corasick
Ниже приведено O(n^2) решение этой проблемы.
void findstringvalid() {
string s = "itwasthebestoftimes";
set<string> dict;
dict.insert("it");
dict.insert("was");
dict.insert("the");
dict.insert("best");
dict.insert("of");
dict.insert("times");
vector<bool> b(s.size() + 1, false);
vector<int> spacepos(s.size(), -1);
//Initialization phase
b[0] = true; //String of size 0 is always a valid string
for (int i = 1; i <= s.size(); i++) {
for (int j = 0; j <i; j++) {
//string of size s[ j... i]
if (!b[i]) {
if (b[j]) {
//check if string "j to i" is in dictionary
string temp = s.substr(j, i - j);
set<string>::iterator it = dict.find(temp);
if (it != dict.end()) {
b[i] = true;
spacepos[i-1] = j;
}
}
}
}
}
if(b[s.size()])
for (int i = 1; i < spacepos.size(); i++) {
if (spacepos[i] != -1) {
string temp = s.substr(spacepos[i], i - spacepos[i] + 1);
cout << temp << " ";
}
}
}
Строка s[] потенциально может быть разбита на несколько способов. Метод ниже находит максимальное количество слов, на которое мы можем разделить s[]. Ниже приведен эскиз / псевдокод алгоритма
bestScore[i] -> Хранит максимальное количество слов, на которые можно разбить первые символы i (иначе будет MINUS_INFINITY)
for (i = 1 to n){
bestScore[i] = MINUS_INFINITY
for (k = 1 to i-1){
bestScore[i] = Max(bestSCore[i], bestScore[i-k]+ f(i,k))
}
}
Где f(i,k) определяется как:
f(i,k) = 1 : if s[i-k+1 to i] is in dictionary
= MINUS_INFINITY : otherwise
bestScore [n] будет хранить максимальное количество слов, на которые можно разделить s[] (если значение MINUS_INFINIY, то s[] нельзя разделить)
Ясно, что время работы O(n^2)
Поскольку это похоже на упражнение из учебника, я не буду писать код для восстановления фактических позиций разделения.