How to split text without spaces into list of words? [duplicate]

Question

This question already has an answer here:

• Splitting words into specific fragments 8 answers

What is the best approach to a problem like this in Mathematica?

I can only manage this:

 func[stringlist_] := 
   With[{i = 
   Last@Flatten@
   Table[DictionaryLookup[StringTake[#[[2]], n]], {n, 14}]}, {i,
   StringDrop[#[[2]], StringLength@i]}] &@stringlist;
func1[string_] := 
   Rest@NestWhileList[func, {"", # <> CharacterRange["a", "z"]}, 
   Length@Characters@#[[2]] > 26 &][[All, 1]] &@string;


 func1["tableapplechairtablecupboard"]

(*
{"table", "apple", "chair", "table", "cupboard"}
*)

with its obvious shortcomings.

Added

Here is a pre-made file (made from WordFrequencyData /@ DictionaryLookup[] - very slow!!) incase anyone wanted to make a weighted function:

wfd = ToExpression@
Import["https://raw.githubusercontent.com/martinq321/dictionary/master/values", "List"];

eg something like this (based on @kirma's answer below) can be used to faithfully recreate about 50% of test cases:

suggested@StringJoin@removespaces@   
TextSentences[WikipediaData["PageID" -> "5094570", "ArticlePlaintext"]][[1]]

(*
the great wall of china is a series of fortifications made of stone 
brick tamped earth wood and other materials generally built along an 
east to west line across the historical northern borders of china to 
protect the chinese states and empires against the raids and 
invasions of the various nomadic groups of the eurasian steppe
*)

though I am sure there are far quicker and more efficient methods.

Answer 1

Simple greedy matching can be done as follows: construct a string pattern with longest words first and find words:

StringCases["tableapplechairtablecupboard", 
 Alternatives @@ SortBy[DictionaryLookup[], Minus@*StringLength]]

(* {"table", "apple", "chair", "table", "cupboard"} *)

Intuitive assumption is that one might use Longest to find longest match every time, but it doesn't really seem to work in this case. Note that this variation may end up not matching the whole string as it always chooses the longest match without considering if the rest can match anything in the dictionary.

For all matches one can, for instance, find all word matches using StringPosition and then find all non-overlapping complete covers of the string using per-string-position Boolean logic and SatisfiabilityInstances:

Module[{string, positions},
  string = "tableapplecharitablecupboarding";
  positions = 
   StringPosition[string, Alternatives @@ DictionaryLookup[], 
    Overlaps -> All];
  StringTake[string, Pick[positions, #]] & /@ 
   SatisfiabilityInstances[
    And @@ (BooleanCountingFunction[{1}, Length@positions] @@@ 
       Transpose@
        MapIndexed[Function[{list, index}, # && c @@ index & /@ list],
          Table[#1 <= i <= #2, {i, StringLength@string}] & @@@ 
          positions]), Array[c, Length@positions], All]] // TableForm

$$ \begin{array}{cccccccc} \text{table} & \text{apple} & \text{char} & \text{it} & \text{able} & \text{cup} & \text{boar} & \text{ding} \\ \text{table} & \text{apple} & \text{char} & \text{it} & \text{able} & \text{cup} & \text{boarding} & \text{} \\ \text{table} & \text{apple} & \text{charitable} & \text{cup} & \text{boar} & \text{ding} & \text{} & \text{} \\ \text{table} & \text{apple} & \text{charitable} & \text{cup} & \text{boarding} & \text{} & \text{} & \text{} \\ \end{array} $$

Note that although StringPosition does find "cupboard" as a valid word substring, none of solutions contain it as remaining part of the string can't be split into set of word matches. Thus, "boar", "ding" and "boarding" are only valid endings for a match.

String matching functions do take an additional IgnoreCase -> True option, which allows for matching "I" on the above example. Sadly this option also exposes various capitalized non-words, such as "Le", whatever that might be. This problem can occur also with other naturally capitalized words, such as country names.

More procedural approaches to solution search are definitely possible, but in the lines of letting Mma avoid me constructing error-prone explicit algorithms, I've chosen the above approach which converts search to a satisfiability problem.

BTW: can anyone tell why WordList[] lacks such words as "is" and "or"? This is the reason for using DictionaryLookup[] instead.