Подтвердить что ты не робот

Разделить строку на строку допустимых слов, используя динамическое программирование

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

Вам предоставляется строка из n символов s [1... n], которая, как вы считаете, является поврежденным текстовым документом, в котором вся пунктуация исчезла (так что она выглядит примерно так: "itwasthebestwhile..." ). Вы хотите восстановить документ с помощью словаря, который доступен в виде логической функции dict (*), так что для любой строки w dict (w) имеет значение 1, если w является допустимым словом и имеет значение 0 в противном случае.

  • Дайте динамический алгоритм программирования, который определяет, может ли строка s [*] быть восстановлена ​​как последовательность действительных слов. Время работы должно быть не более O (n ^ 2), предполагая, что каждый вызов dict требует единицы времени.
  • В том случае, если строка верна, сделайте свой алгоритм выводом соответствующей последовательности слов.
4b9b3361

ОТВЕТЫ

Ответ 1

Пусть длина сжатого документа равна 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), поэтому вы можете просто просмотреть каждую строку, начиная с я в словаре.

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

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 - логический массив, сгенерированный из первой части алгоритма.

Ответ 2

Чтобы формализовать то, что предложил @MinhPham.

Это динамическое программирующее решение.

Для строки str, пусть

b [i] = true, если подстрока str [0... i] (включительно) может быть разделена на допустимые слова.

Подготовьте некоторый начальный символ к str, скажем!, чтобы представить пустое слово. str = "!" + str

Основной случай - это пустая строка, поэтому

b [0] = true.

Для итерационного случая:

b [j] = true, если b [i] == true и str [i..j] является словом для всех я < J

Ответ 3

Решение dp в С++:

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;
}

Ответ 4

O(N^2) Dp понятен, но если вы знаете слова словаря, я думаю, вы можете использовать некоторые предварительные вычисления, чтобы получить еще быстрее в O(N). Aho-Corasick

Ответ 5

Ниже приведено решение 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 << " ";
    }
    }
}

Ответ 6

Строку s [] можно разделить на несколько способов. В приведенном ниже методе найдено максимальное количество слов, в которых мы можем разделить s []. Ниже представлен эскиз/псевдокод алгоритма

bestScore [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)

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