Retrieve words from dictionary when they meet letter requirements

Question

I have a set of functions that retrieve words from some arbitrary dictionary based on what letters they have. For example, this function gets words that use only the specified letters:

function getWordsWithOnlySpecifiedLetters(array $dictionary, string $letters)
{
    foreach ($dictionary as $key => $value) {
        if(mb_strlen($value) > mb_strlen($letters)) unset($dictionary[$key]);
    }

    $step = 0;
    $strSplit = preg_split('//u', $letters, null, PREG_SPLIT_NO_EMPTY);
    $result = [];
    foreach ($dictionary as $word) {
        $step++;
        $wordSplit = preg_split('//u', $word, null, PREG_SPLIT_NO_EMPTY);
        sort($wordSplit);
        sort($strSplit);
        if (array_map('mb_strtolower', $wordSplit) === array_map('mb_strtolower', $strSplit)) {
            //echo "All specified letters from $letters are in $word | Step $step<hr>" . PHP_EOL;
            $result[] = $word;
        }
    }

    return $result;
}

Example usage:

$dictionary = ['apple', 'sample', 'api', 'pia', 'тоҷик'];
getWordsWithOnlySpecifiedLetters($dictionary, "aip");

This would return the words api and pia.

getWordsWithOnlySpecifiedLetters($dictionary, "leamps");

This one would return the word sample.

---

I also have a function that doesn't require that they exclusively use the selected letters, but rather that they use all of the specified letters (and any other letters).

function getWordsWithSpecifiedLetters(array $dictionary, string $letters)
{
    $step = 0;
    mb_internal_encoding("UTF-8");
    $result = [];
    foreach ($dictionary as $word) {
        $step++;
        $wordSplit = preg_split('//u', $word, null, PREG_SPLIT_NO_EMPTY);
        $strSplit = preg_split('//u', $letters, null, PREG_SPLIT_NO_EMPTY);
        $wordSplit = array_filter($wordSplit, function($x) use (&$strSplit) {
            if (in_array(strtolower($x), array_map('strtolower', $strSplit), true)) {
                $pos = array_search(strtolower($x), array_map('strtolower', $strSplit), true);
                unset($strSplit[$pos]);
                return false;
            }
            return true;
        });
        if (count(array_diff($strSplit,$wordSplit)) === 0) {
            //echo "$word contains all letters of $letters | Step $step<hr>" . PHP_EOL;
            $result[] = $word;
        }
    }

    return $result;
}

Example usage:

$dictionary = ['apple', 'sample', 'api', 'pia', 'тоҷик'];
getWordsWithSpecifiedLetters($dictionary, "ple");

This returns the words sample and apple.

I have more 90000 words in my dictionary (UTF-8). This results in a very slow program; if I'm trying to find something from the full dictionary it may take tens of thousands of loops. How can I improve the performance of these functions?

You can download my dictionary from here and testing your code using dictionary words.

Answer 1

How about removing the dictionary preparation each time at a cost of increasing your dictionary width?

You could have an alphabetized lookup column (the rows aren't alphabetized -- each letter of each word is sorted alphabetically) and a word column:

lookup  |  word
-----------------
aelpp   |  apple
aelmps  |  sample
aip     |  api
aip     |  pia
икотҷ   |  тоҷик

Using your lowercase, alphabetized $needle, when you want to find "whole" matches, you merely search the lookup column with the = operator.

SELECT `word` FROM `dictionary` WHERE `lookup` = 'икотҷ'

When you want to match the $needle characters at a minimum, you call:

SELECT `word` FROM `dictionary` WHERE `lookup` REGEXP '.*и.*к.*о.*т.*ҷ.*'

Leveraging something like this technique: Custom REGEXP Function to be used in a SQLITE SELECT Statement with this intended usage: ~.*и.*к.*о.*т.*ҷ.*~u

This, of course, is just a theoretical suggestion -- I haven't tried to do anything like this before.

And definitely remember to sanitize and escape the $needle to be offered to the query for security reasons.

Mostly I am suggesting that you sacrifice memory for speed. Only the $needle should be modified with character sorting and strtolower actions. These processes are expected to be "already done" on words prior to being stored in the dictionary.

Here is another post of mine with the same basic logic: How to best compare these two strings for values even though they are in random order?

---

If altering the dictionary table structure is unattractive, this is how I would recommend searching for exact character matches in any order:

Code:

function getWordsContainingTheExactSpecifedLetters_inanyorder_nomore_noless(array $dictionary, string $letters, string $encoding = 'UTF-8'){
    $lettersLength = mb_strlen($letters, $encoding);  // call just once and cache
    $lettersSplit = preg_split('//u', mb_strtolower($letters, $encoding), null, PREG_SPLIT_NO_EMPTY);
    sort($lettersSplit);

    $result = [];
    foreach ($dictionary as $word) {
      if(mb_strlen($word, $encoding) == $lettersLength) {
        $wordSplit = preg_split('//u', mb_strtolower($word, $encoding), null, PREG_SPLIT_NO_EMPTY);
        sort($wordSplit);
        if ($wordSplit === $lettersSplit) {
          $result[] = $word;
        }
      }
    }
    return $result;
}

Of course, you will need to change the qualifying condition if you wish to retain larger words that merely contain the letters.

Answer 2

Your first function can be easily improved by two ways.

Avoid changing the contents of $dictionary.

foreach ($dictionary as $key => $value) {
    if(mb_strlen($value) > mb_strlen($letters)) unset($dictionary[$key]);
}

can be suppressed, simply inserting this test at the begin of the next foreach():

if(mb_strlen($word) <= mb_strlen($letters))

Don't repeat $letters processing.

Currently you're sorting $strSplit at each foreach() step, while it can be done once for all before entering loop. Likewise for array_map('mb_strtolower', $strSplit).

(also drop useless code)

It appears that $step was used only for tests purpose, so you can give up.

Finally

Taking advantage of the above recommendations, the following modified script should take less time to execute:

function getWordsWithOnlySpecifedLetters(array $dictionary, string $letters)
{
    $strSplit = preg_split('//u', $letters, null, PREG_SPLIT_NO_EMPTY);
    $strSplitLower = array_map('mb_strtolower', $strSplit);
    sort($strSplitLower);
    $result = [];
    foreach ($dictionary as $word) {
      if(mb_strlen($word) <= mb_strlen($letters)) {
        $wordSplit = preg_split('//u', $word, null, PREG_SPLIT_NO_EMPTY);
        sort($wordSplit);
        if (array_map('mb_strtolower', $wordSplit) === $strSplitLower) {
          $result[] = $word;
        }
      }
    }
    return $result;
}

From this you might derive some improvements for your second function.

Answer 3

I will assume all your words only have a-z characters. With that, an efficient check can be made by preprocessing your dictionary:

Pseudocode:

1) Preprocessing:

 words = dictionary
 letters = ['a'..'z']
 wordDataList = []

 for each word in words:
     wordData = new wordData()
     wordData.word = word;
     wordData.num = process(word)
     wordDataList.add(wordData)

 function process(word):
     num = 0
     for idx = 0 to letters.size():
        if letters[idx] in word:
            num = num + (1 << idx)
     return num 

2) Queries:

function query(letters, allowOtherLetters):
    matching = []
    num = process(letters)
    for wordData in wordDataList:
        if (allowOtherLetters == false and wordData.num == num):
            matching.add(wordData.word)
        else if (allowOtherLetters and (wordData.num & num) == num):
            matching.add(wordData.word)

    return matching