{"id":9,"date":"2012-07-16T23:59:58","date_gmt":"2012-07-16T21:59:58","guid":{"rendered":"http:\/\/pit-claudel.fr\/clement\/blog\/?p=9"},"modified":"2013-11-16T10:58:32","modified_gmt":"2013-11-16T09:58:32","slug":"unscrambling-shuffled-text","status":"publish","type":"post","link":"https:\/\/pit-claudel.fr\/clement\/blog\/unscrambling-shuffled-text\/","title":{"rendered":"Unscrambling shuffled text"},"content":{"rendered":"

A story which surfaced a few years ago, and met quite some success in the press and on the internet, pretended Cambridge University had been conducing research on some of the most amazing faculties of the human brain. According to a supposed study, the order in which letters were laid out when writing a word mattered very little, provided the first and last letter be kept in place : this conclusion was supported by a short excerpt of shuffled text, which anyone could easily decipher ((Matt Davis<\/a> has a fascinating write-up on this. Snopes<\/a> also has some reference material; the full text was something like Aoccdrnig to rscheearch at Cmabrigde uinervtisy, it deosn’t mttaer waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteres are at the rghit pclae. The rset can be a tatol mses and you can sitll raed it wouthit a porbelm. Tihs is bcuseae we do not raed ervey lteter by itslef but the wrod as a wlohe.<\/em>)). As a short example, consider the following sentence: <\/p>\n

\n Narlmloy, radneig tihs shdulon’t be too hrad.\n<\/p><\/blockquote>\n

As many commentators pointed out at the time, the trick works well because the words used are relatively short; the following passage should be much harder to understand:<\/p>\n

\nThe eofrft rureieqd to sfssllcceuuy dhiepecr sbecmrald pgsaases daiaarclltmy ianserecs as wdors get lehegtinr.\n<\/p><\/blockquote>\n

This article presents an efficient algorithm to unshuffle scrambled text.<\/p>\n

<\/p>\n

Shuffling text<\/h2>\n

Shuffling a piece of text is easy:<\/p>\n

\r\nimport re, random\r\n \r\ndef shuffle_one(word):\r\n  if len(word) <= 3:\r\n    return word\r\n  \r\n  middle = list(word[1:-1])\r\n  random.shuffle(middle)\r\n   \r\n  return word[0] + ''.join(middle) + word[-1]\r\n \r\ndef repl(match):\r\n  return shuffle_one(match.groups()[0])\r\n \r\ndef shuffle(text):\r\n  return re.sub("(\\w+)", repl, text)\r\n \r\nshuffle("Normally, reading this shouldn't be too hard.")\r\n<\/pre>\n
Consider the opposite problem:<\/p>\n
Unshuffling scrambled text<\/h2>\n
Deciphering a shuffled message is non-trivial because one word can be shuffled in many different ways: \"Cadgmrbie\"<\/code>, \"Cgamdbire\"<\/code>, \"Cmbiagrde\"<\/code> and \"Cgrbimdae\"<\/code> are all acceptable representations of the word \"Cambridge\"<\/code>.<\/p>\n
To overcome this difficulty, we define a shuffling-independent signature — a function that maps each word to a signature that does not change when the word is shuffled. The following snippet implements such a signature by isolating the first and last letter of each word and sorting the central part alphabetically.<\/p>\n
\r\ndef signature(word):\r\n  word = word.lower()\r\n\r\n  if len(word) <= 3:\r\n    return word\r\n   \r\n  middle = list(word[1:-1])\r\n  return word[0] + ''.join(sorted(middle)) + word[-1]\r\n \r\nsignature("Welcome") # 'wcelmoe'\r\nsignature("Woclmee") # 'wcelmoe'\r\n<\/pre>\n
Using this function, we can now compute a normalized version of the word \"Cambridge\"<\/code>, which does not change when its letters are shuffled: signature(\"Cambridge\")<\/code>, signature(\"Cadgmrbie\")<\/code>, signature(\"Cgamdbire\")<\/code>, signature(\"Cmbiagrde\")<\/code> and signature(\"Cgrbimdae\")<\/code> are all equal to \"cabdgimre\"<\/code>.<\/p>\n
We then compute a signature-to-word mapping (possibly multi-valued — different words may map to the same signature) using a word list ((This list<\/a>, found on Keith Vertanen’s website<\/a>, works well)) (english.txt<\/code>).<\/p>\n
\r\nhandler = open("english.txt", encoding = "utf-8")\r\nwords = [word.strip() for word in handler.readlines()]\r\nhandler.close()\r\n \r\n# Load dictionary entries\r\ndictionary = {signature(word):word for word in words}\r\n<\/pre>\n
This gives us a signature-to-word dictionary, which we can then use to decipher the shuffled message. For this, we first compute the signature of each scrambled word in the input, and then retrieve the corresponding clear-text words from the dictionary.<\/p>\n
\r\ndef unshuffle_one(word):\r\n  sig = signature(word)\r\n  return dictionary[sig] if sig in dictionary else word\r\n   \r\ndef unrepl(match):\r\n  return unshuffle_one(match.groups()[0])\r\n \r\ndef unshuffle(text):\r\n  return re.sub("(\\w+)", unrepl, text)\r\n \r\nprint(unshuffle("The eofrft rreuqied to sfssllcceuuy dhiepecr sbecmrald "\r\n                "pgsaases daiaarclltmy ianserecs as wdors get lehegtinr."))\r\n<\/pre>\n
Taking the signature of each word in our example sentence, we obtain<\/p>\n
The effort reeiqrud to sccefllssuuy dceehipr sabcelmrd paaegsss daaacillmrty iaceenrss as wdors get leeghintr.<\/p><\/blockquote>\n
And by applying the signature-to-word mapping to each word, we finally obtain the clear text:<\/p>\n
The effort required to successfully decipher scrambled passages dramatically increases as words get lengthier.<\/p><\/blockquote>\n
Further thoughts<\/h2>\n
Handling signature collisions<\/h3>\n
The code can be modified to allow for signature collisions (collisions happen when multiple words have the same signature): for this, instead of using a dictionary as a word-to-word mapping, we use a dictionary as a word-to-list-of-words mapping:<\/p>\n
\r\n# Load dictionary entries\r\ndictionary = {}\r\nfor word in words:\r\n  sig = signature(word)\r\n\r\n  if not sig in dictionary:\r\n    dictionary[sig] = [] # Create an empty list\r\n  \r\n  # Add word to the list of all words sharing signature sig\r\n  dictionary[sig].append(word)\r\n\r\ndef unshuffle_one(word):\r\n  sig = signature(word)\r\n  return '|'.join(dictionary[sig]) if sig in dictionary else word\r\n<\/pre>\n
The following function prints a list of all signature collisions.<\/p>\n
\r\ndef find_collisions():\r\n  for sig in dictionary:\r\n    if len(dictionary[sig]) > 1:\r\n      print(', '.join(dictionary[sig]))\r\n<\/pre>\n
Relatively common words triggering signature collisions are listed below.<\/p>\n\n\n\n
Most common English words triggering signature collisions<\/th>\n<\/tr>\n
\n      aboard, abroad
\n      alerting, altering
\n      angels, angles
\n      barking, braking
\n      beard, bread
\n      bedroom, boredom
\n      blowing, bowling
\n      brunt, burnt
\n      caller, cellar
\n      calvary, cavalry
\n      carve, crave
\n      cashing, chasing
\n      catering, creating
\n      centers, centres
\n      circles, clerics
\n      clot, colt
\n      cloud, could
\n      compiled, complied\n    <\/td>\n		\n      complaint, compliant
\n      conservation, conversation
\n      dairies, diaries
\n      damned, demand
\n      density, destiny
\n      divers, drives
\n      entirety, eternity
\n      excepted, expected
\n      feeling, fleeing
\n      files, flies
\n      fingers, fringes
\n      fired, fried
\n      flower, fowler
\n      forests, fosters
\n      gateway, getaway
\n      hate, heat
\n      haters, hearts
\n      incest, insect\n    <\/td>\n		\n      lair, liar
\n      lakes, leaks
\n      lanes, leans
\n      maiden, median
\n      males, meals
\n      marital, martial
\n      panel, penal
\n      panels, planes
\n      parties, pirates
\n      patrol, portal
\n      pedals, pleads
\n      pluses, pulses
\n      pointers, proteins
\n      recourse, resource
\n      redrawing, rewarding
\n      reserve, reverse
\n      resorts, rosters
\n      sacred, scared\n    <\/td>\n		\n      saints, stains
\n      sales, seals
\n      shooting, soothing
\n      signing, singing
\n      sinks, skins
\n      skates, stakes, steaks
\n      sorting, storing
\n      spared, spread
\n      spilt, split
\n      spotlight, stoplight
\n      spots, stops
\n      sprite, stripe
\n      taxes, texas
\n      tenor, toner
\n      trail, trial
\n      tribune, turbine
\n      warp, wrap
\n      weird, wired\n    <\/td>\n<\/table>\n
To experiment by yourself, you can download the full source code of this article<\/a>.<\/p>\n
Did you like this article? Leave a comment! (If you hated it, that’s fine too: leave a message and tell me what I should improve next time!)<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"
This article presents an efficient algorithm to unscramble shuffled text (suhffled txet), with a full implementation in Python.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,17,8,14],"tags":[13,15],"_links":{"self":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/9"}],"collection":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/comments?post=9"}],"version-history":[{"count":5,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/9\/revisions"}],"predecessor-version":[{"id":115,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/posts\/9\/revisions\/115"}],"wp:attachment":[{"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/media?parent=9"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/categories?post=9"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/pit-claudel.fr\/clement\/blog\/wp-json\/wp\/v2\/tags?post=9"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}