5
\$\begingroup\$

Today on Stack Overflow the following question came https://stackoverflow.com/questions/39393112/find-out-if-string-contains-english-words-only

The question itself has following prerequisites:

  • A system dictionary that contains all the words of the English language

With the following requirements

  • The input is a text containing only a-z letters, which may or may not end up to be all words contained in the dictonary
  • The algorithm must be able to identify if the sentence only contains words from the dictionary
  • It has to be fast, as it will work with a suggested number of 300.000 words

As the question wasn't in the scope of Stack Overflow, the question got rightfully closed, however, in the comments I was discussing with PaulF what might be an approach to this question.

The question itself is asking for C#, however, as I just wanted to prototype my idea, I created a javascript version of my approach, and I thought I wouldn't mind getting review about this approach.

The workflow of the create the resource dictionary:

  • Get a dictionary from an online resource
  • Group the words per first letter (so dictionary['a'] would contain all the english words starting with a)
  • Group the words per letter on their length (and keep the length of the longest word)

To check the user input itself, the following is happening

  • The sentence is sent to a isWordInDictionary function, giving the sentence and the dictionary
  • the first letter is defined, in case no words in the dictionary contain the first letter, false is returned
  • then starting from the longest word, the text is "matched" against the current letters grouped by length in the arrays, when no match is found, I reduce the word if possible, and check again. If not, false is also returned

