Dynamic Programming - Restoring white space between words in a file

  • #1
2
0
Poster warned about not using the homework template
All the white space among words in a text file was lost. Write a C++ program which using dynamic programming to get all of the possible original text files (i.e. with white spaces between words) and rank them in order of likelihood with the best possible runtime.

You have a text file of dictionary words and the popularity class of the word (words are listed from popularity 1-100 (being most popular words), 101-200, etc)

- Input is a text file

- Output should be a series of files, each containing one the possible original documents and one document containing the ranking of likelihood of the outputs

- Use the right data structure for storing the data structure in memory, as this will impact the runtime

- Only dictionary words will be in the input text file

- Punctuation such as: . ? ! ; should be handled by program

- Remove words with non-English letters from dictionary

- Remove all the single letter words except for 'I' , 'A', and 'a' from dictionary or handle them in another way. (Important so there aren't infinite possible solutions)

To Test:

- Create text files using words in the dictionary. The ranking of outputs is in part based on the popularity class of the words used

I know how to use filestreams to store information from the file, but i'm not sure what data structure to use to store the dictionary for max efficiency
Also not sure of the logic of generating multiple output text files and how to create all possible original documents
 

Answers and Replies

  • #2
.Scott
Homework Helper
2,725
1,025
You have a tree-walk. In each case, you will look at the start of the text and look for all possible first words. The skip past that word and repeat the process. Whenever you get to the end of the file or punctuation, you have success. So back up to the previous word and look for another. Whenever you get to a character string that cannot form a word, that string has failed to generate a solution. So, once again, back up to the previous word and look for another.
 

Related Threads on Dynamic Programming - Restoring white space between words in a file

  • Last Post
Replies
2
Views
643
Replies
2
Views
785
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
16
Views
2K
Replies
0
Views
4K
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
982
  • Last Post
Replies
22
Views
2K
Top