Given a dictionary of words and their frequencies (how many times they appear in a universe and given a string(no spaces, punctuation, etc.). What is the best way to segment into individual words? I believe a dynamic programming approach would be best. But I am not sure how to proceed about throwing away unnecessary prefixes of identified words and so on.

Ex. "theyouthevent" 

 could be "the you the vent"
 or "they out he vent"
 or "the youth event" (most likely)

I think Peter Norvig outlines a pretty good approach in this http://norvig.com/ngrams/ch14.pdf

Just curious to see if there are any other good approaches suited for the specific problem with the data I have. Norvig has n-gram data while I only have word frequencies (which is essentially a unigram)

  • $\begingroup$ Could you give minimal example, if possible with all problems that you encounter. say words are {cat, book, tea} , you are given string for example 'bookteabookcat'? If some words are prefixes of other words, but you have frequencies, would starting from words not being prefixes help? $\endgroup$ – Evil Jan 30 '19 at 22:50
  • $\begingroup$ Have you looked into suffix trees or suffix arrays? $\endgroup$ – Pseudonym Jan 31 '19 at 0:01
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 31 '19 at 7:20
  • $\begingroup$ What's the function to optimize? You say one option is "most likely" -- but why? $\endgroup$ – Raphael Jan 31 '19 at 7:21
  • $\begingroup$ This is asked and answered here: stackoverflow.com/q/26189292/47984 $\endgroup$ – j_random_hacker Jan 31 '19 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.