What I am currently not checking:

  • is the input correct
  • does the dictionary contain the correct words ( though from looking through the list here, that doesn't seem to be the case )

My question would be rather on the algorithm, what could I improve to make the engine potentially faster.

'use strict';
/* dictionary copyright
  Copyright © J Ross Beresford 1993-1999. All Rights Reserved. The following restriction is placed on the use of this publication: if the UK Advanced Cryptics Dictionary is used in a software package or redistributed in any form, the copyright notice must be prominently displayed and the text of this document must be included verbatim.
 */
var dictionaryUrl = 'https://raw.githubusercontent.com/Icepickle/wordlist/master/words2.txt';

/**
 * @param {Array} array an array containing all the words
 * @param {Function} keyFn a function that defines the key for each word
 * @param {Function} transformFn an optional function that transforms each word before creating the key and adding it to the dictionary
 * @returns an object containing all the array in the dictionary per key gotten from keyFn
 */
function createDictionaryFromWords(array, keyFn, transformFn) {
  var result = {},
    keys = [],
    wordLengthFn = function(word) {
      return word.length;
    };
  array.forEach(function(item) {
    var trf = transformFn ? transformFn(item) : item;
    var key = keyFn(trf);
    if (!result[key]) {
      result[key] = [];
      keys.push(key);
    }
    result[key].push(trf);
  });
  keys.forEach(function(key) {
    result[key] = createGrouped(result[key], wordLengthFn);
  });
  return result;
}

/**
 * @param {Array} array
 * @param {keyFn} a function to define the key per item in the array
 * @returns {Object} an object containing the groups for the array
 */
function createGrouped(array, keyFn) {
  var result = {
    groups: {}
  };
  array.forEach(function(item) {
    var key = keyFn(item);
    if (!result.groups[key]) {
      result.groups[key] = {
        max: key,
        items: []
      };
    }
    result.groups[key].items.push(item);
    if (key > result.max) {
      result.max = key;
    }
  });
  return result;
}

/**
 * @param {string} text
 * @param {object} dictionary
 * @returns true if the full sentences only contains words from the dictionary, false if not
 */
function isWordInDictionary(text, sd) {
  var first = text.charAt(0),
    i,
    t,
    tlen = text.length,
    j,
    subset,
    mlen = tlen + 1,
    len,
    subtext;
  if (!sd[first]) {
    // no words that start with this letter in dictionary
    return false;
  }
  if (sd[first].max < mlen) {
    mlen = sd[first].max;
  }
  for (j = mlen; --j >= 0;) {
    subset = sd[first].groups[j];
    if (!subset) {
      continue;
    }
    subtext = text.substr(0, j);
    for (i = 0, len = subset.items.length || 0; i < len; i++) {
      t = subset.items[i];
      if (!t) {
        continue;
      }
      if (subtext === t) {
        console.log('found ' + t);
        if (text.length === t.length) {
          // no more text
          return true;
        }
        if (isWordInDictionary(text.substr(t.length), sd)) {
          return true;
        }
      }
    }
  }
  return false;
}

/**
 * @param {string} the word that will be checked in the dictionary (or sentence of nonspaced words
 * @param {object} the dictionary received from the service
 * @returns true or false based on isWordInDictionary
 */
function checkWord(word, dictionary) {
  console.log('Checking "' + word + '"');
  return isWordInDictionary(word, dictionary);
}

/**
 * @param {string} the url to the dictionary
 * @returns {Promise}
 */
function getDictionary(url) {
  var promise = new Promise(function(resolve, reject) {
    var req = new XMLHttpRequest();
    req.addEventListener('load', function(resp) {
      var lines = resp.target.responseText.split('\n');
      console.log('total words found: ' + lines.length);
      resolve(createDictionaryFromWords(lines, function(word) {
        return word.charAt(0);
      }, function(word) {
        return word.toLowerCase();
      }));
    });
    req.open('get', url);
    req.send();
  });
  return promise;
}

/**
 * @program
 * main entry point for application
 */
window.addEventListener('load', function() {
  console.log('getting dictionary');
  getDictionary(dictionaryUrl).then(function(dictionary) {
    console.log('received dictionary');
    console.log(checkWord('handstand', dictionary));
    console.log(checkWord('pineappleexpress', dictionary));
    console.log(checkWord('thissssisapple', dictionary));
    console.log(checkWord('thisisanunevenbattleaxe', dictionary));
  });
});

\$\endgroup\$
  • 4
    \$\begingroup\$ I'd say it doesn't matter what motivated the creation of your code. There are sometimes questions from job interviews that could also result in some kind of rejection, but they are often very interesting and insightful or at least lead to answers of that kind. Have an upvote for taking the time to think about a problem and try to find a solution. \$\endgroup\$ – I'll add comments tomorrow Sep 8 '16 at 21:05
  • 1
    \$\begingroup\$ @I'lladdcommentstomorrow that's true ofcourse, but should I then put a link in the comments of the on-hold question on stack overflow to here? \$\endgroup\$ – Icepickle Sep 8 '16 at 21:18
  • 1
    \$\begingroup\$ Sure, why not? At worst, TH Todorov would misinterpret this as an invitation to post his future questions about unwritten code on codereview. That wouldn't be worse than any other user misunderstanding the scope of this site and within hopefully only a minimal amount of closed questions that would be corrected. At good, TH Todorov would get many answers to "his" question here. At very good, we all learn from the answers your question receives. At best, TH Todorov posts an answer here to your question that he came up with himself for lack of answers he received on Stack Overflow. Sharing is caring. \$\endgroup\$ – I'll add comments tomorrow Sep 8 '16 at 21:32
  • 2
    \$\begingroup\$ What's the reason not to use a key/value entry for each word? Even if JS allocates 100 bytes per word, 30MB seems more than an affordable price for better speed (and ES6 Set for more gain) and simplicity: the check would be just allWords[word] and for a phrase phrase.split(/\s+/).every(word => allWords[word]). \$\endgroup\$ – wOxxOm Sep 9 '16 at 1:35
  • \$\begingroup\$ @wOxxOm true, I could simply use the and object to see if it exists. I probably over thought it a bit based on the first idea the original author had. I wanted to make a possible search pattern in a smaller dataset by dividing the dataset in a tree based on first letter and length of the word. The split however wouldn't work (i think), the phrase received is just words without spaces or separation in between (I don't know why that requirement is there) \$\endgroup\$ – Icepickle Sep 9 '16 at 5:25
1
\$\begingroup\$

It should be noted, that dictionary file is completely unusable because it contains swarms of gibberish like b, z, th, tryt oread asse parate, and misses a lot e.g. words.

