Reintroducing spaces into a document

Question

Imagine we have some reference text on hand

Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation, so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate, we can not consecrate, we can not hallow this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us—that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion—that we here highly resolve that these dead shall not have died in vain—that this nation, under God, shall have a new birth of freedom—and that government of the people, by the people, for the people, shall not perish from the earth.

and we receive snippets of that text back to us with no spaces or punctuation, and some characters deleted, inserted, and substituted

ieldasafinalrTstingplaceforwhofoughtheregavetheirliZesthatthatn

Using the reference text what are some tools (in any programming language) we can use to try properly space the words

ield as a final rTsting place for who fought here gave their liZes that that n

correcting errors is not necessary, just spacing

Answer 1

Weird problem you've got there :)

If you can't rely on capitalization for hints, just lowercase everything to start with.

Then get a dictionary of words. Maybe just a wordlist, or you could try Wordnet.

And a corpus of similar, correctly spaced, material. If suitable, download the Wikipedia dump. You'll need to clean it up and break into ngrams. 3 grams will probably suit the task. Or save yourself the time and use Google's ngram data. Either the web ngrams (paid) or the book ngrams (free-ish).

Set a max word length cap. Let's say 20chars.

Take the first char of your mystery string and look it up in the dictionary. Then take the first 2 chars and look them up. Keep doing this until you get to 20. Store all matches you get, but the longest one is probably the best. Move the starting point 1 char at a time, through your string.

You'll end up with an array of valid word matches.

Loop through this new array and pair each value up with the following value, comparing it to the original string, so that you identify all possible valid word combinations that don't overlap. You might end up with 1 output string, or several.

If you've got several, break each output string into 3-grams. Then lookup in your new ngram database to see which combinations are most frequent.

There might also be some time-saving techniques like starting with stop words, checking them in a dictionary combined with incremental letter either side, and adding spaces there first.

... or I'm over-thinging the whole issue and there's an awk one liner that someone will humble me with :)

Answer 2

You can do this using edit distance and finding the minimum edit distance substring of the reference. Check out my answer (PHP implementation) to a similar question here:

Longest Common Substring with wrong character tolerance

Using the shortest_edit_substring() function from the above link, you can add this to do the search after stripping out everything but letters (or whatever you want to keep in: letters, numbers, etc.) and then correctly map the result back to the original version.

// map a stripped down substring back to the original version
function map_substring($haystack_letters,$start,$length,$haystack, $regexp)
{
    $r_haystack = str_split($haystack);
    $r_haystack_letters = $r_haystack;
    foreach($r_haystack as $k => $l) 
    {   
        if (preg_match($regexp,$l))
        {       
            unset($r_haystack_letters[$k]);
        }       
    }   
    $key_map = array_keys($r_haystack_letters);
    $real_start = $key_map[$start];
    $real_end = $key_map[$start+$length-1];
    $real_length = $real_end - $real_start + 1;
    return array($real_start,$real_length);
}

$haystack = 'Four score and seven years ago our fathers brought forth on this continent a new nation, conceived in liberty, and dedicated to the proposition that all men are created equal. Now we are engaged in a great civil war, testing whether that nation, or any nation, so conceived and so dedicated, can long endure. We are met on a great battle-field of that war. We have come to dedicate a portion of that field, as a final resting place for those who here gave their lives that that nation might live. It is altogether fitting and proper that we should do this. But, in a larger sense, we can not dedicate, we can not consecrate, we can not hallow this ground. The brave men, living and dead, who struggled here, have consecrated it, far above our poor power to add or detract. The world will little note, nor long remember what we say here, but it can never forget what they did here. It is for us the living, rather, to be dedicated here to the unfinished work which they who fought here have thus far so nobly advanced. It is rather for us to be here dedicated to the great task remaining before us—that from these honored dead we take increased devotion to that cause for which they gave the last full measure of devotion—that we here highly resolve that these dead shall not have died in vain—that this nation, under God, shall have a new birth of freedom—and that government of the people, by the people, for the people, shall not perish from the earth.';

$needle = 'ieldasafinalrTstingplaceforwhofoughtheregavetheirliZesthatthatn';

// strip out all non-letters
$regexp_to_strip_out = '/[^A-Za-z]/';

$haystack_letters = preg_replace($regexp_to_strip_out,'',$haystack);

list($start,$length) = shortest_edit_substring($needle,$haystack_letters);
list($real_start,$real_length) = map_substring($haystack_letters,$start,$length,$haystack,$regexp_to_strip_out);

printf("Found |%s| in |%s|, matching |%s|\n",substr($haystack,$real_start,$real_length),$haystack,$needle);

This will do the error correction as well; it's actually easier to do it than to not do it. The minimum edit distance search is pretty straightforward to implement in other languages if you want something faster than PHP.