Anyway, my idea is to use a lookup table with both start/end letters so we can tell sooner if a word is possible at any given input text range.

word length:
    first + last letter:
        word
        word
        ..........
    first + last letter:
        word
        word
        ..........
    ..........
word length:
    first + last letter:
        word
        word
        ..........
    first + last letter:
        word
        word
        ..........
    ..........
..........

Compared to OP's it takes twice as long to build the lookup table for 2.5MB text: ~150 ms:

function downloadText(url) {
    return new Promise(resolve => {
        var req = new XMLHttpRequest();
        req.onload = () => resolve(req.responseText);
        req.open('get', url);
        req.send();
    });
}

function buildLookupTable(text) {
    text = text.toLowerCase();
    var LUT = {minLen: 1, maxLen: 0};
    var rxWord = /\w+/gm;
    for (var match; match = rxWord.exec(text); ) {
        var word = match[0];
        var wordLen = word.length;
        if (wordLen > LUT.maxLen)
            LUT.maxLen = wordLen;

        var fringeHub = LUT[wordLen];
        if (!fringeHub)
            fringeHub = LUT[wordLen] = {};

        var fringe = word[0] + word.slice(-1);
        var words = fringeHub[fringe];
        if (!words)
            words = fringeHub[fringe] = new Set();
        words.add(word);
    }

    // Fix the dictionary a bit: remove all 1-letter nonwords (except I and A)
    LUT[1] = LUT[1] ? {aa: LUT[1].aa, ii: LUT[1].ii} : undefined;
    return LUT;
}

But parsing is much faster: all possible splittings are calculated in 300ms when running the test 10k times (the first answer was ready in under 100ms!), compared to OP's 600ms.

function parsePhrase(text, LUT, start) {
    start = start || 0;
    var phrases = [];
    var maxNext = Math.min(text.length, start + LUT.maxLen - 1);
    var firstChar = text[start];
    var wordLen = LUT.minLen;
    for (var next = start + wordLen; next <= maxNext; next++, wordLen++) {
        var fringeHub = LUT[wordLen];
        if (!fringeHub)
             continue;

        var words = fringeHub[firstChar + text[next - 1]];
        if (!words)
             continue;

        var word = text.substring(start, next);
        if (!words.has(word))
             continue;

        if (next == text.length) {
            phrases.push([word]);
            break;
        }

        parsePhrase(text, LUT, next).forEach(phrase =>
            phrases.push([word].concat(phrase))
        );
    }
    return phrases;
}

It's recursive and doesn't lowercase the text. That might be added in a wrapper if needed.
In case only a check is needed without listing the words, the end of the function is simplified:

        if (next == text.length || parsePhrase(text, LUT, next))
            return true;
    }
    return false;
}

Usage:

downloadText('https://raw.githubusercontent.com/Icepickle/wordlist/master/words2.txt')
    .then(buildLookupTable)
    .then(lut => {
        // the dictionary doesn't have 'words' so the next will be empty:
        console.log(parsePhrase('trytoreadmeasseparatewords', lut).map(w => w.join(' ')));
        // 'word' will work (plus 60+ variants with gibberish thanks to the "dictionary")
        console.log(parsePhrase('trytoreadmeasseparateword', lut).map(w => w.join(' ')));
    });
\$\endgroup\$
  • \$\begingroup\$ That's a nice approach to it, did you try as you suggested in the comments in the starting post to match with a key/value pair or a set? I agree that the word list is gibberish, but it was the one I could find of with a bit of searching (it was actually a SO topic where I found it :) ) Cool review :) \$\endgroup\$ – Icepickle Sep 9 '16 at 23:07
  • 1
    \$\begingroup\$ I tried but it was slower because dictionary look-up speed is proportional to the number of items inside. \$\endgroup\$ – wOxxOm Sep 10 '16 at 6:07
  • \$\begingroup\$ I saw that the wordlist is no longer maintained on github, so I got a new wordlist and added it to my personal github space, maybe you can update the downloadlink to that one for the dictionary?) \$\endgroup\$ – Icepickle Aug 22 '17 at 20:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.